主題
Search

Atkin-Goldwasser-Kilian-Morain 證書

素數 p 的遞迴素性證書。該證書包含以下列表：

1. 橢圓曲線 C 上的一個點

y^2=x^3+g_2x+g_3 (mod p)

對於某些數字 g_2 和 g_3。

2. 一個素數 q，其中 q>(p^(1/4)+1)^2，使得對於某些其他數字 k 和 m=kq，其中 k!=1，mC(x,y,g_2,g_3,p) 是曲線上的單位元，但 kC(x,y,g_2,g_3,p) 不是單位元。根據 Goldwasser 和 Kilian (1986) 的一個定理，這保證了 p 的素性。

3. 每個 q 都有其後續的遞迴證書。因此，如果最小的 q 已知是素數，則鏈中的所有數字都被證明是素數。

對於小數字，Pratt 證書生成速度更快。Wolfram 語言任務ProvablePrimeQ[n] 在 Wolfram 語言包PrimalityProving`因此，僅對於超過一定限制的數字（預設情況下為 10^(10)）生成 Atkin-Goldwasser-Kilian-Morain 證書，而對於較小的數字則生成 Pratt 證書。

另請參閱

橢圓曲線素性證明, 橢圓偽素數, Pratt 證書, 素性證書, 證人

使用 探索

參考文獻

Atkin, A. O. L. and Morain, F. "橢圓曲線與素性證明。" Math. Comput. 61, 29-68, 1993.Bressoud, D. M. 因式分解與素性測試。 New York: Springer-Verlag, 1989.Goldwasser, S. and Kilian, J. "幾乎所有素數都可以被快速證明。" Proc. 18th STOC. pp. 316-329, 1986.Morain, F. "Atkin-Goldwasser-Kilian 素性測試演算法的實現。" Rapport de Recherche 911, INRIA, Octobre 1988.Schoof, R. "有限域上的橢圓曲線以及模 p 平方根的計算。" Math. Comput. 44, 483-494, 1985.Wunderlich, M. C. "簡單素性測試演算法的效能分析。" Math. Comput. 40, 709-714, 1983.

在 中被引用

Atkin-Goldwasser-Kilian-Morain 證書

請引用本文為

Weisstein, Eric W. "Atkin-Goldwasser-Kilian-Morain 證書。" 來自 —— 資源。 https://mathworld.tw/Atkin-Goldwasser-Kilian-MorainCertificate.html

主題分類