参考
実行例
幾つまでの素数を小さいと考えますか ( 100 以上 ) : 1000
素数 p のビット数を指定してください ( 10 以上 ) : 1024
素数生成中 ...
素数 p = 2258968316115259531236612710706864812801625388363886419505487896413704583382991502282273274396238423791479079706354652138857156035724251041017314131706386506243212885895864440421288806441673565124738377440599931624404714724436345388982983221338004707455459667648391257564119040000000000000000000000000000000001 ( 1028 bits )
p-1 の素因数分解 : [[2, 103], [3, 44], [5, 34], [7, 23], [11, 9], [13, 5], [17, 7], [19, 9], [23, 2], [29, 4], [31, 8], [37, 2], [41, 4], [43, 3], [47, 2], [59, 4], [61, 1], [67, 2], [71, 2], [73, 3], [79, 3], [83, 3], [89, 2], [97, 2], [103, 2], [107, 1], [109, 1], [137, 3], [139, 1], [149, 1], [151, 1], [157, 1], [191, 2], [193, 1], [197, 1], [211, 1], [251, 1], [277, 1], [283, 1], [311, 1], [313, 1], [397, 2], [431, 1], [443, 1], [467, 2], [487, 1], [547, 1], [571, 1], [577, 1], [613, 1], [673, 1], [701, 1], [709, 1], [733, 1], [823, 1], [829, 1], [877, 1], [911, 1]]
原始根計算中 ...
法 p の原始根 g = 159
y = 1943412200448161918272568217533643089770088552943561076336928801170280559986331456354647684839103722023539802628445305860905081943843100543472541651688514044940541280534877898440948956393472313659302626371316904753224162963024582322222499495423165610101288208763360644310367191450243764378192801308195283457103
離散対数 x = log_g(y) を求める
Pohlig-Hellman 法開始
x mod 2^103 = 5546254845206667923759569927658
x mod 3^44 = 623422219145647624879
x mod 5^34 = 297568777965974945791837
x mod 7^23 = 9869616109269471215
x mod 11^9 = 399376899
x mod 13^5 = 278834
x mod 17^7 = 23314227
x mod 19^9 = 168405771692
x mod 23^2 = 53
x mod 29^4 = 565123
x mod 31^8 = 4133224832
x mod 37^2 = 437
x mod 41^4 = 1365962
x mod 43^3 = 12125
x mod 47^2 = 2074
x mod 59^4 = 11326329
x mod 61^1 = 40
x mod 67^2 = 1014
x mod 71^2 = 1521
x mod 73^3 = 57437
x mod 79^3 = 181408
x mod 83^3 = 56253
x mod 89^2 = 1329
x mod 97^2 = 4278
x mod 103^2 = 5556
x mod 107^1 = 1
x mod 109^1 = 21
x mod 137^3 = 404201
x mod 139^1 = 34
x mod 149^1 = 128
x mod 151^1 = 33
x mod 157^1 = 121
x mod 191^2 = 14224
x mod 193^1 = 104
x mod 197^1 = 123
x mod 211^1 = 35
x mod 251^1 = 161
x mod 277^1 = 139
x mod 283^1 = 233
x mod 311^1 = 303
x mod 313^1 = 167
x mod 397^2 = 109496
x mod 431^1 = 143
x mod 443^1 = 209
x mod 467^2 = 55302
x mod 487^1 = 110
x mod 547^1 = 418
x mod 571^1 = 509
x mod 577^1 = 383
x mod 613^1 = 405
x mod 673^1 = 152
x mod 701^1 = 672
x mod 709^1 = 447
x mod 733^1 = 550
x mod 823^1 = 331
x mod 829^1 = 791
x mod 877^1 = 756
x mod 911^1 = 383
解 x = 282945460895527248767774214278626004388782417161647738940816527628105549780903800388503639268434179365851215172611796975330277345628219402987915858847886590202863615333843354922913148900588899813039393526360685247918722028252311161290922503287073025949555047784437168071142090421783191565901080536317963369962
検算 : g^x = 1943412200448161918272568217533643089770088552943561076336928801170280559986331456354647684839103722023539802628445305860905081943843100543472541651688514044940541280534877898440948956393472313659302626371316904753224162963024582322222499495423165610101288208763360644310367191450243764378192801308195283457103
y = 1943412200448161918272568217533643089770088552943561076336928801170280559986331456354647684839103722023539802628445305860905081943843100543472541651688514044940541280534877898440948956393472313659302626371316904753224162963024582322222499495423165610101288208763360644310367191450243764378192801308195283457103
計算時間 = 5.345960378646851