具體離散對數題
我遇到了一個需要解決的 DL…
5^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587)模數是 124 位數字，所以一般的 Baby Step - Giant Step 需要一些 $ 2^{62} $ 操作，這在家用 PC 上是不可行的。
它有什麼弱點嗎？模數是 2 * 另一個巨大的素數 + 1，所以絕對不平滑（並且容易受到 Pohlig - Hellman 的影響）。
顯然，有些人在幾個小時內就在他們的家用電腦上解決了這個問題……如何？這對我來說似乎是不可能的。
(12:15) gp > p=15860584089531798358308118294328202587; (12:15) gp > y=6361196924231058595008858273263807320; (12:15) gp > x=znlog(Mod(y,p),Mod(5,p)) 11473769387225613271575199155876761324 (12:17) gp > ## *** last result computed in 1min, 26,253 ms. (12:17) gp > Mod(5,p)^x == Mod(y,p) 1 (12:17) gp > firas@wakaba ~ % cat /proc/cpuinfo |grep 'model name' model name : Intel(R) Core(TM) i5-3330 CPU @ 3.00GHz從文件中：
該功能使用
- 通用離散對數算法的組合（見下文）。
- 在 $ (\mathbb Z/N\mathbb Z)^* $ 什麼時候 $ N $ 是素數：一種線性篩指數演算方法，適用於 $ N < 10^{50} $ ，例如，用於順序的大素數除數。
通用離散對數算法是：
- Pohlig-Hellman 算法，簡化為素數組 $ q $ ， 在哪裡 $ q \mid p-1 $ 和 $ p $ 是一個奇數的素數除數 $ N $ ,
- 香克斯嬰兒步/巨人步（ $ q < 2^{32} $ 是小），
- 波拉德 rho 方法 ( $ q > 2^{32} $ ).
岩漿線上計算器給出了以下資訊
$$ I was interested in CPU time after @fkraiem’s answer $$. **TL;DR：**隨機選擇的 200 位可能素數超過了 120 秒的 CPU 時間限制。
程式碼：
x:=6361196924231058595008858273263807320;
p:=15860584089531798358308118294328202587；
F:=GF(p);
b:=F!5; x:=F!x;
“p 是素數嗎？",IsPrime(p);
時間 k:=Log(b,x);
“檢查: b^k = “,F!(b^k),” =?=”, x;
輸出：
p 是素數嗎？真的
時間：3.490
檢查：b^k = 6361196924231058595008858273263807320 =?= 6361196924231058595008858273263807320
計算時間限制為 120 秒。輸入限制為 50000 字節。執行 Magma V2.23-9。種子：2717357355；總時間：3.680秒；總記憶體使用量：32.09MB。
DL 上的 Magma 文件說：
Magma 中不同類型的有限域按如下方式處理（按此順序）：
(a) 小域（任何特徵）：如果除以 q - 1 的最大素數 l 相當小（通常小於 2^36），則使用 Pohlig-Hellman 算法（特徵 p 無關緊要）。
(b) 大素數：假設 K 是素數域（所以 q=p）。然後是高斯整數篩
$$ COS86 $$,$$ LO91a $$如果 p 至少有 4 位但不超過 400 位，則使用 p - 1 不是正方形，並且以下之一是模 p 的二次餘數：-1、-2、-3、-7 或 - 11. 如果不能使用高斯整數篩，如果 p 不超過 300 位，則線性篩
$$ COS86 $$,$$ LO91a $$用來。預計算階段總是發生，並且通常需要比計算單個對數更多的時間（並且對於大欄位可能還需要大量記憶體）。因此，第一次呼叫下面的函式 Log 可能比後續呼叫花費更多的時間。 此外，對於大素數域，與高斯方法相比，線性篩在預計算階段需要比高斯方法更多的時間和記憶體，因此僅在無法使用高斯整數算法時使用。有關基本線性篩算法的解釋以及所採用的稀疏線性代數技術的更多資訊，請參見稀疏矩陣一章中的範例 H27E3。
以此為挑戰，讓我們嘗試 200 位素數（可能的素數）
尋找生成器的第一個預計算：
p = 495998296780695342795805838124611282143307443742260790342431
在 205 次試驗中發現的可能素數 p
組順序 - 這些元素的順序是
$$ 247999148390347671397902919062305641071653721871130395171215, 0, 247999148390347671397902919062305641071653721871130395171215, 0 $$ 在 4 次試驗中發現的發電機
取b=3，即L
$$ 2 $$; 此試驗未達到 CPU 時間限制
注意：我無法訪問正在工作的筆記型電腦來嘗試 Magma 的本地副本。