素数有限体で一変数多項式の根を見つける高速なアルゴリズムを探しています。
つまり、 (n > 0) の場合、与えられた素数 p に対してを満たすすべての を見つけるアルゴリズムです。f = a0 + a1x + a2x2 + ... + anxnr < pf(r) = 0 mod p
Chiens 検索アルゴリズムhttps://en.wikipedia.org/wiki/Chien_searchを見つけましたが、これが 20 ビットを超える素数に対してそれほど高速であるとは想像できません。チェンの検索アルゴリズムの経験がある人、またはより速い方法を知っている人はいますか? これのためのsympyモジュールはありますか?
mcdowella のコメントが示すように、これはかなりよく研究されています。より一般的な因数分解の代わりに、多項式の根を見つけたい場合にCantor-Zassenhaus ランダム アルゴリズムがどのように機能するかを次に示します。
係数が p を法とする多項式の環では、積 x(x-1)(x-2)...(x-p+1) はすべての可能な根をもち、フェルマーの小定理とこの環で唯一の因数分解。
g = GCD(f,x^px) を設定します。Euclid のアルゴリズムを使用して 2 つの多項式の GCD を計算すると、一般に高速であり、最大次数で対数的な多数のステップを実行します。多項式を因数分解する必要はありません。g は体の f と同じ根をもち、繰り返される因数はありません。
x^px の特別な形式のため、非ゼロ項が 2 つしかないため、ユークリッドのアルゴリズムの最初のステップは、f の次数の 2 倍以下の次数の多項式のみを含む約 2 log_2 (p) ステップで、 2乗を繰り返すことによって実行できます。 、係数 mod p。x mod f、x^2 mod f、x^4 mod f などを計算し、p の 2 進展開のゼロ以外の場所に対応する項を掛け合わせて x^p mod f を計算し、最後に x を減算します。
次のことを繰り返します: Z/p でランダムな d を選択します。g の GCD を r_d = (x+d)^((p-1)/2)-1 で計算します。これは、最初のステップで 2 乗を繰り返すことにより、ユークリッドのアルゴリズムによって再び高速に計算できます。この GCD の次数が厳密に 0 と g の次数の間にある場合、g の非自明な因数が見つかったことになり、線形因数、したがって g の根、したがって f が見つかるまで再帰できます。
これはどのくらいの頻度で機能しますか? r_d は、非ゼロ平方 mod p よりも d 小さい数値を根として持ちます。g の 2 つの異なる根 a と b を考えます。したがって、(xa) と (xb) は g の因数です。a+d が非ゼロ平方で、b+d がそうでない場合、(xa) は g と r_d の公約数ですが、(xb) はそうではありません。つまり、GCD(g,r_d) は g の非自明な因数です。 . 同様に、b+d が非ゼロ平方で、a+d がそうでない場合、(xb) は g と r_d の公約数ですが、(xa) はそうではありません。数論では、d の可能な選択肢の半分近くでどちらかのケースが発生します。つまり、平均して、g の自明でない因数、実際には 1 つの分離 (xa) を見つける前に、一定数の d の選択肢が必要になることを意味します。 (xb) から。
あなたの答えは良いですが、任意の数を法として根を見つける素晴らしい方法を見つけたと思います。この方法は「LATTICES」に基づいています。r ≤ Rをmod pの根とします。hが大きくなく、rがhの根となる h(x)などの別の関数を見つける必要があります。格子法はこの関数を見つけます。最初に、格子の多項式の基底を作成する必要があります。次に、「LLL」アルゴリズムを使用して、モジュロpなしで根rを持つ「最短ベクトル」を見つけます。実際、この方法でmodulo pを消去します。
詳細については、「Coppersmith D. 小さな次数の多項式に対する小さな解を見つける。暗号化とラティスで」を参照してください。