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

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

素数生成中 ...
素数 p = 76565942884384537084560529064335782213698447735290903882874881  ( 206 b
its )

p-1 の素因数分解 : [[2, 14], [3, 9], [5, 1], [7, 3], [11, 1], [17, 2], [23, 1],
[41, 2], [131, 1], [227, 1], [241, 1], [263, 1], [307, 1], [1987, 1], [3527, 1],
 [4507, 1], [4931, 1], [98377, 1], [321821, 1], [394759L, 1]]

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

y = 42130946832411370496544871476575693092165399403511279742513125

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

Pohlig-Hellman 法開始
x mod 2^14 = 12421
x mod 3^9 = 8651
x mod 5^1 = 0
x mod 7^3 = 298
x mod 11^1 = 5
x mod 17^2 = 50
x mod 23^1 = 13
x mod 41^2 = 725
x mod 131^1 = 49
x mod 227^1 = 61
x mod 241^1 = 229
x mod 263^1 = 158
x mod 307^1 = 145
x mod 1987^1 = 1065
$
x mod 4507^1 = 2694
x mod 4931^1 = 9
x mod 98377^1 = 741
x mod 321821^1 = 243402
x mod 394759^1 = 56345

解     x   = 46217918190425363484578736833868027916662199571771267175903365
検算 : g^x = 42130946832411370496544871476575693092165399403511279742513125
       y   = 42130946832411370496544871476575693092165399403511279742513125
計算時間   = 4.40499997139