EXAMPLE  OF  THE  ATKIN  TEST  (ECPP)

To be tested:

n =  10^60 + 7

  =  1000000000000000000000000000000000000000000000000000000000007

Trial division < 100000
 
  =  2 * 7 * 107 * composite

Pollard < 1000000 steps

  =  2 * 7 * 107 * 1679641 * 8255453 * c_44

unable to factor c_44:   primality proof FAILS.


                                Indeed: http://www.alpertron.com.ar/ECM.HTM


                            48142740675164958124983839862825092751269939  = 

                           152778774688461206737 * 315114064590027073770947


NOW  TRY  WITH  ELLIPTIC   CURVES:

For d = -1, -2 and -3 there is no integer  a  in Q(sqrt(d))  with Norm(a) = p.
Try an elliptic curve with  d = - 7. Then

                           a = 10^30 - sqrt(-7)

Norm(a - 1)  = (10^30 + 1)^2 + 7
             = 1000000000000000000000000000002000000000000000000000000000008

Norm(-a - 1) = (10^30 - 1)^2 + 7
             =  999999999999999999999999999998000000000000000000000000000008

Try the first one:


(10^30 + 1)^2 + 7  =  2^3 * 11 * 29 * 6091 * 10343 * composite

Pollard:
composite  =  233466671 * 26641539363749891267808119193147605196373

               Let  q  =  26641539363749891267808119193147605196373

Rabin-Miller:  q seems prime after 2 tests.

 
So, we test a point P on an elliptic curve with CM by -7.

An elliptic curve E with CM by -7 is given by   Y^2 = X^3 - 35*X + 98  
Consider E modulo p.

point P = [1,8]

(8 * 11 * 29 * 6091 * 10343 * 233466671) * P =

Q = [134909388004237426741439770229014933404027427122877707339028,
     104863395002033207811422392950141345076180678473979694340998]

and 

26641539363749891267808119193147605196373 * Q = \infinity


By the "elliptic" Pocklington test we conclude:

============================================================================
IF q = 26641539363749891267808119193147605196373   IS  PRIME, THEN

 n = 1000000000000000000000000000000000000000000000000000000000007 IS PRIME.

============================================================================

We now concentrate on q.

q - 1 = 2^2 * 3 * 17 * 73 * 157 * 541 * 2053 * 6581 * composite

Pollard:
composite = 24835579 * 62770305230483869
             
             Let  q1 = 62770305230483869

Rabin-Miller test: q1 seems prime after 2 tests.

So, we test a "point" in the multiplicative group Z_q^* namely "2".

2^(q-1) = 1 modulo q and

2^(4 * 3 * 17 * 73 * 157 * 541 * 2053 * 6581 * 24835579) =
19947534424390668500236388436205823483816 mod q

2^(4 * 3 * 17 * 73 * 157 * 541 * 2053 * 6581 * 62770305230483869) =
3432226949137161869203238427902961649420 mod q

Since 24835579 * 62770305230483869  >   sqrt(q) we conclude
by the usual Pocklington test:

============================================================================
IF q1 = 62770305230483869   IS  PRIME, THEN

    q = 26641539363749891267808119193147605196373 IS PRIME.

============================================================================

Now we only need to prove that q1 = 62770305230483869  is prime.
This is easy since the numbers involved are so small. 
We leave this to the reader

q1 - 1 =  4 * 9 * 1743619589735663 

and q2 = 1743619589735663  seems prime after 2 tests.

q2 - 1 = 2 * 871809794867831 

and q3 = 871809794867831 seems prime after 2 tests.

q3 - 1 = 2 * 5 * 7 * 13 * 859 * 26423 * 42209

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
The other elliptic curve ...??

Trial division:

999999999999999999999999999998000000000000000000000000000008

=  2^3 * 7 * 17857142857142857142857142857107142857142857142857142857143


17857142857142857142857142857107142857142857142857142857143 is not prime.


Pollard:

6963301 * 1023641119 * 416194781 * 6019389570987393171008033755972537


6019389570987393171008033755972537 seems prime after 2 tests.



etc .... this should also work out fine.