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

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

素数生成中 ...
素数 p = 23587630700582190785702063926031043837931518390228338967644804833705158
01840245622196661682875442347439227446726483331753387305373478925536574660741358
97096309511123828553835932916810881910669162268358090670415229631185471385730338
8465141999858296107799672659998512379383124098515013474451456000000000001  
( 1008 bits )

p-1 の素因数分解 : [[2, 63], [3, 20], [5, 12], [7, 3], [11, 5], [13, 4], [17, 7]
, [19, 1], [23, 2], [29, 1], [31, 2], [37, 2], [41, 2], [59, 1], [61, 2], [67, 1], 
[71, 1], [73, 1], [83, 1], [89, 1], [97, 1], [127, 1], [137, 2], [149, 1], [163, 1], 
[179, 1], [197, 2], [211, 1], [223, 1], [239, 1], [269, 1], [419, 1], [421, 1], 
[439, 1], [461, 1], [503, 1], [547, 1], [809, 1], [821, 1], [839, 1], [877, 1], 
[1423, 1], [1429, 1], [1439, 1], [1621, 1], [1627, 1], [1697, 1], [2593, 1], 
[2671, 1], [2789, 1], [2999, 2], [3187, 1], [3853, 1], [4211, 1], [4679, 1], 
[5527, 1], [6317, 1], [6607, 1], [6703, 1], [7817, 1], [11399, 1], [20071, 1],
[30427, 1], [32909, 1], [34513, 1], [42649, 1], [47807, 1], [58601, 1], [71471, 1], 
[73681, 1], [106637, 1], [178151, 1], [268063, 1], [295873, 1], [312047, 1], 
[439613, 1], [514081, 1], [641549L, 1]]

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

y = 2283797796212620461510129423506787330187297414931590604988996829724096107652
98515485289783258542967391349916458517286975320190570042023078678031871392016291
88698841634464208160411458956195499749743024656983055471670281436677916412052431
6436667752164324764779723904098313988588604337167531364078868307589

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

Pohlig-Hellman 法開始
x mod 2^63 = 1219780353157657304
x mod 3^20 = 463422322
x mod 5^12 = 105511518
x mod 7^3 = 15
x mod 11^5 = 120785
x mod 13^4 = 19323
x mod 17^7 = 385944406
x mod 19^1 = 13
x mod 23^2 = 223
x mod 29^1 = 27
x mod 31^2 = 92
x mod 37^2 = 998
x mod 41^2 = 1038
x mod 59^1 = 46
x mod 61^2 = 2441
x mod 67^1 = 13
x mod 71^1 = 29
x mod 73^1 = 26
x mod 83^1 = 30
x mod 89^1 = 24
x mod 97^1 = 35
x mod 127^1 = 21
x mod 137^2 = 15652
x mod 149^1 = 110
x mod 163^1 = 104
x mod 179^1 = 37
x mod 197^2 = 24998
x mod 211^1 = 105
x mod 223^1 = 82
x mod 239^1 = 211
x mod 269^1 = 206
x mod 419^1 = 110
x mod 421^1 = 326
x mod 439^1 = 330
x mod 461^1 = 427
x mod 503^1 = 308
x mod 547^1 = 222
x mod 809^1 = 170
x mod 821^1 = 330
x mod 839^1 = 163
x mod 877^1 = 812
x mod 1423^1 = 1268
x mod 1429^1 = 396
x mod 1439^1 = 1222
x mod 1621^1 = 771
x mod 1627^1 = 483
x mod 1697^1 = 1437
x mod 2593^1 = 2574
x mod 2671^1 = 1747
x mod 2789^1 = 1548
x mod 2999^2 = 6842798
x mod 3187^1 = 1672
x mod 3853^1 = 134
x mod 4211^1 = 59
x mod 4679^1 = 2800
x mod 5527^1 = 3670
x mod 6317^1 = 82
x mod 6607^1 = 1232
x mod 6703^1 = 311
x mod 7817^1 = 5350
x mod 11399^1 = 2540
x mod 20071^1 = 13679
x mod 30427^1 = 21406
x mod 32909^1 = 13795
x mod 34513^1 = 20358
x mod 42649^1 = 6927
x mod 47807^1 = 11201
x mod 58601^1 = 12520
x mod 71471^1 = 42878
x mod 73681^1 = 39856
x mod 106637^1 = 53124
x mod 178151^1 = 154644
x mod 268063^1 = 211767
x mod 295873^1 = 207170
x mod 312047^1 = 290421
x mod 439613^1 = 190762
x mod 514081^1 = 339549
x mod 641549^1 = 219459

解     x   = 2041573077139379385883783335989187956606084836585302489766568373599
31561541509546270727656605117738720556840189311877860288185970120011789028925233
74893267874989654050121389707441399010664764650400886534648605261537197200485702
20625136078574898993327239857971729159104601869849711543174887629522078167768

検算 : g^x = 2283797796212620461510129423506787330187297414931590604988996829724
09610765298515485289783258542967391349916458517286975320190570042023078678031871
39201629188698841634464208160411458956195499749743024656983055471670281436677916
4120524316436667752164324764779723904098313988588604337167531364078868307589

       y   = 2283797796212620461510129423506787330187297414931590604988996829724
09610765298515485289783258542967391349916458517286975320190570042023078678031871
39201629188698841634464208160411458956195499749743024656983055471670281436677916
4120524316436667752164324764779723904098313988588604337167531364078868307589

計算時間   = 317.111000061