平方剩余、二次互反律

一、平方剩余

1. 定義：設 p 為奇素數且 \(\mathsf{a \neq 0\ mod\ p}\) ，如果 a 在模 p 下是另一個數的平方，即 \(\mathsf{a \equiv b^{2}\ mod\ p}\) ，則稱 a 為模 p 下的平方剩余，否則稱 a 為平方非剩余，而二次同余式 \(\mathsf{x^{2}\equiv a\ mod\ p}\) 可能有 0—2 個解

• 例子：

  \(\mathsf{p=5}\) 時，因為

  \(\mathsf{1^{2}\equiv 1\ mod\ 5 \qquad 2^{2}\equiv 4\ mod\ 5 \qquad 3^{2}\equiv 4\ mod\ 5 \qquad 4^{2}\equiv 1\ mod\ 5}\)

  則 1，4 是模 5 下的平方剩余，而 2，3 是模 5 下的平方非剩余

  \(\mathsf{p=7}\) 時，因為

  \(\mathsf{1^{2}\equiv 1\ mod\ 7 \qquad 2^{2}\equiv 4\ mod\ 7 \qquad 3^{2}\equiv 2\ mod\ 7 \qquad 4^{2}\equiv 2\ mod\ 7 \qquad 5^{2}\equiv 4\ mod\ 7 \qquad 6^{2}\equiv 1\ mod\ 7}\)

  則 1，2，4 為模 7 下的平方剩余，而 3，5，6 是模 7 下的平方非剩余

1. 引理：令 \(\mathsf{a\neq0\ mod\ p}\) ，如果 \(\mathsf{a^{\frac{p-1}{2}}\equiv1\ mod\ p}\) ，則 a 是模 p 下的平方剩余

• 例子：

  15 是模 17 下的平方剩余，因為 \(\mathsf{15^{\frac{17-1}{2}}\equiv 1\ mod\ 17}\)

  12 是模 17 下的平方非剩余，因為 \(\mathsf{12^{\frac{17-1}{2}}\equiv -1\ mod\ 17}\)

• 證明：

  p 是奇數，所以根據歐拉定理：\(\mathsf{a^{p-1}\equiv 1\ mod\ p \qquad (a^{\frac{p-1}{2}})^{2}\equiv 1\ mod\ p \qquad a^{\frac{p-1}{2}}\equiv \pm1\ mod\ p}\)

  設 g 為模 p 下的原根，則 \(\mathsf{\{1,\ g,\ g^{2},\ \cdots,\ g^{p-2}\}=1,\ 2,\ \cdots,\ p-1\ mod\ p}\)

  對應某些 k ，設 \(\mathsf{a \equiv g^{k}\ mod\ p}\) ，所以 \(\mathsf{a \equiv g^{k+(p-1)m}\ mod\ p}\)

  當 k 是偶數時，a 是模 p 下的平方剩余

  如果 \(\mathsf{k=2l}\) ，那么 \(\mathsf{a \equiv g^{2l} \equiv (g^{l})^{2}}\)

  相反，如果\(\mathsf{a \equiv b^{2}\ mod\ p}\) 并且假設 \(\mathsf{b=g^{l}\ mod\ p}\) ，那么 \(\mathsf{a \equiv g^{2l}\ mod\ p}\) ，所以 k 是偶數，

1. 注：在模 p 的剩余系統當中，有一半的數是平方剩余，另一半是平方非剩余，

二、Legendre 符號

1. 定義：\(\mathsf{(\frac{a}{p})= \begin{cases}1 \qquad a\ 是\ mod\ p\ 的平方剩余 \\ -1 \qquad a\ 是\ mod\ p\ 的平方非剩余 \\ 0 \qquad a\ 為\ p\ 等整數倍 \end{cases} \qquad}\)，也可寫作 \(\mathsf{(a \mid p)}\) ，滿足 \(\mathsf{(\frac{a}{p})=a^{\frac{p-1}{2}}\ mod\ p}\) ，
2. 定理：\(\mathsf{(a \mid p)(b \mid p)=(ab \mid p)}\)

• 證明：

  \(\mathsf{a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv (ab)^{\frac{p-1}{2}}\ mod\ p \qquad (a^{2} \mid p)=(a \mid p)^{2}=1}\)

• 例子：

  \(\mathsf{(-9 \mid 71)=(-1 \times 3^{2} \mid 71)=(-1 \mid 71)(3^{2} \mid 71)=(-1 \mid 71)=(-1)^{35}\ mod\ 71=-1}\)

  \(\mathsf{(-9 \mid 53)=(-1 \times 3^{2} \mid 53)=(-1 \mid 53)(3^{2} \mid 53)=(-1 \mid 53)=(-1)^{26}\ mod\ 53=1}\)

三、高斯引理

1. 高斯引理：設 p 為奇素數并且 \(\mathsf{a \neq 0\ mod\ p}\) ，對于任意整數 x ，令 \(\mathsf{x_{p}}\) 為模 p 下關于 x 的同余，且具有最小的絕對值，將 x 除以 p ，余數為 b ，則 \(\mathsf{0 \leq b < p}\) ，如果 \(\mathsf{b<\frac{p}{2}}\) ，令 \(\mathsf{x_{p}=b}\) ，如果 \(\mathsf{b> \frac{p}{2}}\) ，令 \(\mathsf{x_{p}=b-p}\) ，則 \(\mathsf{-p/2 < x_{p} < p/2}\) ，令 n 為 \(\mathsf{(a)_{p},\ (2a)_{p},\ (3a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}}\) 中負數的個數，則 \(\mathsf{(a \mid p)=(-1)^{n}}\)

• 例子：

  \(\mathsf{p=13 \qquad a=5 \qquad \{a,\ 2a,\ \cdots,\ (\frac{p-1}{2})a\}=\{5,\ 10,\ 15,\ 20,\ 25,\ 30 \}}\)

  \(\mathsf{\{(a)_{p},\ (2a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}\}=\{5,\ -3,\ 2,\ -6,\ -1,\ 4\}}\)

  其中有 3 個負數，所以 \(\mathsf{(5 \mid 13)=(-1)^{3}=-1}\)

  \(\mathsf{p=13 \qquad a=10 \qquad \{a,\ 2a,\ \cdots,\ (\frac{p-1}{2})a\}=\{10,\ 20,\ 30,\ 40,\ 50,\ 60\}}\)

  \(\mathsf{\{(a)_{p},\ (2a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}\}=\{-3,\ -6,\ 4,\ 1,\ -2,\ -5\}}\)

  其中有 4 個負數，所以 \(\mathsf{(10 \mid 13)=(-1)^{4}=1}\)

• 證明：

  首先證明：如果 \(\mathsf{1 \leq k \neq l \leq (p-1)/2}\) ，那么 \(\mathsf{(ka)_{p} \neq \pm (la)_{p}}\)

  假設 \(\mathsf{(ka)_{p}= \pm(la)_{p}}\) 不正確，那么有 \(\mathsf{ka \equiv \pm\ la\ mod\ p \Rightarrow (k \pm l)a \equiv 0\ mod\ p \Rightarrow k \pm l \equiv 0\ mod\ p}\)

  這是不可能的，因為 \(\mathsf{2 \leq k+l \leq p-1\ ,\ -p/2 < k-l < p/2\ ,\ k-l \neq 0}\)

  所以在模 p 下數 \(\mathsf{\mid (ka)_{p} \mid\ \qquad k=1,\ 2,\ \cdots,\ \frac{p-1}{2}}\) 全部是不同的 (它們有 \(\mathsf{\frac{p-1}{2}}\) 個) 并且必須是整數 \(\mathsf{\{1,\ 2,\ \cdots,\ \frac{p-1}{2} \}}\) 且按照某種順序排列，

  \(\mathsf{1 \cdot 2 \cdots(\frac{p-1}{2})\equiv \prod\limits_{k=1}^{\frac{p-1}{2}}\mid (ka)_{p} \mid\ mod\ p}\) ，恰好是 n 個數字 \(\mathsf{(ka)_{p}<0}\) 則 \(\mathsf{\equiv(-1)^{n}\prod\limits_{k=1}^{\frac{p-1}{2}}(ka)_{p}\ mod\ p}\)

  \(\mathsf{\equiv (-1)^{n} \prod\limits_{k=1}^{\frac{p-1}{2}}ka\ mod\ p \equiv a^{\frac{p-1}{2}}(-1)^{n}(1\cdot 2 \cdots (\frac{p-1}{2}))\ mod\ p}\)

  \(\mathsf{\Rightarrow 1 \equiv a^{\frac{p-1}{2}}(-1)^{n}\ mod\ p \quad \Rightarrow \quad a^{\frac{p-1}{2}}\equiv (-1)^{n}\ mod\ p \quad \Rightarrow \quad (a \mid p)\equiv (-1)^{n}\ mod\ p}\)

1. 定理：如果 p 為奇素數且 \(\mathsf{gcd(a,\ p)=1}\) ，如果 a 是奇數，\(\mathsf{(a \mid p)=(-1)^{t}}\) 且 \(\mathsf{t=\sum\limits_{j=1}^{\frac{p-1}{2}} \lfloor \frac{ja}{p} \rfloor}\) 且 \(\mathsf{(a \mid p)=(-1)^{\frac{(p^{2}-1)}{8}}}\)

• 證明：

  使用高斯引理，主要關注 \(\mathsf{(-1)^{n}}\) 或 \(\mathsf{n\ mod\ 2}\) 的情況，

  對于 1 到 \(\mathsf{\frac{p-1}{2}}\) 之間的每個數 k ，\(\mathsf{ka=p\lfloor \frac{ka}{p} \rfloor +ka\ mod\ p}\)

  \(\mathsf{ka=p \lfloor \frac{ka}{p} \rfloor +(ka)_{p}+ \begin{cases}0 \qquad 如果 (ka)_{p}>0 \\p \qquad 如果 (ka)_{p}<0 \end{cases}}\)

  \(\mathsf{ka= \lfloor \frac{ka}{p} \rfloor + \mid (ka)_{p} \mid + \begin{cases}0 \qquad 如果 (ka)_{p}>0 \\1 \qquad 如果 (ka)_{p}<0 \end{cases}\ mod\ 2}\)

  \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}ka \equiv \sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor+\sum\limits_{k=1}^{\frac{p-1}{2}}\mid(ka)_{p}\mid+n\ (mod\ 2)}\)

  \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}ka=a\sum\limits_{k=1}^{\frac{p-1}{2}}k=\frac{a}{2}(\frac{p-1}{2})(\frac{p-1}{2}+1)=\frac{a(p^{2}-1)}{8}}\)

  由于 \(\mathsf{\{\mid a\mid_{p},\ \cdots,\ \mid \frac{p-1}{2} a \mid _{p}\}}\) 是 \(\mathsf{\{1,\ \cdots,\ \frac{p-1}{2} \}}\)

  \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}\mid (ka)_{p} \mid = \sum\limits_{k=1}^{\frac{p-1}{2}}k=\frac{1}{2}(\frac{p-1}{2})(\frac{p-1}{2}+1)=\frac{(p^{2}-1)}{8}}\)

  所以，\(\mathsf{n\equiv \frac{a(p^{2}-1)}{8}-\frac{p^{2}-1}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor\ (mod\ 2)}\)

  \(\mathsf{n\equiv \frac{(a-1)(p^{2}-1)}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}}\lfloor \frac{ka}{p} \rfloor\ mod\ 2}\)

  \(\mathsf{n\equiv \sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor \equiv t\ mod\ 2}\)

  由于 a 是奇數，所以 \(\mathsf{(a\mid p)=(-1)^{t}}\)

  如果 \(\mathsf{a=2}\) ，\(\mathsf{n\equiv \frac{(p^{2}-1)}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{2k}{p} \rfloor\ mod\ 2 \qquad k \in \{1,\ 2,\ \cdots,\ \frac{p-1}{2}\}}\)

  所以 \(\mathsf{\lfloor \frac{2k}{p} \rfloor=0}\) ，則 \(\mathsf{n \equiv \frac{(p^{2}-1)}{8}\ mod\ 2}\) ，也就是說：

  \(\mathsf{(2 \mid p)=(-1)^{(p^{2}-1)/8}=\begin{cases}1 \qquad 如果\ p=1,7\ mod\ 8 \\-1 \qquad 如果\ p=3,5\ mod\ 8 \end{cases}}\)

  \(\mathsf{(-1 \mid p)=(-1)^{\frac{p-1}{2}}= \begin{cases}1 \qquad 如果\ p=1\ mod\ 4 \\-1 \qquad 如果\ p=3\ mod\ 4 \end{cases}}\)

四、二次互反律

1. 定理 (二次互反律)：如果 p，q 是不同的奇素數，那么 \(\mathsf{(\frac{p}{q})(\frac{q}{p})=(-1)^{(\frac{p-1}{2})(\frac{q-1}{2})}}\) ，或其他版本：\(\mathsf{(\frac{p}{q})=\begin{cases}+(\frac{q}{p}) \qquad 如果\ p\equiv 1\ mod\ 4\ 或者\ q \equiv 1\ mod\ 4 \\-(\frac{q}{p}) \qquad 如果\ p\equiv q \equiv 3\ mod\ 4 \end{cases}}\)

• 例子：

  \(\mathsf{(\frac{37}{73}) \leftarrow (\frac{73}{37}) \leftarrow (\frac{-1}{37})}\)

  \(\mathsf{(7 \mid 11)=-(11 \mid 7)=-(4 \mid 7)=-1}\)

  \(\mathsf{(10 \mid 13)=(2 \mid 13)(5 \mid 13)=(-1)(13 \mid 5)=-(3 \mid 5)=-(5 \mid 3)=-(2 \mid 3)=-(-1)=1}\)

  \(\mathsf{p=11,\ x=\pm 1,\ \pm2,\ \pm3,\ \pm4,\ \pm5,\ \Rightarrow x^{2}=1,\ 3,\ 4,\ 5,\ 9}\)

  \(\mathsf{p=13,\ x=\pm1,\ \pm2,\ \pm3,\ \pm4,\ \pm,5\ \pm6 \Rightarrow x^{2}=1,\ 3,\ 4,\ 9,\ 10,\ 12}\)

1. 雅克比符號(n 不一定只是奇素數)：對于任意整數 a 和任意正奇數 n ，雅克比符號被定義為對應于 n 的素因子的 Legendre 符號的乘積，即：\(\mathsf{(\frac{a}{n})=(\frac{a}{p_{1}})^{\alpha_{1}}(\frac{a}{p_{2}})^{\alpha_{2}}\cdots(\frac{a}{p_{k}})^{\alpha_{k}}}\) ，其中 \(\mathsf{n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}}\)

• 注意：

  如果 \(\mathsf{(\frac{a}{n})=-1}\) 那么 a 是模 n 下的平方剩余，如果 a 是模 n 下的平方剩余并且 \(\mathsf{gcd(a,\ n)=1}\)，則 \(\mathsf{(\frac{a}{n})=1}\)

  但是，不同于 Legendre 符號：如果 \(\mathsf{(\frac{a}{n})=1}\) 那么 a 可能是也可能不是模 n 下的平方剩余，如：\(\mathsf{(\frac{-1}{77})=1}\) ，但是 -1 是平方非剩余

• 例子：

  \(\mathsf{(\frac{1001}{9907})=(\frac{7}{9907})(\frac{11}{9907})(\frac{13}{9907})}\)

  \(\mathsf{ (\frac{7}{9907})=-(\frac{9907}{11})=-(\frac{2}{7})=-1 \qquad (\frac{11}{9907})=-(\frac{9907}{11})=-(\frac{7}{11})=(\frac{11}{7})=(\frac{4}{7})=1 \qquad (\frac{13}{9907})=(\frac{9907}{13})=(\frac{1}{3})=1}\)

  \(\mathsf{(\frac{1001}{9907})=(\frac{9907}{1001})=(\frac{898}{1001})=(\frac{2}{1001})(\frac{449}{1001})=(\frac{449}{1001})=(\frac{1001}{449})=(\frac{103}{449})=(\frac{449}{103})=(\frac{37}{103})=(\frac{103}{37})=(\frac{29}{37})=(\frac{37}{29})=(\frac{8}{29})=(\frac{2}{29})^{3}=-1}\)

五、Tonelli-Shanks 演算法

1. Tonelli-Shanks 演算法用于求解形如：\(\mathsf{x^{2} \equiv n\ mod\ p}\) 的二次同余方程，

   輸入：p ，一個奇素數，n 是一個整數，其中 n 是模 p 下的平方剩余，意味著 Legendre 符號\(\mathsf{(n/p)=1}\)

   輸出：R ，一個整數滿足\(\mathsf{R^{2} \equiv n}\)

   (1) 從 p-1 開始，對 p-1 進行因式分解，分解為\(\mathsf{p-1=Q2^{S}}\) ，其中 Q 為奇數，如果 \(\mathsf{S=1\ (p \equiv 3\ mod\ 4)}\) ，則由 \(\mathsf{R \equiv \pm n^{\frac{p+1}{4}}}\) 直接給出解，

   (2) 選擇一個 Z 為模 p 下的平方非剩余，令\(\mathsf{c \equiv z^{Q}}\)

   (3) 令\(\mathsf{R \equiv n^{\frac{Q+1}{2}}，t \equiv n^{Q}，M=S}\)

   (4) 回圈：

   <1> 如果\(\mathsf{t \equiv 1}\) ，回傳 R

   <2> 否則，找一個最小的 i ，\(\mathsf{0<i<M}\) ，使得 \(\mathsf{t^{2^{i}} \equiv 1}\) (重復平方)

   <3> 令\(\mathsf{b\equiv c^{2^{(M-i-1)}}}\) 并且令 \(\mathsf{R \equiv Rb,\ t \equiv tb^{2},\ c \equiv b^{2}}\) 且 \(\mathsf{M=i}\) (mod p 條件下)

   如果 R 是一個解，那么第二個解就是\(\mathsf{p-R}\)

• 證明：

  已知 \(\mathsf{p-1=Q2^{S} \qquad r \equiv n^{\frac{Q+1}{2}}\ mod\ p \qquad t \equiv n^{Q}\ mod\ p}\)

  所以 \(\mathsf{r^{2}\equiv nt\ mod\ p}\) 對于每次迭代都為真

  如果 \(\mathsf{t \equiv 1\ mod\ p}\) ，那么 \(\mathsf{r^{2} \equiv n\ mod\ p}\) 并且該演算法以 \(\mathsf{R \equiv \pm r\ mod\ p}\) 結束

  如果 \(\mathsf{t \neq 1\ mod\ p}\) ，那么認為 z 為模 p 下的平方非剩余

  令 \(\mathsf{c \equiv z^{Q}\ mod\ p}\) ，那么 \(\mathsf{c^{2^{S}} \equiv (z^{Q})^{2^{S}} \equiv z^{2^{S}Q} \equiv z^{p-1} \equiv 1\ mod\ p}\) 并且 \(\mathsf{c^{2^{S-1}} \equiv z^{\frac{p-1}{2}} \equiv -1\ mod\ p}\) 這表明 c 的階數是 \(\mathsf{2^{S}}\)

  同理，有 \(\mathsf{t^{2^{S}} \equiv 1\ mod\ p}\) ，所以 t 的階數整除 \(\mathsf{2^{S}}\)

  假設 t 的階數是 \(\mathsf{2^{S^{'}}}\) ，由于 n 是模 p 的平方，\(\mathsf{t \equiv n^{Q}\ mod\ p}\) 也是一個平方，因此 \(\mathsf{S^{'} \leq S-1}\)

  之后令 \(\mathsf{b \equiv c^{2^{S-S^{'}-1}}\ mod\ p \qquad r^{'} \equiv br\ mod\ p \qquad c^{'} \equiv b^{2}\ mod\ p \qquad t^{'} \equiv c^{'}t\ mod\ p}\) 則和上述一致，\(\mathsf{(r^{'})^{2} \equiv nt^{'}\ mod\ p}\) 成立

  然而 t 和 \(\mathsf{c^{'}}\) 的階都是 \(\mathsf{2^{s^{'}}}\) ，這表明 \(\mathsf{t^{'}}\) 的階數為 \(\mathsf{2^{S^{''}}}\)滿足 \(\mathsf{S^{''}<S{'}}\)

  如果 \(\mathsf{S^{''}=0}\) 那么 \(\mathsf{t^{'} \equiv 1\ mod\ p}\) 并且該演算法在 \(\mathsf{R \equiv \pm r^{'}\ mod\ p}\) 終止

  否則，用 \(\mathsf{b^{'},\ r^{''},\ c^{''},\ t^{''}}\) 相似的定義重新開始回圈直到 \(\mathsf{S^{' \cdots '}}\) 等于 0

  因此，一系列的 S 是屬于嚴格逐漸減少的演算法，一定會終止

• 例子：

  求解二次同余方程 \(\mathsf{x^{2} \equiv 10\ mod\ 13}\) ，明顯 13 是奇素數，由于 \(\mathsf{10^{\frac{13-1}{2}}=10^{6}\equiv 1\ mod\ 13}\) ，10 是平方剩余

  (1) 已知 \(\mathsf{p-1=12=3 \cdot 2^{2}}\) ，令 \(\mathsf{Q=3,\ S=2}\)

  (2) 令 \(\mathsf{Z=2}\) 為平方剩余，因為 \(\mathsf{2^{\frac{13-1}{2}}=-1\ mod\ 13}\) ，令 \(\mathsf{c=2^{3} \equiv 8\ mod\ 13}\)

  (3)\(\mathsf{R=10^{2} \equiv -4\ ,\ t \equiv 10^{3} \equiv-1\ mod\ 13 \qquad M=2}\)

  (4) 開始回圈：\(\mathsf{t \neq 1\ mod\ 13}\) ，所以 \(\mathsf{0<i<2}\) ，則 \(\mathsf{i=1}\) ，

  令 \(\mathsf{b \equiv 8^{2^{2-1-1}}\equiv 8\ mod\ 13 \qquad c=b^{2}\equiv 8^{2} \equiv -1\ mod\ 13}\)

  \(\mathsf{R=Rb=-4 \cdot 8 \equiv 7\ mod\ 13 \qquad t=tb^{2} \equiv -1 \cdot -1 \equiv 1\ mod\ 13 \qquad M=i=1}\)

  回傳開始，因為 \(\mathsf{t \equiv 1\ mod\ 13}\) ，回傳 \(\mathsf{R \equiv 7\ mod\ 13}\)

  驗證：\(\mathsf{7^{2}=49 \equiv 10\ mod\ 13}\) 且 \(\mathsf{(-7)^{2} \equiv 6^{2} \equiv 10\ mod\ 13}\)

1. 引理：如果 a，b 都與 p 互素，且 a，b 的階都為 \(\mathsf{2^{j}\ mod\ p\ (j>0)}\) ，則對于某些 \(\mathsf{k<j}\) 時 ab 的階表示為 \(\mathsf{2^{k}}\)

• 證明：

  a 的階數為 \(\mathsf{2^{j}\ mod\ p}\) ，則 \(\mathsf{a^{2^{j-1}} \equiv -1\ mod\ p}\) ，同理 \(\mathsf{b^{2^{j-1}} \equiv -1\ mod\ p}\)

  所以，\(\mathsf{(ab)^{2^{j-1}} \equiv 1\ mod\ p}\) ，也就是說 ab 的階數整除 \(\mathsf{2^{j-1}}\) ，因此，\(\mathsf{k<j}\)

標籤：其他

上一篇：19.HVV溯源

下一篇：計算機二級WPS科目