“Atkin-Goldwasser-Kilian-Morain Certificate”的概念、定义、习题解题方法及翻译-数学辞典

单词 Atkin-Goldwasser-Kilian-Morain Certificate

释义

Atkin-Goldwasser-Kilian-Morain Certificate

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. Thisguarantees 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 thenumbers are certified Prime up the chain.

A Pratt Certificate is quicker to generate for small numbers. The Mathematica (Wolfram Research, Champaign,IL) task ProvablePrime[n] therefore generates an Atkin-Goldwasser-Kilian-Morain certificate only for numbers above acertain limit ( by default), and a Pratt Certificate for smaller numbers.

See also Elliptic Curve Primality Proving,Elliptic Pseudoprime, Pratt Certificate, Primality Certificate, Witness

References

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

Bressoud, D. M. Factorization and Prime 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.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。