Loading article…
数論において、証明可能素数とは、素数証明アルゴリズムを使用して素数であると計算された整数である。ポックリントン素数判定を使用したブートストラップ技術は、暗号用の証明可能素数を生成する最も一般的な方法である。[1] [2]確率的素数判定の出力に基づいて素数である可能性が高い（しかし確実ではない）確率的素数 とは対照的である。
原理的には、 AKS素数判定法を用いることで、あらゆる素数が素数であることが多項式時間で証明できる。結果が素数であることを保証するが、すべての素数に対して機能するわけではない他の方法は、証明可能な素数のランダム生成に有用である。[3]
証明可能な素数は組み込みデバイス上でも生成されている。[4]
参照
参考文献
- ^ C. Couvreur と JJ Quisquater (1982)、「大きな素数の高速生成入門」、Philips Journal of Research、第 37 巻、231 ～ 264 ページ
- ^ リチャード・クランドール、カール・ポメランス（2005年）。素数：計算の観点。シュプリンガー。pp. 174–178。ISBN 978-0387-25282-7。
- ^ モリン、リチャード A. (2002)、RSA と公開鍵暗号、離散数学とその応用、CRC プレス、pp. 124–125、ISBN 9781420035247。
- ^ Christophe, Clavier. 「組み込みデバイス上で証明可能な素数を効率的に生成する」(PDF)。国際暗号研究協会。