Deterministic elliptic curve primality proving for a special sequence of numbers

Details Deterministic elliptic curve primality proving for a special sequence of numbers Deterministic elliptic curve primality proving for a special sequence of numbers

2012-02-16

arxiv.org/abs/1202.3695v1

Mathematics

Number Theory

preliminary version, 15 pages

Scientific paper

We give a deterministic algorithm that very quickly proves the primality or compositeness of the integers N in a certain sequence, using an elliptic curve E/Q with complex multiplication by the ring of integers of Q(sqrt(-7)). The algorithm uses O(log N) arithmetic operations in the ring Z/NZ, implying a bit complexity that is quasi-quadratic in log N. Notably, neither of the classical "N-1" or "N+1" primality tests apply to the integers in our sequence. We discuss how this algorithm may be applied, in combination with sieving techniques, to efficiently search for very large primes. This has allowed us to prove the primality of several integers with more than 100,000 decimal digits. We believe that these are the largest proven primes for which no nontrivial partial factorization of N-1 or N+1 is known.

Affiliated with

Also associated with

No associations

Rating

Deterministic elliptic curve primality proving for a special sequence of numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deterministic elliptic curve primality proving for a special sequence of numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic elliptic curve primality proving for a special sequence of numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35000