Public-Key
將數字轉換為乘法循環群的成員
我目前正在嘗試為教育目的實施 ElGamal 加密。據我了解，當使用具有乘法循環組的加密時，會為安全私鑰生成一個循環組，如下所示：
- 找到一個安全的素數 $ p $ （形式為 $ p = 2*q + 1 $ 在哪裡 $ q $ 是素數）
- 找到具有順序的循環群的生成器 $ q $ 和模 $ p $ （即一個數字 $ g $ 少於 $ p $ 這樣 $ g^q \mod p = 1 $ 和 $ g^2 \mod p \neq 1 $ )
例如，對於 $ p = 11 $ ，我們會有 $ q = 5 $ , $ g = 3, 4, 5 $ 或者 $ 9 $ , 循環群有元素 { $ 1, 3, 9, 5, 4 $ }.
然後，在加密階段，執行加密的人應該轉換 $ m $ , 消息的數字表示, 成 $ m_1 $ ，該組的成員。如果這是怎麼做的 $ m $ 不屬於我們的組（例如，如果它是 $ 2, 6, 7, 8 $ 或者 $ 10 $ )?
如果我遺漏了什麼，請告訴我我做錯了什麼！
在您的情況下使用勒讓德符號。解釋：當 $ p=2.q+1 $ , 乘法群的階數 $ F_p $ 是 p-1=2q。那麼就沒有其他選擇了，當你選擇一個隨機數時，它可能是一個有機率的二次殘差 $ \frac{1}{2} $ . 任意數 a 的勒讓德符號是： $ a^{\frac{p-1}{2}}=a^{q}=\pm 1 $
那麼除數字 1 外，所有其他二次餘數（Legendre 符號為 1）都具有 q 階。