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

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

素数生成中 ...
素数 p = 93203420993881600280184235766121541478396574966599767008138981439997771
98456756457993974874869118401964670770455085124098896200487927600074870426591673
28450820716041585437726089583268386696588706152403251957902750743984032688914152
289351385426227677865089554872520526035571044295639040000000000000000001  
( 1007 bits )

p-1 の素因数分解 : [[2, 94], [3, 46], [5, 19], [7, 11], [11, 4], [13, 6], [17, 2], 
[19, 8], [23, 7], [29, 4], [31, 3], [37, 3], [41, 2], [43, 1], [47, 2], [59,1], 
[61, 1], [67, 1], [71, 1], [79, 1], [83, 2], [89, 3], [97, 1], [101, 1], [109, 1], 
[151, 1], [167, 1], [179, 1], [193, 1], [199, 2], [223, 1], [251, 1], [271, 2], 
[283, 1], [293, 1], [313, 3], [359, 1], [409, 1], [463, 1], [467, 1], [487, 1], 
[499, 1], [569, 2], [601, 1], [661, 1], [733, 1], [757, 1], [829, 1], [863, 1], 
[953, 1], [1019, 1], [1061, 1], [1063, 1], [1471, 2], [1993, 1], [2083, 1], 
[2371, 1], [2411, 1], [2557, 1], [2609, 1], [2663, 1], [2711, 1], [2897, 1],
[3089, 1], [4027, 1], [4481, 1], [4931, 1], [5791, 1], [6373, 1], [8819L, 1]]

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

y = 8677171914028598594403766801510802722942866578197645161159906986260088428999
65712966303591194197930946800351340932620882147620121840671684787854074311681601
86642380471851299502728342044144458964061337928338441375581013128935654084121850
8060561562953920169835031931607310705841770211899551600970600142321

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

Pohlig-Hellman 法開始
x mod 2^94 = 4109834600596466119371720942
x mod 3^46 = 8268130701969783610326
x mod 5^19 = 2203460717314
x mod 7^11 = 117693604
x mod 11^4 = 8967
x mod 13^6 = 1735828
x mod 17^2 = 23
x mod 19^8 = 2500670695
x mod 23^7 = 423691943
x mod 29^4 = 389641
x mod 31^3 = 15561
x mod 37^3 = 15246
x mod 41^2 = 991
x mod 43^1 = 38
x mod 47^2 = 767
x mod 59^1 = 25
x mod 61^1 = 13
x mod 67^1 = 2
x mod 71^1 = 46
x mod 79^1 = 40
x mod 83^2 = 2932
x mod 89^3 = 314119
x mod 97^1 = 25
x mod 101^1 = 90
x mod 109^1 = 54
x mod 151^1 = 144
x mod 167^1 = 133
x mod 179^1 = 116
x mod 193^1 = 51
x mod 199^2 = 8120
x mod 223^1 = 137
x mod 251^1 = 121
x mod 271^2 = 63174
x mod 283^1 = 85
x mod 293^1 = 98
x mod 313^3 = 1783822
x mod 359^1 = 10
x mod 409^1 = 401
x mod 463^1 = 233
x mod 467^1 = 126
x mod 487^1 = 125
x mod 499^1 = 107
x mod 569^2 = 142033
x mod 601^1 = 319
x mod 661^1 = 325
x mod 733^1 = 585
x mod 757^1 = 586
x mod 829^1 = 729
x mod 863^1 = 351
x mod 953^1 = 138
x mod 1019^1 = 537
x mod 1061^1 = 632
x mod 1063^1 = 284
x mod 1471^2 = 2028134
x mod 1993^1 = 34
x mod 2083^1 = 1820
x mod 2371^1 = 1209
x mod 2411^1 = 760
x mod 2557^1 = 1810
x mod 2609^1 = 539
x mod 2663^1 = 2624
x mod 2711^1 = 2343
x mod 2897^1 = 2471
x mod 3089^1 = 1147
x mod 4027^1 = 3672
x mod 4481^1 = 214
x mod 4931^1 = 4414
x mod 5791^1 = 1671
x mod 6373^1 = 4908
x mod 8819^1 = 7119

解     x   = 2844035998153805031161300074142781165277186936603497753837772937109
19043187681670735722174528592613741378840578017294285697639541925214725314711906
90857308567627848782197890802124000849518085060371462129092583847291868492306560
7657278482817436514608934429783730699600449775642716707356857225714202904814

検算 : g^x = 8677171914028598594403766801510802722942866578197645161159906986260
08842899965712966303591194197930946800351340932620882147620121840671684787854074
31168160186642380471851299502728342044144458964061337928338441375581013128935654
0841218508060561562953920169835031931607310705841770211899551600970600142321

       y   = 8677171914028598594403766801510802722942866578197645161159906986260
08842899965712966303591194197930946800351340932620882147620121840671684787854074
31168160186642380471851299502728342044144458964061337928338441375581013128935654
0841218508060561562953920169835031931607310705841770211899551600970600142321

計算時間   = 55.0799999237

単純検索開始（たぶん宇宙が終わるまで答えは出ない）