From: Wei Dai (weidai@eskimo.com)
Date: Fri Jun 14 2002 - 09:45:28 MDT
On Fri, Jun 14, 2002 at 06:04:30AM -0400, Eliezer S. Yudkowsky wrote:
> There are tests for primeness that don't use factoring; they are
> probabilistic rather than absolute tests, but you can obtain a very high
> probability of primeness by applying the tests repeatedly. That's how PGP
> generates 4096-bit private keys in less than the age of the universe.
There are fast provable primality tests too. The following took just a
second in Mathematica 4. See the end for notes from the Mathematica
manual.
In[1]:= << NumberTheory`PrimeQ`
In[2]:=
ProvablePrimeQ[30082232218581187462432471034748868284388270918928732239,
Certificate -> True]
Out[2]=
{True, {{CertificatePrime ->
30082232218581187462432471034748868284388270918928732239,
CertificatePoint ->
PointEC[2,
3833475313076111899084512459256560013358990607795956251,
9549914990025773797597609852301228026789927275850391185,
16394020732877578352542563579783774779322708490209838203,
30082232218581187462432471034748868284388270918928732239],
CertificateK -> 534412256,
CertificateM ->
30082232218581187462432471026803315847883063578061013024,
CertificateNextPrime ->
56290311236015491872313031359077430753914190879,
CertificateDiscriminant -> -7}, {CertificatePrime ->
56290311236015491872313031359077430753914190879,
CertificatePoint ->
PointEC[2, 11750259512280963367152217666969523979258472324,
19367677208189431455607079953572663791480457277,
31675221884131451594509063755407586112291701811,
56290311236015491872313031359077430753914190879],
CertificateK -> 776801620764,
CertificateM -> 56290311236015491872313433677528395182689931484,
CertificateNextPrime -> 72464204156336388558088270746846481,
CertificateDiscriminant -> -43}, {CertificatePrime ->
72464204156336388558088270746846481,
CertificatePoint ->
PointEC[7, 62074838238401657766484359318708744,
43708567586361631193767528386986431,
40641299685564323741573315868598824,
72464204156336388558088270746846481], CertificateK -> 4,
CertificateM -> 72464204156336389049660750247314996,
CertificateNextPrime -> 18116051039084097262415187561828749,
CertificateDiscriminant -> -7}, {CertificatePrime ->
18116051039084097262415187561828749,
CertificatePoint ->
PointEC[2, 10187535381242412221347386949140768,
17608447148298042930773964684477404,
17439245851369358153560223725360289,
18116051039084097262415187561828749], CertificateK -> 1138767,
CertificateM -> 18116051039084097262271078005457541,
CertificateNextPrime -> 15908479117399869562668287723,
CertificateDiscriminant -> -35}, {CertificatePrime ->
15908479117399869562668287723,
CertificatePoint ->
PointEC[2, 3961195425499771976063092764,
3748380051780674275433900815,
13104572779453695892068125692, 15908479117399869562668287723],
CertificateK -> 92030415, CertificateM ->
15908479117400118848470655415,
CertificateNextPrime -> 172861103770966575001,
CertificateDiscriminant -> -11}, {CertificatePrime ->
172861103770966575001,
CertificatePoint ->
PointEC[2, 90444630819751908344, 46645059747721139284,
88717074422136284523, 172861103770966575001], CertificateK ->
13568,
CertificateM -> 172861103771543784704,
CertificateNextPrime -> 12740352577501753,
CertificateDiscriminant -> -7}, {CertificatePrime ->
12740352577501753,
CertificatePoint ->
PointEC[2, 2735010993189134, 12538124758811247, 8358749839207498,
12740352577501753], CertificateK -> 15268,
CertificateM -> 12740352803230756, CertificateNextPrime ->
834448048417,
CertificateDiscriminant -> -7}, {CertificatePrime -> 834448048417,
CertificatePoint ->
PointEC[2, 820506324948, 264904142305, 604864458211,
834448048417],
CertificateK -> 1072, CertificateM -> 834449363504,
CertificateNextPrime -> 778404257, CertificateDiscriminant -> -7},
778404257,
3, {2, {7, 3, {2, {3, 2, {2}}}}, {73, 5, {2, {3, 2, {2}}}}, {181,
2, {2, {3, 2, {2}}, {5, 2, {2}}}}, {263,
5, {2, {131, 2, {2, {5, 2, {2}}, {13, 2, {2, {3, 2, {2}}}}}}}}}}}
The certificate of primality used in this package for large n is based on
the theory of elliptic curves. The basic idea was discovered by S.
Goldwasser and J. Kilian, "Almost All Primes Can Be Quickly Certified," in
Proc. 18th STOC, 1986, pp. 316–329. Their algorithm was only of
theoretical significance, however. A. O. L. Atkin found a way to make it
practical by using ideas from complex multiplication, which is a branch of
number theory that combines the fields of complex analysis, Galois theory
and modular forms. This method was implemented very successfully by F.
Morain in "Implementation of the Atkin-Goldwasser-Kilian Primality Testing
Algorithm," INRIA Research Report, # 911, October 1988. In November 1989,
Morain was able to give a primality proof for a 1065-digit number, the
first titanic prime (> 1000 digits) to be tested without special purpose
algorithms. Since that time Atkin and Morain have written an extensive
treatise on the algorithm: A. O. L. Atkin and F. Morain, "Elliptic Curves
and Primality Proving," Mathematics of Computation, 1993, 29-68.
For an introduction to primality testing and elliptic curves, see D.
Bressoud, Factorization and Primality Testing, Springer-Verlag, 1989.
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:14:47 MST