二次剩餘

二次剩餘（英文：Quadratic residue ）係數論入邊嘅概念。攞住一個正整數 n，如果有第個整數 x，達到 x² 除以 n 後得出嘅餘數係 q，噉 q 就謂之模 n 嘅二次剩餘。用數學符號表達，就係：

x^{2}\equiv q{\pmod {n}}

而如果搵唔到任何整數 x 可以令到上便條式成立嘅，噉 q 就算係做模 n 嘅二次非剩餘（英文：quadratic nonresidue ）。

基本概念

舉例：

模 5 嗰陣，
$2^{2}=4$ ，而 $4$ 除以 $5$ 餘 $4$ ，所以 $4$ 係模 $5$ 嘅二次剩餘。
模 7 嗰陣，
$3^{2}=9$ ，而 $9$ 除以 $7$ 餘 $2$ ，所以 $2$ 係模 $7$ 嘅二次剩餘。
模 11 嗰陣，
$5^{2}=25$ ，而 $25$ 除以 $11$ 餘 $3$ ，所以 $3$ 係模 $11$ 嘅二次剩餘。

實際應用

密碼學

二次剩餘同密碼學有密切關係。設依家要同二次剩餘搵出佢哋對應咩數嘅次方，如果涉及嘅數夠細，分析者可以好容易試勻晒唔同嘅 x，睇吓邊啲餘數係二次剩餘；但若果 n 數值好大，要判斷某個數係咪二次剩餘，或者要由一個二次剩餘反過來搵返佢嘅平方根，就可以好嘥時間，而噉就意味住，密碼學專家可以用二次剩餘，嚟令到黑客難以搵出用咗嘅輸入^{[未記出處或冇根據]}。

睇埋

二次互反律

參考資料

Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae, Clarke, Arthur A.翻譯 (第Second corrected版), New York: Springer, ISBN 0-387-96254-9
Gauss, Carl Friedrich (1965), Untersuchungen über hohere Arithmetik [Disquisitiones Arithemeticae & other papers on number theory], Maser, H.翻譯 (第second版), New York: Chelsea, ISBN 0-8284-0191-8