##### Pohlig-Hellman 法実行例 #####

幾つまでの素数を小さいと考えますか ( 100 以上 ) : 1000000
素数 p のビット数を指定してください ( 10 以上 ) : 500

素数生成中 ...
素数 p = 14574037986011467232614402643598517508538769304624820369662336973386849
65803206427952246705819859442308035900475627417525983446798595173452980224000000
001  ( 509 bits )

p-1 の素因数分解 : [[2, 22], [3, 16], [5, 9], [7, 4], [11, 1], [13, 1], [17, 6],
[19, 3], [23, 2], [29, 2], [37, 2], [41, 5], [47, 1], [59, 1], [67, 2], [89, 1], 
[97, 1], [131, 1], [149, 1], [157, 1], [227, 1], [263, 1], [281, 1], [307, 1],
[337, 1], [349, 1], [383, 1], [397, 1], [419, 1], [431, 1], [673, 1], [677, 1],
[2161, 1], [3137, 1], [4357, 1], [6163, 1], [7069, 1], [18143, 1], [20407, 1],
[23663, 1], [33073, 1], [43151, 1], [45751, 1], [560891L, 1]]

原始根計算中 ...
法 p の原始根 g = 93

y = 3527005027171850604543772163428461150209757581737902246102115357002196481566
93308076137735865500242050689361376254215087418168563270977939965680140950578

離散対数 x = log_g(y) を求める

Pohlig-Hellman 法開始
x mod 2^22 = 2667988
x mod 3^16 = 24029804
x mod 5^9 = 1117481
x mod 7^4 = 467
x mod 11^1 = 7
x mod 13^1 = 9
x mod 17^6 = 9794296
x mod 19^3 = 6409
x mod 23^2 = 125
x mod 29^2 = 34
x mod 37^2 = 914
x mod 41^5 = 35686639
x mod 47^1 = 25
x mod 59^1 = 29
x mod 67^2 = 1670
x mod 89^1 = 26
x mod 97^1 = 46
x mod 131^1 = 92
x mod 149^1 = 43
x mod 157^1 = 41
x mod 227^1 = 159
x mod 263^1 = 256
x mod 281^1 = 269
x mod 307^1 = 135
x mod 337^1 = 30
x mod 349^1 = 3
x mod 383^1 = 191
x mod 397^1 = 266
x mod 419^1 = 227
x mod 431^1 = 424
x mod 673^1 = 530
x mod 677^1 = 419
x mod 2161^1 = 523
x mod 3137^1 = 661
x mod 4357^1 = 457
x mod 6163^1 = 2263
x mod 7069^1 = 608
x mod 18143^1 = 4034
x mod 20407^1 = 19364
x mod 23663^1 = 20217
x mod 33073^1 = 15098
x mod 43151^1 = 37824
x mod 45751^1 = 13587
x mod 560891^1 = 411182

解     x   = 6560715744661105264397112972896846725135020586333225039167352146618
78302873120329917276773823027966923551642431353788168736861232350818243357314405
414356
検算 : g^x = 3527005027171850604543772163428461150209757581737902246102115357002
19648156693308076137735865500242050689361376254215087418168563270977939965680140
950578
       y   = 3527005027171850604543772163428461150209757581737902246102115357002
19648156693308076137735865500242050689361376254215087418168563270977939965680140
950578
計算時間   = 27.2409999371