[Cryptography] 數論相關筆記-Quadratic equations mod p

最後，綜合上面幾篇的概念，來解二元一次方程式的難題。題目是：

x² + 4x + 1 = 0 in Z₂₃

首先，我們要先求得(2a)^-1 in Z_p是多少。

(2a)^-1 = (2*1)^-1 = 2^-1 in Z₂₃

這問題相當於在問，2與23互質，其2-1就是用Extended Eculid algorithm所得到的係數。跑這篇的python演算法可以得到其值為

2^-1 = -11

再來，要計算麻煩的開根號。

(b²-4*a*c)^(1/2) in Z₂₃ = (4²-4*1*1)^(1/2) in Z₂₃ = 12^(1/2) in Z₂₃

這問題要從Modular e'th Roots來下手。

投影片提到一個很重要的性質，也就是

c^(1/2) = c^(p+1)/4 in Z_p

所以開根號就變成

12^(1/2) in Z₂₃ =12^(23+1)/4 in Z₂₃ = 12⁶ in Z₂₃ = 9 in Z₂₃

代回方程式，得到

2^-1*(-4±12⁶) in Z₂₃ = -11*(-4±9) in Z₂₃ = -11*(-13, 5) in Z₂₃ = 143, -55 in Z₂₃ = 5, 14 in Z₂₃

歷經千辛萬苦，可以計算答案為5, 14。