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

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

素数生成中 ...
素数 p = 55581698592923402741247694373171809774064732140283615317178618709429860
62261169356800000001  ( 302 bits )

p-1 の素因数分解 : [[2, 22], [3, 4], [5, 8], [7, 4], [11, 1], [13, 3], [17, 3],
[19, 2], [29, 1], [41, 1], [47, 1], [59, 2], [67, 1], [73, 1], [101, 1], [109, 1], 
[131, 1], [157, 1], [179, 1], [193, 1], [211, 1], [263, 1], [397, 1], [439, 1], 
[547, 1], [733, 1], [751, 1], [859, 1], [971, 1], [1307, 1], [1721, 1], [1801, 1], 
[5557L, 1]]

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

y = 2566445113347048450861988015693146671988492924964069827252591955900676213204
797092113385943

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

Pohlig-Hellman 法開始
x mod 2^22 = 2905374
x mod 3^4 = 47
x mod 5^8 = 356807
x mod 7^4 = 1277
x mod 11^1 = 4
x mod 13^3 = 1042
x mod 17^3 = 3963
x mod 19^2 = 284
x mod 29^1 = 10
x mod 41^1 = 38
x mod 47^1 = 19
x mod 59^2 = 1652
x mod 67^1 = 42
x mod 73^1 = 23
x mod 101^1 = 90
x mod 109^1 = 57
x mod 131^1 = 19
x mod 157^1 = 100
x mod 179^1 = 141
x mod 193^1 = 118
x mod 211^1 = 65
x mod 263^1 = 88
x mod 397^1 = 199
x mod 439^1 = 419
x mod 547^1 = 150
x mod 733^1 = 697
x mod 751^1 = 241
x mod 859^1 = 839
x mod 971^1 = 412
x mod 1307^1 = 885
x mod 1721^1 = 56
x mod 1801^1 = 233
x mod 5557^1 = 2729

解     x   = 5105452904278247585238336649316245411295053598268709067377986189017
306788889800731221841182
検算 : g^x = 2566445113347048450861988015693146671988492924964069827252591955900
676213204797092113385943
       y   = 2566445113347048450861988015693146671988492924964069827252591955900
676213204797092113385943
計算時間   = 1.16900014877