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

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

素数生成中 ...
素数 p = 73086403960875902279253078432575953803678470080537559040000001
( 206 bits )

p-1 の素因数分解 : [[2, 25], [3, 2], [5, 7], [7, 2], [11, 2], [17, 1], [19, 4],
[23, 1], [61, 2], [73, 1], [107, 1], [109, 1], [277, 1], [367, 1], [677, 1],
[1543, 1], [1609, 1], [1733, 1], [1847, 1], [2393, 1], [2473L, 1]]

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

y = 22722049013696635649979601135825579285276309041908594914167694

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

Pohlig-Hellman 法開始
x mod 2^25 = 11918347
x mod 3^2 = 7
x mod 5^7 = 28883
x mod 7^2 = 17
x mod 11^2 = 94
x mod 17^1 = 0
x mod 19^4 = 95256
x mod 23^1 = 1
x mod 61^2 = 1227
x mod 73^1 = 35
x mod 107^1 = 50
x mod 109^1 = 12
x mod 277^1 = 204
x mod 367^1 = 215
x mod 677^1 = 368
x mod 1543^1 = 1123
x mod 1609^1 = 1366
x mod 1733^1 = 1091
x mod 1847^1 = 134
x mod 2393^1 = 1524
x mod 2473^1 = 502

解     x   = 13398061156001837383838235702473047673136242716060013661903883
検算 : g^x = 22722049013696635649979601135825579285276309041908594914167694
       y   = 22722049013696635649979601135825579285276309041908594914167694
計算時間   = 0.395000219345