＝＞$M$を素因数分解する。
＝＞まず $x^r mod M$ の位数を求める。

　　除数$M$：
　　基数 $x$ ：

＝＞位数$q$を求める（位数計算）。
　　$x$の$r$乗($r$=0,1,2,3,.....)をMで割った余りの周期が \(x^r mod M\) の位数となる。
　　具体的には横軸を$r$、縦軸を「$x$の$r$乗を$M$で割った余り」とし、
　　この関数を離散フーリエ変換することで周期を求め、それが位数となる。

　　位数$q$：

＝＞次に [\(x^{\frac{q}{2}} -１\)] と [\(x^{\frac{q}{2}} +１\)] を求める。

　　\(x^{\frac{q}{2}} -1\)：（ )
　　\(x^{\frac{q}{2}}+1\)：（ )

＝＞素因数を求める。
　　$M$と[$x^{\frac{q}{2}} -１$]、または$M$と [$x^{\frac{q}{2}} +１$]の最大公約数が素因数となる。
　　 素因数ペア１：（ <==> ）
　　 素因数ペア２：（ <==> ）