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

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

素数生成中 ...
素数 p = 29292843985202135446936676566166099707774268591955093324202665411787632
89046811594255789882039786207402924463610619843466003339790288762435905770035889
34844768489839098759213449235205705934433499255668157899046163005145377372515100
65565991276119096435212115638546292937883515208254984166455627324242206003538312
30744913843570938038315430100880502450391905930586827557945761047621084191565243
09817201070505887634714742136758711463000877873515868013153590289380266922074990
45646812183757458567361915029365241058823653896366477289320623223242083527223014
924655743813029986304000000000000000000000000000000001  ( 2008 bits )

p-1 の素因数分解 : [[2, 122], [3, 85], [5, 33], [7, 26], [11, 20], [13, 17], 
[17, 10], [19, 2], [23, 8], [29, 2], [31, 1], [37, 5], [41, 6], [43, 3], [47, 6], 
[53, 4], [59, 2], [61, 4], [67, 1], [71, 3], [73, 1], [79, 2], [83, 5], [89, 3],
[101, 1], [103, 4], [107, 4], [109, 2], [127, 2], [131, 1], [139, 2], [149, 2],
[181, 2], [199, 2], [211, 3], [227, 1], [229, 1], [257, 1], [271, 1], [277, 1],
[311, 1], [337, 2], [347, 2], [349, 1], [359, 2], [379, 1], [389, 1], [401, 2],
[419, 1], [421, 1], [431, 1], [433, 2], [443, 1], [457, 2], [461, 1], [463, 1],
[557, 1], [569, 1], [599, 2], [659, 1], [661, 1], [701, 1], [739, 1], [757, 1],
[797, 1], [821, 1], [859, 1], [883, 1], [907, 1], [919, 2], [941, 1], [953, 1],
[1093, 1], [1097, 1], [1459, 1], [1609, 1], [1721, 1], [1783, 1], [1823, 1], 
[2011, 1], [2161, 1], [2237, 1], [2273, 1], [2311, 1], [2609, 1], [2633, 1], 
[2659, 1], [2711, 1], [2713, 1], [2741, 1], [3041, 1], [3191, 1], [3329, 1], 
[3559, 1], [3583, 1], [3697, 1], [3779, 1], [3821, 1], [3931, 1], [4127, 1], 
[4153, 1], [4259, 2], [4993, 1], [5087, 1], [6043, 1], [6211, 1], [6287, 1], 
[6323, 1], [6659, 1], [6737, 1], [6841, 1], [6911, 1], [6967, 1], [8117, 1], 
[8431, 1], [9857L, 1]]

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

y = 1811160767218469288602855592970566355444087125210070577449860629867867970224
04124108924697363994042514613240682415043048002157370633982174154067960737539856
46738914083569996278434506173274705302785351097108260171281135766141339590959137
94416295883899586286758022616240502227138581755198362148070099759834008565844419
62546313877334703814846366746744980143592697264330024454002048420337798222207886
97274319551976657158327189067833155883893033281033000635108443152438639814413089
22852480091914587445131700106454943404596517810326901773065113002301492539719984
498046123508123555142756816081041615898411407075

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

Pohlig-Hellman 法開始
x mod 2^122 = 1660720825845680675028735750552474498
x mod 3^85 = 9446257953825521657258033626558296744088
x mod 5^33 = 84156328418300207240070
x mod 7^26 = 532837108372978736180
x mod 11^20 = 580750318704901316960
x mod 13^17 = 3106768874423916617
x mod 17^10 = 277122674764
x mod 19^2 = 207
x mod 23^8 = 21876486583
x mod 29^2 = 54
x mod 31^1 = 10
x mod 37^5 = 53176795
x mod 41^6 = 4620878341
x mod 43^3 = 22516
x mod 47^6 = 7073682400
x mod 53^4 = 5055753
x mod 59^2 = 2311
x mod 61^4 = 12989731
x mod 67^1 = 6
x mod 71^3 = 246019
x mod 73^1 = 30
x mod 79^2 = 3903
x mod 83^5 = 3449919772
x mod 89^3 = 66731
x mod 101^1 = 58
x mod 103^4 = 51598179
x mod 107^4 = 111698261
x mod 109^2 = 3569
x mod 127^2 = 15871
x mod 131^1 = 30
x mod 139^2 = 10241
x mod 149^2 = 14982
x mod 181^2 = 7044
x mod 199^2 = 848
x mod 211^3 = 187515
x mod 227^1 = 14
x mod 229^1 = 98
x mod 257^1 = 31
x mod 271^1 = 209
x mod 277^1 = 177
x mod 311^1 = 20
x mod 337^2 = 113430
x mod 347^2 = 64527
x mod 349^1 = 177
x mod 359^2 = 86916
x mod 379^1 = 211
x mod 389^1 = 2
x mod 401^2 = 156525
x mod 419^1 = 369
x mod 421^1 = 170
x mod 431^1 = 400
x mod 433^2 = 59036
x mod 443^1 = 261
x mod 457^2 = 9917
x mod 461^1 = 257
x mod 463^1 = 73
x mod 557^1 = 233
x mod 569^1 = 564
x mod 599^2 = 61621
x mod 659^1 = 488
x mod 661^1 = 504
x mod 701^1 = 362
x mod 739^1 = 191
x mod 757^1 = 403
x mod 797^1 = 249
x mod 821^1 = 239
x mod 859^1 = 314
x mod 883^1 = 156
x mod 907^1 = 895
x mod 919^2 = 667636
x mod 941^1 = 746
x mod 953^1 = 78
x mod 1093^1 = 491
x mod 1097^1 = 1019
x mod 1459^1 = 1108
x mod 1609^1 = 1438
x mod 1721^1 = 896
x mod 1783^1 = 1212
x mod 1823^1 = 701
x mod 2011^1 = 1101
x mod 2161^1 = 40
x mod 2237^1 = 1490
x mod 2273^1 = 1173
x mod 2311^1 = 2273
x mod 2609^1 = 2470
x mod 2633^1 = 213
x mod 2659^1 = 1309
x mod 2711^1 = 1143
x mod 2713^1 = 2091
x mod 2741^1 = 1170
x mod 3041^1 = 1449
x mod 3191^1 = 427
x mod 3329^1 = 2246
x mod 3559^1 = 2587
x mod 3583^1 = 3280
x mod 3697^1 = 1052
x mod 3779^1 = 2049
x mod 3821^1 = 1914
x mod 3931^1 = 1484
x mod 4127^1 = 3299
x mod 4153^1 = 810
x mod 4259^2 = 8865836
x mod 4993^1 = 2341
x mod 5087^1 = 1637
x mod 6043^1 = 328
x mod 6211^1 = 2573
x mod 6287^1 = 5856
x mod 6323^1 = 995
x mod 6659^1 = 1236
x mod 6737^1 = 2133
x mod 6841^1 = 2598
x mod 6911^1 = 5928
x mod 6967^1 = 6506
x mod 8117^1 = 2860
x mod 8431^1 = 8075
x mod 9857^1 = 9259

解     x   = 1717805909495300111996969050286774816031984392948020613717970728629
97821026177737787737214104090459373064985473346860701559104796705271370579674035
90435321736467951211441163087064722858340495809771924333105226004475082616815320
66321634607036891959000663755474848019920320625155262771671249560249774470944299
85279040157364752897760325300355784306075412580087470858514458084501891777689014
78318423412874459490161573764484025971431693036729908721179859848985424487697027
17931161720274951519577643369913803815411516870389569948246037262991334322414814
1118885413318128400407441703321063509548240878627355677570

検算 : g^x = 1811160767218469288602855592970566355444087125210070577449860629867
86797022404124108924697363994042514613240682415043048002157370633982174154067960
73753985646738914083569996278434506173274705302785351097108260171281135766141339
59095913794416295883899586286758022616240502227138581755198362148070099759834008
56584441962546313877334703814846366746744980143592697264330024454002048420337798
22220788697274319551976657158327189067833155883893033281033000635108443152438639
81441308922852480091914587445131700106454943404596517810326901773065113002301492
539719984498046123508123555142756816081041615898411407075

       y   = 1811160767218469288602855592970566355444087125210070577449860629867
86797022404124108924697363994042514613240682415043048002157370633982174154067960
73753985646738914083569996278434506173274705302785351097108260171281135766141339
59095913794416295883899586286758022616240502227138581755198362148070099759834008
56584441962546313877334703814846366746744980143592697264330024454002048420337798
22220788697274319551976657158327189067833155883893033281033000635108443152438639
81441308922852480091914587445131700106454943404596517810326901773065113002301492
539719984498046123508123555142756816081041615898411407075

計算時間   = 592.372999907