From this point of view, it is no use saying ``it passed the Miller-Rabin test for me why don't you try it''. In fact (somewhat more surprisingly perhaps) it is no use saying ``I have tried all divisors upto ''. Thus even if you are ``convinced'' that you have a prime; how can you convince someone else without asking the other person to perform an identical computation!

Again group theoretic methods are very useful. In the situation of the
group scheme as above, suppose we find an non-trivial element *g* in
*G*(*N*) whose order *m* is larger than the order of *G*(*p*) for any
prime less than (recall that we have a good estimate of the
order of *G*(*p*)). Let *d* < *m*, then there is some ``co-ordinate'' of
*g*^{d} which differs from the same coordinate for the identity element
of *G*; this is what one means by saying that *g*^{d} is not the
identity element of *G*(*N*). Thus, this difference must be a unit of
/*N* (since we are morally certain that *N* is a prime!). In
particular, for every prime factor *q* of *m* we provide a co-ordinate
of *g*^{m/q} and its inverse *x*_{q} in
/*N*. This is a
certificate of primality.

The person receiving this certificate would argue as follows. Suppose
*p* is the a prime factor of *N* that it is less than . Then
some power *g*^{d} for *d* = *m*/*q* must become trivial in *G*(*p*) (since a
this group cannot have an element of order large than it!). But the
given co-ordinate of *g*^{d} differs from the same co-ordinate of
identity by a unit in
/*N* (we have given a proof of this by
providing *x*_{q}). Thus this co-ordinate cannot be zero. Hence there
are not such prime prime factors--hence *N* is prime.

Thus a primality ``certificate'' would be the tuple
(*G*, *g*, *m*,{*x*_{q}}_{q|}). Of course, the correct-ness of this
certificate depends on the primality of various *q*'s, so we would need a
certificate for those as well!

To make this explicit, suppose we find an element *a* in
/*N*
so that *a*^{m} = 1 but
*a*^{m/q} 1 and
*q* ; for some
integer *m* and a prime factor *q*. Then, *N* is prime; for if *p* is
a factor of *N*, then the
gcd(*a*^{m/q} - 1, *p*) divides
gcd(*a*^{m/q} - 1, *N*) and thus
*a*^{m/q} 1 in
/*p*. But that
means *q* divides *p* - 1. On the other hand, if *N* is not prime, *N*
msut have a prime factor smaller than .

This can be carried some steps further.

As we can see the main stumbling block for this method is that we need
to factor *N* - 1 since the units in
/*N* is the *only*
group available with us (so far) to apply this method to. Later we
will expand the class of groups (and so we can try to *pick* a
group with order easily factorisable) and it will be easier to find
such primality certificates.