1 Deterministic Elliptic Curve Primality Proving for a Special Sequence of Numbers Alex Abatzoglou, Alice Silverberg, Andrew V. Sutherland, Angela Won...

Author:
Frederick Webster

0 downloads
0 Views
236KB Size

Tenth Algorithmic Number Theory Symposium University of California, San Diego July 9, 2012

Recent History of Primality Proving

Agarwal, Kayal, and Saxena (2004) developed the AKS primality test which runs in deterministic polynomial time. ˜ 6 ) time. The algorithm runs in O(k One can do even better with special sequences of numbers. Pépin’s test, which tests Fermat numbers, and the Lucas-Lehmer test, which tests Mersenne numbers, ˜ 2 ) time. are both deterministic and run in O(k

Recent History of Primality Proving

Agarwal, Kayal, and Saxena (2004) developed the AKS primality test which runs in deterministic polynomial time. ˜ 6 ) time. The algorithm runs in O(k One can do even better with special sequences of numbers. Pépin’s test, which tests Fermat numbers, and the Lucas-Lehmer test, which tests Mersenne numbers, ˜ 2 ) time. are both deterministic and run in O(k

History of EC Primality Proving

Goldwasser-Kilian (1986) gave the first general purpose primality proving algorithm, using randomly generated elliptic curves. Atkin-Morain (1993) improved upon this algorithm by using elliptic curves with complex multiplication. The Atkin-Morain algorithm has a heuristic expected running ˜ k4 . time of O

Prior Work

Our work fits into a general framework given by D. V. Chudnovsky and G. V. Chudnovsky (1986) who used √ elliptic curves with complex multiplication by Q( −D) to give sufficient conditions for the primality of integers in certain sequences {sk }, where sk = NQ(√−D)/Q 1 + α0 α1k , √ for algebraic integers α0 , α1 ∈ Q( −D).

Prior Work We extend the work done by Gross (2004) and Denomme-Savin (2008), who used elliptic curves with CM √ by Q(i) or Q( −3) to test the primality of Mersenne, Fermat, and other related numbers. However, as noted by Pomerance, the families of numbers they consider are susceptible to N − 1 or N + 1 primality tests that are more efficient than their tests using elliptic curves. (see also Gurevich-Kunyavski˘ı (2009, 2012), and Tsumura (2011))

Prior Work We extend the work done by Gross (2004) and Denomme-Savin (2008), who used elliptic curves with CM √ by Q(i) or Q( −3) to test the primality of Mersenne, Fermat, and other related numbers. However, as noted by Pomerance, the families of numbers they consider are susceptible to N − 1 or N + 1 primality tests that are more efficient than their tests using elliptic curves. (see also Gurevich-Kunyavski˘ı (2009, 2012), and Tsumura (2011))

The Plan

Introduce a sequence of numbers, Jk , to test for primality. Present primality test that will tell us if Jk is prime or composite. Prove this primality test

Our Work

We give necessary and sufficient conditions for the primality of integers of the form √ k ! 1 + −7 Jk = NQ(√−7)/Q 1 + 2 . 2 Initial sequence of Jk ’s: 11, 11, 23, 67, 151, 275, 487, 963, 2039, 4211, . . .

Our Work

We use these conditions to give a deterministic algorithm that very quickly proves the primality or compositeness of Jk , using an elliptic curve E/Q with complex multiplication √ by the ring of integers of Q( −7). ˜ 2 ). This algorithm runs in quasi-quadratic time: O(k Note that the sequence of integers Jk does not succumb to classical N − 1 or N + 1 primality tests.

Our Work

We use these conditions to give a deterministic algorithm that very quickly proves the primality or compositeness of Jk , using an elliptic curve E/Q with complex multiplication √ by the ring of integers of Q( −7). ˜ 2 ). This algorithm runs in quasi-quadratic time: O(k Note that the sequence of integers Jk does not succumb to classical N − 1 or N + 1 primality tests.

k ’s for which Jk is prime 2 3 4 5 7 9 10 17 18 28 38 49 53 60

63 65 77 84 87 100 109 147 170 213 235 287 319 375

467 489 494 543 643 684 725 1129 1428 2259 2734 2828 3148 3230

3779 5537 5759 7069 7189 7540 7729 9247 10484 15795 17807 18445 19318 26207

27140 414349 31324 418033 36397 470053 47294 475757 53849 483244 83578 680337 114730 810653 132269 857637 136539 1111930 147647 167068 167950 257298 342647

Large Primes We’ve Found The largest prime we’ve found, J1111930 , has 334,725 decimal digits and is more than a million bits. It is currently the 1311th largest proven prime. We believe this is currently the second largest known prime N for which no significant partial factorization of N − 1 or N + 1 is known and is the largest such prime with a Pomerance proof. We’ve checked all k ≤ 106 and found 78 primes in this range.

Large Primes We’ve Found The largest prime we’ve found, J1111930 , has 334,725 decimal digits and is more than a million bits. It is currently the 1311th largest proven prime. We believe this is currently the second largest known prime N for which no significant partial factorization of N − 1 or N + 1 is known and is the largest such prime with a Pomerance proof. We’ve checked all k ≤ 106 and found 78 primes in this range.

Differences From Chudnovsky-Chudnovsky

Recall Chudnovsky-Chudnovsky only gives sufficient conditions for primality. Our work gives both necessary and sufficient conditions, which allows us to construct a deterministic algorithm. This is done by selecting explicit elliptic curves E/Q and a point P ∈ E(Q) such that P reduces to a point of maximal order 2k +1 mod Jk whenever Jk is prime.

ECPP on Jk

Pomerance (1987) showed that for every prime p > 31, there exists an elliptic curve E/Fp with a point of order 2r > (p1/4 + 1)2 . This can be used to establish the primality of p in r operations. The algorithm we will be presenting for our numbers Jk outputs exactly such a primality proof.

Some Definitions Let E be an elliptic curve over Q. We take points P = [x, y , z] ∈ E(Q) such that x, y , z ∈ Z and gcd(x, y , z) = 1. Definition A point P = [x, y , z] ∈ E(Q) is zero mod N when N | z; otherwise P is nonzero mod N. Definition Given a point P = [x, y , z] ∈ E(Q), and N ∈ Z, we say that P is strongly nonzero mod N if gcd(z, N) = 1.

Some Definitions Let E be an elliptic curve over Q. We take points P = [x, y , z] ∈ E(Q) such that x, y , z ∈ Z and gcd(x, y , z) = 1. Definition A point P = [x, y , z] ∈ E(Q) is zero mod N when N | z; otherwise P is nonzero mod N. Definition Given a point P = [x, y , z] ∈ E(Q), and N ∈ Z, we say that P is strongly nonzero mod N if gcd(z, N) = 1.

Some Definitions Let E be an elliptic curve over Q. We take points P = [x, y , z] ∈ E(Q) such that x, y , z ∈ Z and gcd(x, y , z) = 1. Definition A point P = [x, y , z] ∈ E(Q) is zero mod N when N | z; otherwise P is nonzero mod N. Definition Given a point P = [x, y , z] ∈ E(Q), and N ∈ Z, we say that P is strongly nonzero mod N if gcd(z, N) = 1.

Strongly Nonzero

Remark Note the following: 1

If P is strongly nonzero mod N, then P is nonzero mod p for every prime p|N.

2

If N is prime, then P is strongly nonzero mod N if and only if P is nonzero mod N.

Notation Let √ K = Q( −7),

α=

1+

√ 2

−7

∈ OK ,

jk = 1 + 2αk ∈ OK , Jk = NK /Q (jk ) = 1 + 2(αk + αk ) + 2k +2 ∈ N. We can define Jk recursively, like so: Jk +4 = 4Jk +3 − 7Jk +2 + 8Jk +1 − 4Jk , with initial values J1 = J2 = 11, J3 = 23, and J4 = 67.

Notation Let √ K = Q( −7),

α=

1+

√ 2

−7

∈ OK ,

jk = 1 + 2αk ∈ OK , Jk = NK /Q (jk ) = 1 + 2(αk + αk ) + 2k +2 ∈ N. We can define Jk recursively, like so: Jk +4 = 4Jk +3 − 7Jk +2 + 8Jk +1 − 4Jk , with initial values J1 = J2 = 11, J3 = 23, and J4 = 67.

Sieving the Sequence Jk

When searching for prime Jk over a large range of k , we can accelerate this search by sieving out values of k for which we know Jk is composite: Lemma 1 2

3 | Jk if and only if k ≡ 0 (mod 8), 5 | Jk if and only if k ≡ 6 (mod 24).

Sieving the Sequence Jk

When searching for prime Jk over a large range of k , we can accelerate this search by sieving out values of k for which we know Jk is composite: Lemma 1 2

3 | Jk if and only if k ≡ 0 (mod 8), 5 | Jk if and only if k ≡ 6 (mod 24).

Elliptic Curves

We would like to consider a family of elliptic curves with √ complex multiplication by Q( −7). For a ∈ Q× , define the family of quadratic twists Ea : y 2 = x 3 − 35a2 x − 98a3 . √ Ea has complex multiplication by Q( −7).

The Twisting Parameters a and Points Pa For k > 1 such that k 6≡ 0 (mod 8) and k 6≡ 6 (mod 24), we can choose a twisting factor a and a point Pa ∈ Ea (Q) as follows: k k k k k k

a Pa ≡ 0 or 2 (mod 3) −1 (1, 8) ≡ 4, 7, 13, 22 (mod 24) −5 (15, 50) ≡ 10 (mod 24) −6 (21, 63) ≡ 1, 19, 49, 67 (mod 72) −17 (81, 440) ≡ 25, 43 (mod 72) −111 (−633, 12384)

Primality Test

Theorem Fix k > 1 such that k 6≡ 0 (mod 8) and k 6≡ 6 (mod 24). Based on this k , choose a as in the table above, with the corresponding Pa ∈ Ea (Q). The following are equivalent: 1 2k +1 Pa is zero mod Jk and 2k Pa is strongly nonzero mod Jk , 2 Jk is prime.

Proof (The “Easy” Direction)

Proposition (Goldwasser-Kilian, Lenstra) Let E/Q be an elliptic curve, let N be a positive integer prime to disc(E), let P ∈ E(Q), and let m > (N 1/4 + 1)2 . Suppose mP is zero modN and (m/q)P is strongly nonzero modN for all primes q|m. Then N is prime. 2 1/4 Note that 2k +1 > Jk + 1 for k > 2. Let m = 2k +1 and m q

= 2k . By this proposition, (1) ⇒ (2) of the Theorem.

Proof (The “Harder” Direction)

Recall α =

√ 1+ −7 2

and jk = 1 + 2αk .

Define a set of k ’s such that if jk is prime, then Ea (OK /(jk )) ∼ = OK /(2αk ). Define another set of k ’s such that if jk is prime, then Pa 6∈ α(Ea (OK /(jk ))). Show that for k ’s in the intersection of the two sets for which jk is prime, 2k +1 annihilates Pa mod Jk , but 2k doesn’t.

Frobenius Endomorphism

For prime jk ∈ OK , let E˜a denote the reduction of Ea mod jk . Proposition (Stark) If jk ∈ OK is prime, then the Frobenius endomorphism of E˜a is a jk √ jk . Jk −7

Sa Let a be a squarefree integer. Define a jk √ Sa := k > 1 : =1 . Jk −7 By the Stark result, Lemma Suppose a is a squarefree integer, k > 1, and jk is prime in OK . 1 k ∈ Sa if and only if the Frobenius endomorphism of Ea over the finite field OK /(jk ) is jk . 2 If k ∈ Sa , then Ea (OK /(jk )) ∼ = OK /(2αk ) as OK -modules.

Sa Let a be a squarefree integer. Define a jk √ Sa := k > 1 : =1 . Jk −7 By the Stark result, Lemma Suppose a is a squarefree integer, k > 1, and jk is prime in OK . 1 k ∈ Sa if and only if the Frobenius endomorphism of Ea over the finite field OK /(jk ) is jk . 2 If k ∈ Sa , then Ea (OK /(jk )) ∼ = OK /(2αk ) as OK -modules.

TP

Let a be a squarefree integer, and suppose that P ∈ Ea (K ). Then the field K (α−1 (P)) has degree 1 or 2 √ over K , so it can be written in the form K ( δP ) with δP ∈ K . Assuming jk is prime, let δP TP := k > 1 : = −1 . jk For a ∈ {−1, −5, −6, −17, −111}, let Ta = TPa .

TP

Lemma Suppose that k > 1, jk is prime in OK , and a is a ˜ squarefree integer. Suppose that P ∈ Ea (K ), and let P ˜ ˜ denote the reduction of P mod jk . Then P 6∈ αEa (OK /(jk )) if and only if k ∈ TP .

Proof (The “Harder” Direction)

Define a set Sa of k ’s such that if jk is prime, then Ea (OK /(jk )) ∼ = OK /(2αk ). Define another set Ta of k ’s such that if jk is prime, then Pa 6∈ α(Ea (OK /(jk ))). Show that for k ’s in the intersection of the two sets for which jk is prime, 2k +1 annihilates Pa mod Jk , but 2k doesn’t.

The Twisting Parameters a and Points Pa k k k k k k

a Pa ≡ 0 or 2 (mod 3) −1 (1, 8) ≡ 4, 7, 13, 22 (mod 24) −5 (15, 50) ≡ 10 (mod 24) −6 (21, 63) ≡ 1, 19, 49, 67 (mod 72) −17 (81, 440) ≡ 25, 43 (mod 72) −111 (−633, 12384)

We considered Sa and Ta for a number of values of a, and found these five values covered all cases of k that weren’t sieved out.

Proof Suppose that k > 1 and Jk is prime. Let a be as in the ˜ denote the reduction of Pa table. Then k ∈ Sa ∩ Ta . Let P ˜ in OK . mod jk , and let β be the annihilator of P Since k ∈ Sa , we have Ea (OK /(jk )) ∼ = OK /(2αk ) and therefore β | 2αk . We also have that ˜ 6∈ αE˜a (OK /(jk )). Hence, αk +1 | β. k ∈ Ta ⇒ P ˜ =0 Since 2αk | 2k +1 , but αk +1 - 2k , we must have 2k +1 P ˜ 6= 0. and 2k P

Proof Suppose that k > 1 and Jk is prime. Let a be as in the ˜ denote the reduction of Pa table. Then k ∈ Sa ∩ Ta . Let P ˜ in OK . mod jk , and let β be the annihilator of P Since k ∈ Sa , we have Ea (OK /(jk )) ∼ = OK /(2αk ) and therefore β | 2αk . We also have that ˜ 6∈ αE˜a (OK /(jk )). Hence, αk +1 | β. k ∈ Ta ⇒ P ˜ =0 Since 2αk | 2k +1 , but αk +1 - 2k , we must have 2k +1 P ˜ 6= 0. and 2k P

Proof Suppose that k > 1 and Jk is prime. Let a be as in the ˜ denote the reduction of Pa table. Then k ∈ Sa ∩ Ta . Let P ˜ in OK . mod jk , and let β be the annihilator of P Since k ∈ Sa , we have Ea (OK /(jk )) ∼ = OK /(2αk ) and therefore β | 2αk . We also have that ˜ 6∈ αE˜a (OK /(jk )). Hence, αk +1 | β. k ∈ Ta ⇒ P ˜ =0 Since 2αk | 2k +1 , but αk +1 - 2k , we must have 2k +1 P ˜ 6= 0. and 2k P

Conclusion

We have shown a deterministic algorithm that proves primality or compositeness of our integers Jk . ˜ 2 ). This algorithm runs in time O(k These Jk do not succumb to classical N ± 1 tests.

Future Work

We are currently working on extending our results to other elliptic curves with complex multiplication by imaginary quadratic fields of class number > 1. Another possibility we are considering is extending our results to abelian varieties of higher dimension.

Select Bibliography I D. V. Chudnovsky, G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math 7 no. 4 (1986) 385–434. R. Denomme, G. Savin, Elliptic Curve Primality Tests for Fermat and Related Primes, Journal of Number Theory 128 (2008) 2398–2412. B. Gross, An Elliptic Curve Test for Mersenne Primes, Journal of Number Theory 110 (2005) 114–119.

Select Bibliography II A. Gurevich, B. Kunyavski˘ı, Primality testing through algebraic groups, Arch. Math. (Basel) 93 (2009) 555–564. A. Gurevich, B. Kunyavski˘ı, Deterministic primality tests based on tori and elliptic curves, Finite Fields and Their Applications 18 (2012) 222–236. H. M. Stark, Counting Points on CM Elliptic Curves, The Rocky Mountain Journal of Mathematics 26 (1996) 1115–1138.

"* Life is not a problem to be solved but a reality to be experienced! *"

© Copyright 2013 - 2019 DOKUMENTIS.COM - All rights reserved.