ソロベイ–シュトラッセン素数判定法

ウィキペディア

ソロベイ–シュトラッセン素数判定法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/15 15:31 UTC 版)

ソロベイ–シュトラッセン素数判定法（英: Solovay–Strassen primality test）は、Robert M. Solovayとフォルカー・シュトラッセンによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではBaillie–PSW primality testやミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。

概要

レオンハルト・オイラーは任意の素数pと整数aに対して、

$a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$ この項目は、数論に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。