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

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

素数生成中 ...
素数 p = 72231549405628275285316965647563360482090656089018896247667777267185508
43037572158602793448473012545698048130007778213138461079409737878626815400190700
80526734649592396932444725170816332494449116815904013777855534721432733117199591
25204559707009180016933129377692845770157251678037746482138031819438286386239173
72984500667279994161630495533772238629848788286858352777706078955927876044367887
70274892629259903038164326977646710060679722794418600151901489133302710701634750
05594065241471029607601887929789344731028608880793142473863646955661630036341680
9045670089460370700305896466022400000000000000000000001  ( 2013 bits )

p-1 の素因数分解 : [[2, 76], [3, 62], [5, 23], [7, 9], [11, 11], [13, 6], [17, 10], 
[19, 6], [29, 3], [31, 2], [37, 6], [41, 5], [43, 1], [47, 5], [53, 6], [71, 1], 
[73, 1], [79, 2], [83, 1], [103, 1], [127, 1], [131, 1], [137, 1], [149, 1], 
[151, 3], [157, 1], [167, 2], [179, 2], [181, 1], [199, 1], [227, 3], [229, 3], 
[233, 1], [239, 1], [251, 1], [263, 1], [269, 1], [271, 1], [277, 1], [307, 1], 
[331, 2], [349, 2], [353, 1], [359, 1], [397, 1], [433, 1], [439, 1], [443, 1], 
[461, 1], [463, 1], [479, 1], [499, 1], [613, 1], [641, 2], [647, 1], [751, 1], 
[863, 1], [881, 1], [907, 1], [947, 2], [1061, 2], [1231, 1], [1237, 1], [1511, 1], 
[1877, 1], [1879, 1], [2017, 1], [2099, 1], [2111, 1], [2341, 1], [3023, 1], 
[3041, 1], [3643, 1], [3793, 1], [3881, 1], [3923, 1], [4493, 1], [4567, 1],
[4799, 1], [5281, 1], [5659, 1], [7411, 1], [9661, 1], [9749, 1], [9781, 1], 
[9839, 1], [10069, 1], [10687, 1], [10957, 1], [12433, 1], [12619, 1], [13723, 1],
[15991, 1], [16487, 1], [17383, 1], [18701, 1], [19289, 1], [19489, 1], [20593, 1], 
[21487, 1], [22051, 1], [23081, 1], [29101, 1], [34871, 1], [38959, 1], [43411, 1], 
[43543, 1], [48799, 1], [48821, 1], [62383, 1], [66919, 1], [71993, 1], [80251, 1], 
[93307, 1], [96259, 1], [99823, 1], [101293, 1], [113017, 1], [136273, 1], 
[171937, 1], [218527, 1], [235241, 1], [257311, 1], [283631, 1], [352249, 1], 
[532811, 1], [535849, 1], [652373, 1], [766127, 1], [875027L, 1]]

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

y = 3230798201502894120753929753194907137635416317755743499302270707328984221999
48894520964156308654383191231521143301095128781373729360158291715910453022153091
16462898579161368133789315748354444202321683921174083829023559985268164020491487
10975345101470719079253545652580396349845145945937022106444768368764281837367163
72676718185866203038046429357125855323843011157253758109338623211907066564664917
69781509112160725107411086270993942318241812588866622097771928777744171835999376
92121974815481475549535942786817200063646410776593402170726171903785310048211330
71302748303984934618392345468981892755823639551104

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

Pohlig-Hellman 法開始
x mod 2^76 = 44899623981179713561111
x mod 3^62 = 187339652469407807200913103718
x mod 5^23 = 8100564885389452
x mod 7^9 = 4472287
x mod 11^11 = 50251844417
x mod 13^6 = 3960096
x mod 17^10 = 768953746426
x mod 19^6 = 10349321
x mod 29^3 = 501
x mod 31^2 = 669
x mod 37^6 = 2145137042
x mod 41^5 = 45626752
x mod 43^1 = 7
x mod 47^5 = 182939423
x mod 53^6 = 446652395
x mod 71^1 = 57
x mod 73^1 = 45
x mod 79^2 = 194
x mod 83^1 = 29
x mod 103^1 = 59
x mod 127^1 = 90
x mod 131^1 = 60
x mod 137^1 = 31
x mod 149^1 = 1
x mod 151^3 = 1562235
x mod 157^1 = 153
x mod 167^2 = 24038
x mod 179^2 = 31154
x mod 181^1 = 170
x mod 199^1 = 96
x mod 227^3 = 10141034
x mod 229^3 = 9840703
x mod 233^1 = 149
x mod 239^1 = 140
x mod 251^1 = 220
x mod 263^1 = 50
x mod 269^1 = 170
x mod 271^1 = 53
x mod 277^1 = 273
x mod 307^1 = 47
x mod 331^2 = 4233
x mod 349^2 = 61121
x mod 353^1 = 313
x mod 359^1 = 47
x mod 397^1 = 104
x mod 433^1 = 186
x mod 439^1 = 166
x mod 443^1 = 216
x mod 461^1 = 281
x mod 463^1 = 187
x mod 479^1 = 171
x mod 499^1 = 185
x mod 613^1 = 387
x mod 641^2 = 280050
x mod 647^1 = 378
x mod 751^1 = 193
x mod 863^1 = 673
x mod 881^1 = 217
x mod 907^1 = 157
x mod 947^2 = 653966
x mod 1061^2 = 392834
x mod 1231^1 = 239
x mod 1237^1 = 707
x mod 1511^1 = 1289
x mod 1877^1 = 698
x mod 1879^1 = 1060
x mod 2017^1 = 704
x mod 2099^1 = 468
x mod 2111^1 = 1050
x mod 2341^1 = 356
x mod 3023^1 = 738
x mod 3041^1 = 1983
x mod 3643^1 = 3018
x mod 3793^1 = 2958
x mod 3881^1 = 1612
x mod 3923^1 = 2408
x mod 4493^1 = 3473
x mod 4567^1 = 2662
x mod 4799^1 = 4460
x mod 5281^1 = 3081
x mod 5659^1 = 1581
x mod 7411^1 = 3936
x mod 9661^1 = 1591
x mod 9749^1 = 9400
x mod 9781^1 = 6407
x mod 9839^1 = 808
x mod 10069^1 = 8168
x mod 10687^1 = 7834
x mod 10957^1 = 6629
x mod 12433^1 = 8486
x mod 12619^1 = 10671
x mod 13723^1 = 2065
x mod 15991^1 = 14023
x mod 16487^1 = 2601
x mod 17383^1 = 1541
x mod 18701^1 = 3117
x mod 19289^1 = 6318
x mod 19489^1 = 17828
x mod 20593^1 = 9992
x mod 21487^1 = 5265
x mod 22051^1 = 13450
x mod 23081^1 = 18373
x mod 29101^1 = 7329
x mod 34871^1 = 29390
x mod 38959^1 = 34036
x mod 43411^1 = 34600
x mod 43543^1 = 36406
x mod 48799^1 = 38477
x mod 48821^1 = 22575
x mod 62383^1 = 11723
x mod 66919^1 = 38230
x mod 71993^1 = 31935
x mod 80251^1 = 42205
x mod 93307^1 = 11183
x mod 96259^1 = 55945
x mod 99823^1 = 84269
x mod 101293^1 = 5878
x mod 113017^1 = 616
x mod 136273^1 = 42424
x mod 171937^1 = 81897
x mod 218527^1 = 139364
x mod 235241^1 = 77418
x mod 257311^1 = 138558
x mod 283631^1 = 105275
x mod 352249^1 = 311961
x mod 532811^1 = 223951
x mod 535849^1 = 514499
x mod 652373^1 = 271607
x mod 766127^1 = 232222
x mod 875027^1 = 637193

解     x   = 4740201353437089780381628413696206102652258109237159542734592041891
68082792319991797990956433238415334098767350716910049647051855559336504962308201
01667183951456985673322448393883313834869594198417819753530520411367738113794823
93146314197530819363970639513022191603674185261636297029613015638801032782224328
27482198964907905439191247010271335767719996290608101318672034271269583461570104
81022155774003272085621209330812957387528072971450062869206243183430988837265230
19465431284458441158450390485901239761365816217311479636110136339037784445921713
04732936435814148867766161561730735277265449518258977186327

検算 : g^x = 3230798201502894120753929753194907137635416317755743499302270707328
98422199948894520964156308654383191231521143301095128781373729360158291715910453
02215309116462898579161368133789315748354444202321683921174083829023559985268164
02049148710975345101470719079253545652580396349845145945937022106444768368764281
83736716372676718185866203038046429357125855323843011157253758109338623211907066
56466491769781509112160725107411086270993942318241812588866622097771928777744171
83599937692121974815481475549535942786817200063646410776593402170726171903785310
04821133071302748303984934618392345468981892755823639551104

       y   = 3230798201502894120753929753194907137635416317755743499302270707328
98422199948894520964156308654383191231521143301095128781373729360158291715910453
02215309116462898579161368133789315748354444202321683921174083829023559985268164
02049148710975345101470719079253545652580396349845145945937022106444768368764281
83736716372676718185866203038046429357125855323843011157253758109338623211907066
56466491769781509112160725107411086270993942318241812588866622097771928777744171
83599937692121974815481475549535942786817200063646410776593402170726171903785310
04821133071302748303984934618392345468981892755823639551104

計算時間   = 2390.88599992