## Elliptic curve primality proving

Expand Messages
• Hello. I attempted to write a prime number test routine based on this web page. http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving It would be nice
Message 1 of 49 , Mar 11, 2012
• 0 Attachment
Hello.

I attempted to write a prime number test routine based on this web page.

http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving

It would be nice to have a reasonable quick algorithm that actually
proved an integer to be prime or composite, rather than being able
only to prove that a composite z is composite.

I would of course precede the call to this prime proving routine
by a fast composite proving routine which would screen out almost
all composites.

The problem is that this web page is difficult for me to follow.

Is there any resource that explains the elliptic curve primality algorithm
in a simple step by step description?

Kermit
• Hi, I had a methodology(may be not efficient had a intuition it will be useful) to generate all odd composite. Factors of all odd composites are predetermined
Message 49 of 49 , May 7, 2012
• 0 Attachment
Hi,
I had a methodology(may be not efficient had a intuition it will be useful) to generate all odd composite. Factors of all odd composites are predetermined through multiples of 4. Let A(n) = 4n where n = 1,2,3... Then A(n) = P1Q1 = P2Q2 = ..... = PkQk be the 'K' possible set of distinct even factors(means both Pk,Qk  should even) such that Pk > Pk-1 > Pk-2 > ....> P1 then  (Pk  + 1) (Qk  + 1),   (Pk-1 + 1)(Qk-1  + 1), ......   (P1 + 1)(Q 1  + 1)    will eventually generate all odd composite numbers. For e.g. A(1) = 4 = 2x2 here P1 = 2, Q1  = 2. Then (P1 + 1)(Q 1  + 1) = (2 + 1)(2 +1) = 9 First odd composite. A(2) = 8 = 2x4 here P1 = 2, Q1  = 4. Then (P1 + 1)(Q 1  + 1) = (2 + 1)(4 +1) = 15 second odd composite A(3) = 12 = 2x6 => 3x7 = 21  third odd composite A(4) = 16 = 2x8 = 4x4 => 5x5 =25 fourth odd composite and 3x9 = 27 fifth odd composite like that it continues. Based on this i found a methodology to
sieve Primes in given range 'a' to 'b' a,b both odd numbers. Write all the odd composite between 'a' to 'b' Find 'm' even such that 3(m + 1) <= 'a' < 3(u + 3) Now v= u/2 Calculate 4v = P1Q1 = P2Q2 = ..... = PkQk Then omit the following numbers  (Pk  + 1) (Q k  + 1),   (Pk-1 + 1)(Q k-1  + 1), ......    (P1 + 1)(Q 1  + 1)  which falls in the range 'a' to 'b' Now increment 'k' and repeat the procedure till (Pk  + 1) (Q k  + 1) > b. Now the remaining numbers are prime.

With regards