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

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

素数生成中 ...
素数 p = 19760231768429748842094811216950118816145718330390015467459705080324913
95660678587383664508099362197009688972881524068916189330315063627995288167427910
82588964830206750074398625527715611355078485219138290981345729931727549923593037
233700004869084230176925188170022408573688787523993600000000000000000000001  
( 1015 bits )

p-1 の素因数分解 : [[2, 38], [3, 17], [5, 23], [7, 6], [11, 6], [13, 6], [17, 2], 
[23, 2], [29, 1], [31, 3], [37, 1], [47, 2], [53, 1], [61, 1], [67, 2], [71, 1], 
[83, 1], [89, 1], [97, 1], [103, 1], [109, 1], [113, 1], [127, 1], [197, 2],
[233, 1], [269, 1], [293, 1], [349, 1], [373, 1], [419, 1], [443, 1], [577, 1],
[709, 1], [953, 1], [2069, 1], [2221, 1], [2861, 1], [3517, 1], [4003, 1], [4759, 1], 
[4799, 1], [6197, 1], [6653, 1], [7867, 1], [8387, 1], [8447, 1], [13103,1], 
[14747, 1], [16943, 1], [18899, 1], [23669, 1], [25237, 1], [33113, 1], [33751, 1], 
[53731, 1], [68687, 1], [123289, 1], [173149, 1], [178567, 1], [191561,1], 
[278353, 1], [322433, 1], [382363, 1], [438601, 1], [648107, 1], [660769, 1], 
[708473, 1], [1335233, 1], [2640857, 1], [3213101, 1], [9670207, 1], [9951257L, 1]]

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

y = 4303154387186053566765845700889163565585300747709478732664829150400624237162
59783537955491989525522957872046486661927260099507606519796741871184320353746725
75616523023079841532728165395529919110416072765178050013766265754620576217124997
87517778635805394923075944253019414735106214861232233137319684452433

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

Pohlig-Hellman 法開始
x mod 2^38 = 142586713512
x mod 3^17 = 17564096
x mod 5^23 = 11607461964575587
x mod 7^6 = 19306
x mod 11^6 = 1047249
x mod 13^6 = 54786
x mod 17^2 = 25
x mod 23^2 = 488
x mod 29^1 = 24
x mod 31^3 = 29608
x mod 37^1 = 20
x mod 47^2 = 851
x mod 53^1 = 27
x mod 61^1 = 43
x mod 67^2 = 835
x mod 71^1 = 57
x mod 83^1 = 40
x mod 89^1 = 30
x mod 97^1 = 87
x mod 103^1 = 66
x mod 109^1 = 73
x mod 113^1 = 2
x mod 127^1 = 109
x mod 197^2 = 19948
x mod 233^1 = 224
x mod 269^1 = 21
x mod 293^1 = 86
x mod 349^1 = 297
x mod 373^1 = 218
x mod 419^1 = 92
x mod 443^1 = 101
x mod 577^1 = 401
x mod 709^1 = 346
x mod 953^1 = 867
x mod 2069^1 = 491
x mod 2221^1 = 714
x mod 2861^1 = 2120
x mod 3517^1 = 2817
x mod 4003^1 = 2033
x mod 4759^1 = 3426
x mod 4799^1 = 1246
x mod 6197^1 = 5648
x mod 6653^1 = 5315
x mod 7867^1 = 1971
x mod 8387^1 = 2854
x mod 8447^1 = 5444
x mod 13103^1 = 989
x mod 14747^1 = 7791
x mod 16943^1 = 2141
x mod 18899^1 = 1758
x mod 23669^1 = 13350
x mod 25237^1 = 1099
x mod 33113^1 = 10201
x mod 33751^1 = 28176
x mod 53731^1 = 14409
x mod 68687^1 = 22224
x mod 123289^1 = 118066
x mod 173149^1 = 155741
x mod 178567^1 = 39725
x mod 191561^1 = 144060
x mod 278353^1 = 112687
x mod 322433^1 = 24500
x mod 382363^1 = 369052
x mod 438601^1 = 356733
x mod 648107^1 = 536216
x mod 660769^1 = 230679
x mod 708473^1 = 295964
x mod 1335233^1 = 839979
x mod 2640857^1 = 653311
x mod 3213101^1 = 1983059
x mod 9670207^1 = 690160
x mod 9951257^1 = 8143335

解     x   = 1302045894841530823144298523008575799025636656409822044631184947546
76013911869004035781097215901954712167795565329307286166526514724450296369181677
03196273983788981287310845382726866937119584828823744483335481059136449672917022
8487937992647454107747656295047084399876939410439742441749764179869943654028712

検算 : g^x = 4303154387186053566765845700889163565585300747709478732664829150400
62423716259783537955491989525522957872046486661927260099507606519796741871184320
35374672575616523023079841532728165395529919110416072765178050013766265754620576
21712499787517778635805394923075944253019414735106214861232233137319684452433

       y   = 4303154387186053566765845700889163565585300747709478732664829150400
62423716259783537955491989525522957872046486661927260099507606519796741871184320
35374672575616523023079841532728165395529919110416072765178050013766265754620576
21712499787517778635805394923075944253019414735106214861232233137319684452433

計算時間   = 2164.65200019