A recursive primality certificate for a prime . The certificate consists of a list of

1. A point on an elliptic curve 

for some numbers  and .

2. A prime  with , such that for some other number  and  with ,  is the identity on the curve, but  is not the identity. This guarantees primality of  by a theorem of Goldwasser and Kilian (1986).

3. Each  has its recursive certificate following it. So if the smallest  is known to be prime, all the numbers are certified prime up the chain.

A Pratt certificate is quicker to generate for small numbers. The Wolfram Language task ProvablePrimeQ[n] in the Wolfram Language package PrimalityProving` therefore generates an Atkin-Goldwasser-Kilian-Morain certificate only for numbers above a certain limit ( by default), and a Pratt certificate for smaller numbers.

REFERENCES:

Atkin, A. O. L. and Morain, F. "Elliptic Curves and Primality Proving." Math. Comput. 61, 29-68, 1993.

Bressoud, D. M. Factorization and Primality Testing. New York: Springer-Verlag, 1989.

Goldwasser, S. and Kilian, J. "Almost All Primes Can Be Quickly Certified." Proc. 18th STOC. pp. 316-329, 1986.

Morain, F. "Implementation of the Atkin-Goldwasser-Kilian Primality Testing Algorithm." Rapport de Recherche 911, INRIA, Octobre 1988.

Schoof, R. "Elliptic Curves over Finite Fields and the Computation of Square Roots mod ." Math. Comput. 44, 483-494, 1985.

Wunderlich, M. C. "A Performance Analysis of a Simple Prime-Testing Algorithm." Math. Comput. 40, 709-714, 1983.a

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد