数論アルゴリズム

円分合同式テスト
５．２５川原未鈴
1
4.3.3 計算手順
P.104～
算法4.3.3では𝑟を手順中に求めるが、最初に上界𝑅 ≥ 𝑟の入力が必要であるため
具
体的評価を与えておかなくてはいけない.
そのとき、注意4.3.1より k < 𝑟 < 𝑛≢0 mod 2 、したがって 𝑛 ≥ 263と仮定し
て考える。
𝑀 ≔ ｌｃｍ{𝑛 𝑗 -1| 𝑗 ∈ ℕ≤𝑘 } とすると
これに対して
𝑟 = min{𝑝 ∈ ℙ
𝑟 ≤ ⎾lg𝑀⏋ < 6.5⎾lg 2 𝑛⏋5/2
|
𝑝 ⫮ 𝑀}である
(4.12)
を証明する.
（ⅰ） 𝑟 ≤ ⎾lg𝑀⏋ の証明
一般にL以下の全ての素数𝑝 ∈ ℙの積の下からの評価
𝑝 > 2𝐿
𝑝∈ ℙ≤𝐿
𝐿 ∈ ℤ>677
が𝑝. 68の 3.14 から示される.
そこで𝐿 ≔ ⎾lg𝑀⏋とすれば𝑛 ≥ 263の範囲では
𝐿
𝐿 ≥ ⎾ lg 𝑛𝑘−1 − 1 ⏋ ≥ 2083 > 677,
𝑝∈ ℙ≤𝐿 𝑝 > 2 ≥ 𝑀…＊
となる.
もし、全ての𝑝 ∈ ℙ≤𝐿 が𝑀を割り切っていたとしたら、 𝑝∈ ℙ≤𝐿 𝑝 < 𝑀となり、
＊に矛盾。よって、全ての𝑝 ∈ ℙ≤𝐿 が𝑀を割り切ることはない。
なので、 𝑀を割り切らない𝑝 ∈ ℙ≤𝐿 の最小が𝑟となるので、𝑟 ≤ ⎾lg𝑀⏋が成り立2
つ。
（ⅱ） ⎾lg 𝑀⏋ < 6.5⎾lg 2 𝑛⏋5/2 の証明
𝑙 = ⎾lg 2 𝑛⏋, 𝑚 = 4𝑙 − 1 とすると4𝑙 = 𝑘, 𝑚 = 𝑘 − 1となる。
Mの定義の中の(𝑛 − 1)は、
定義中の𝑛2 − 1＝(𝑛 − 1)(𝑛 + 1）の赤の部分とかぶるので考えなくて
よい。
同様に（𝑛3 − 1）も
𝑛6 − 1＝ 𝑛3 − 1 𝑛3 + 1 の赤の部分とかぶるので考えなくてよい。
これを考えていくと、𝑛2𝑠−1 − 1は𝑛4𝑠−2 − 1＝ 𝑛2𝑠−1 − 1 𝑛2𝑠−1 + 1
の赤の部分とかぶるので
𝑛2𝑠−1 − 1 (1 ≤ 𝑠 ≤ ⎿(𝑚 + 2)/4⏌= 𝑙)は不用である。
𝑙
𝑛4𝑠−2 − 1 (1 ≤ 𝑠 ≤ ⎿(𝑚 + 4)/8⏌=⎿ ⏌)も同様に不用。
2
したがって,
𝑀<
<
=𝑛
𝑠∈ℕ<𝑙 ( 𝑛
𝑠∈ℕ<𝑙 𝑛
4𝑠
4𝑠
− 1)
𝑠∈ℤ
𝑠∈ℤ
𝑙
>⎿2⏌,≤𝑙
𝑙
>⎿2⏌,≤𝑙
𝑛4𝑠−2
( 𝑛4𝑠−2 − 1)
𝑠∈ℤ>𝑙,≤2𝑙 𝑛
𝑠∈ℤ>𝑙,≤2𝑙 ( 𝑛
2𝑠−1
− 1)
2𝑠−1
2𝑙
𝑙−1 4𝑠+ 𝑙
𝑠=1
𝑠=⎿𝑙/2⅃(4𝑠−2)+ 𝑠=𝑙+1(2𝑠−1)
𝑙
7𝑙 2 −2⎿2⏌2 −2𝑙
2
=𝑛
< 𝑛13𝑙 /2
両辺 lg をとれば⎾lg 𝑀⏋ < 6.5⎾lg 2 𝑛⏋5/2 が成り立つ。
（ⅰ）、（ⅱ）より 𝑟 ≤ ⎾lg𝑀⏋ < 6.5⎾lg 2 𝑛⏋5/2 が証明された。
∎
3
4.3.4
計算量
算法4.3.3CCTの多項式時間停止性を証明する
(ⅰ)冪検出は線形時間
(ⅱ）素数表作成の合成数篩CSによる計算量はｐ.34(2.1)
より
𝑅lg𝑅
𝑂
lglg𝑅
(ⅲ）𝑘 = 𝑂 lg 2 𝑛 回のP ∈ ℙ≤𝑟 を法とする合同式演算
であ
り、高速乗算法を使えば注意1.3.2と定理2.1.3PNTか
≪参考≫
ら注意1.3.2 Õを次のように定義する：
𝑓 = Õ 𝑔 : ⇔ 域𝑘 ∈ ℤ≥0 に対し𝑓 2= 𝜪(𝑔lg 𝑘 𝑔)
𝑂(# ℙ≤𝑟
lg𝑟lglg𝑟lglglg𝑟lg 𝑛)=𝑂(𝑟lglg𝑟lglglg𝑟lg 2 𝑛)
既知最高速算法ならば、乗除算計算量は
Õ(lg𝑛)BC
定理2.1.3
𝜪（ｌｇ𝑛ｌｇｌｇ𝑛ｌｇｌｇｌｇ𝑛） =
である
# ℙ≤𝑛
lim 𝑛/ｌｎ
=1
𝑛
𝑛→+∞
4
（ⅳ)各b ∈ ℕ≤𝑟 に対する(4.10)のテストが(4.11)の通り
だから全部でr回のテストは
𝑂(𝑟 2 lg 𝑟lg 2 𝑛 lglg 𝑛 lglglg 𝑛 )・・・★
𝑟次式２つを１回かけるのに必要な計算
量
𝑟・𝑟lg𝑟・lg𝑛・lg𝑛lglg𝑛lglglg𝑛
全部でｒ回反復二乗法よりlg𝑛 １回の乗算に必要な計算
量
回
5
ここで（4.12）により𝑟 ≤ 𝑅 = 𝑂(lg 𝑛)とすれば、★
が最も計算量の大きいところで
定理4.3.2
算法4.3.3円分合同式テストCCTの計算量は
𝑂(lg12 𝑛(lglg 𝑛) 2 lglglg 𝑛 )=Õ lg12 𝑛
5
定理4.3.2は多項式時間であるが実用的にはＳＰｓＰＴのＥ
ＺＨを仮定した評価(4.6)
𝑂（lg 4 𝑛lglg𝑛lglglg𝑛） =
Õ(lg 4 𝑛)
とこの評価を比較すると遥かに及ばない.
しかし、予想4.3.1が成立すれば計算量がＳＰｓＰＴに勝る
Õ（lg 3 𝑛）の決定性アルゴリズムが提案されている.
予想4.3.1
もし、𝑟 ∈ ℙ, 𝑟 ⫮ 𝑛, 𝑏 = −1 に対して𝑃. 103の 4.10
が成立するならば
𝑛 ∈ ℙ 又は 𝑛2 ≡ 1 (mod 𝑟)
しかしこの予想はおそらく成立しないだろうという考察も
されている.
以上の様に、この「PRIMES∈P」を理論的に解決したアル
ゴリズムもまだまだ実践的には非常に多くの課題が残され
6

Download Report