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

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

素数生成中 ...
素数 p = 9641650943046217731929530997761  ( 103 bits )

p-1 の素因数分解 : [[2, 10], [3, 3], [5, 1], [7, 1], [11, 1], [13, 1], [31, 2],
[67, 1], [83, 1], [1999, 1], [3251, 1], [28723, 1], [69847L, 1]]

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

y = 7575231744515298672286087956073

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

Pohlig-Hellman 法開始
x mod 2^10 = 915
x mod 3^3 = 14
x mod 5^1 = 1
x mod 7^1 = 6
x mod 11^1 = 10
x mod 13^1 = 12
x mod 31^2 = 543
x mod 67^1 = 27
x mod 83^1 = 18
x mod 1999^1 = 1659
x mod 3251^1 = 2388
x mod 28723^1 = 18320
x mod 69847^1 = 4216

解     x   = 7967853146202689962613617197971
検算 : g^x = 7575231744515298672286087956073
       y   = 7575231744515298672286087956073
計算時間   = 0.342000007629