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

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

素数生成中 ...
素数 p = 17754751957617977892817997909596557809282928714031949886947781094539923
991670840605122179891201  ( 314 bits )

p-1 の素因数分解 : [[2, 33], [3, 8], [5, 2], [7, 6], [11, 2], [19, 1], [23, 1],
[29, 1], [31, 1], [41, 1], [43, 1], [47, 1], [53, 1], [59, 1], [127, 1], [173, 1], 
[197, 1], [229, 1], [257, 1], [743, 1], [797, 1], [857, 1], [1093, 1], [4813, 1], 
[18743, 1], [70111, 1], [75223, 1], [144569, 1], [895393, 1], [999329L, 1]]


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

y = 1162290546857350245606254695757381521912868328032339480863406480951337322895
7437893819798559773

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

Pohlig-Hellman 法開始
x mod 2^33 = 1200782251
x mod 3^8 = 4133
x mod 5^2 = 2
x mod 7^6 = 70968
x mod 11^2 = 86
x mod 19^1 = 12
x mod 23^1 = 7
x mod 29^1 = 19
x mod 31^1 = 12
x mod 41^1 = 38
x mod 43^1 = 40
x mod 47^1 = 33
x mod 53^1 = 20
x mod 59^1 = 53
x mod 127^1 = 102
x mod 173^1 = 35
x mod 197^1 = 122
x mod 229^1 = 221
x mod 257^1 = 186
x mod 743^1 = 503
x mod 797^1 = 726
x mod 857^1 = 433
x mod 1093^1 = 91
x mod 4813^1 = 2537
x mod 18743^1 = 3250
x mod 70111^1 = 64466
x mod 75223^1 = 15364
x mod 144569^1 = 89324
x mod 895393^1 = 31722
x mod 999329^1 = 361929

解     x   = 8558869551641606682065713638653931364351848739369861323255013294436
730782086559225384713485227
検算 : g^x = 1162290546857350245606254695757381521912868328032339480863406480951
3373228957437893819798559773
       y   = 1162290546857350245606254695757381521912868328032339480863406480951
3373228957437893819798559773
計算時間   = 13.4330000877