Loading article…
計算数論において、ウィリアムズのp + 1アルゴリズムは、代数群分解アルゴリズムの一種である整数分解アルゴリズムである。これは1982年にヒュー・C・ウィリアムズによって考案された。
因数分解する数Nに、 p + 1 が滑らかであるような素因数p が1 つ以上含まれている場合、つまりp + 1 に小さな因数しか含まれていない場合に、この方法はうまく機能します。二次体におけるべき乗を実行するために、ルーカス数列を使用します。
これはポラードのp - 1アルゴリズム に類似している。実際、p - 1が滑らかな場合、 pを見つけることも可能であり、その場合はポラードのアルゴリズムの低速バージョンに退化する。
ルーカス数列を特徴づける、2より大きい整数Aを選択してください。
すべての演算はNを法として実行されます。
すると、任意の奇素数pはMが倍数であるとき、 どこ そしてはヤコビ記号です。
Mの異なる値に対して、我々は計算する。そして、結果が 1 またはNと等しくない場合、 Nの非自明な因数を見つけたことになります。
滑らかなp + 1を持つpを見つけるには、次のことが必要です。つまり、D はp を法とする非剰余の二次式でなければならない。しかし、 p は事前にわからないため、解を見つける前にAの複数の値を試す必要があるかもしれない。このアルゴリズムは、 Pollardのp - 1アルゴリズム の低速バージョンに退化します。これは50%の確率で発生します。
使用されるMの値は連続階乗であり、は、以下の特徴を持つ数列のM番目の値です。数列BのM番目の要素Vを求めるには、左から右へのべき乗と同様の方法で進めます。
x := B y := (B ^ 2 − 2) mod N 最上位ビットの右側のMの各ビットについて、ビットが 1 の場合は、 x := (x × y − B) mod N y := (y ^ 2 − 2) mod N それ以外 y := (x × y − B) mod N x := (x ^ 2 − 2) mod N V := x
William の p+1 アルゴリズムには、p-1 や Lenstra ECM と同様に「第 2 段階」の拡張があります。上記の手順 (現在は「第 1 段階」と呼ばれています) の後、継続により、緩和された条件で p+1 を見つけることができます。p + 1のすべての因数がBより小さいという要件の代わりに、1 つの因数を除くすべての因数が何らかのB 1 (通常のBと同じ) より小さく、残りの因数が何らかのB 2 ≫ B 1より小さいという要件を課します。[ 1 ] [ 2 ]
N = 112729、A = 5 の場合、は：
この時点で、gcd(110229-2,112729) = 139 なので、139 は 112729 の非自明な因数です。p+1 = 140 = 2 2 × 5 × 7 であることに注目してください。7! は 140 の倍数である最小の階乗なので、このステップで適切な因数 139 が見つかります。
別の初期値、例えばA =9を用いると、次のようになります。
この時点で gcd(91645-2,112729) = 811 なので、811 は 112729 の非自明な因数です。 p−1 = 810 = 2 × 5 × 3 4であることに注目してください。 9! は 810 の倍数である最小の階乗なので、このステップで適切な因数 811 が見つかります。 因数 139 は今回は見つかりません。なぜなら p−1 = 138 = 2 × 3 × 23 であり、これは 9! の約数ではないからです。
これらの例からわかるように、見つかる素数が滑らかな p+1 または p−1 を持つかどうかは事前にわかりません。
ポラードのp − 1およびウィリアムズのp +1 因数分解アルゴリズムに基づいて、エリック・バッハとジェフリー・シャリットは、任意のk番目の円分多項式Φ k ( p ) が滑らかとなるような素因数pを持つnを効率的に因数分解する手法を開発した。[ 3 ] 最初のいくつかの円分多項式は、Φ 1 ( p ) = p −1、Φ 2 ( p ) = p +1、Φ 3 ( p ) = p 2 + p +1、および Φ 4 ( p ) = p 2 +1 のシーケンスで与えられる。
