[Luogu 4718]【テンプレート】Pollard-Rhoアルゴリズム[pollrd-ρ][Miller-Rabbin]
Miller−Rabbinは、大きな数のp p pが素数であるかどうかを迅速に検出するために使用される.
0
次に,a a a aをランダムに1回ずつランダムにし,まずフェルマa p−1≡1(m o d p)a^{p−1}equiv 1pmod{p}ap−1≡1(modp)からa p−1 2 k a^{frac{p−1}{2 k}}a 2 kp−1とa p−1 2 k−1 a^{frac{p−1}{2 k−1}}a 2 k−1とa p−1 2 k−1に基づいて2回検出する.比較的一般的な書き方は,a a aとして前⑨素数(2~23)を検出することである.(比較して)小さをすばやく判断することもできます
具体的な手順:ランダムa a、p−1 p−1 p−1の2 2 2を1個ずつ除去し、隣接する2個が二次検出を満たすか否かを判定する
Pollard-ρ 大合数N N N Nを分解する.
誕生日パラドックスの思想の核心はx 1⋯x n x_を組み合わせて選択することにある.1\cdots x_n x1⋯xn ;(∣x i−x j∣,N)∈(1,N)(|x_i−x_j|,N)in(1,N)(∣xi−xj∣,N)∈(1,N)では,N N N Nの因数∣x i−x j∣|x_i-x_j| ∣xi−xj∣ . x i x_ixiは完全にx i−1 x_{i−1}xi−1が決定すると明らかにループする.誕生日パラドックスサイクル節の期待O(p)O(sqrt{p})O(p)に基づいて,j=2 i j=2 i=2 i,i i i iを列挙し,現在N Nがふるいにかけられていない最小素因数p pを仮定した.(最小のそれを考えるのは……型のサイクルが最小なので、先にそれを出す確率が高い)そしてy u=x u%p y_u=x_u%p yu=xu%pは一定のサイクル(たぶん?)比x u x_uxuは早いのでx i=k 1 p+y 1,x 2 i=k 2 p+y 2 x_i=k_1p+y_1,x_{2i}=k_2p+y_2 xi=k1p+y1,x2i=k2p+y2 . このとき(∣x i−x j∣,N)(|x_i−x_j|,N)(∣xi−xj∣,N)を求めるとp p p pが得られる.y y y yサイクル節はpsqrt{p}pが期待され、y y yは約≦Nlesqrt{N}≦Nが期待されるので、O(N 1/4)O(N^{1/4})O(N 1/4)が期待される
Pollardで-ρ では、x 1=2 x_を選択します.1=2 x 1=2、そしてx i≡x i−1 2+α x_i\equiv x_{i-1}^2+\alpha xi≡xi−12+α ,これでは2 2 2 2を判断できないので特判(2 2 2を判断できない証明:モジュール4 4 4の意味に気づくと発生するだけα + 1\alpha+1 α+1またはα\alpha α )
1つの最適化可能な点は、i i i当を列挙し続け、(x i−x j∣,N)=1(|x_i−x_j|,N)=1(∣xi−xj∣,N)=1が一般的にバッチgcdを用いて加速し、一般的にはN 10sqrt[10]{N}10 Nを一括gcdを求めるステップとして有効に複雑さを低減できることに留意することである(確かにそうだ.
具体的な手順:コードがはっきりしていてかわいい
#include
", p);
}
return 0;
}