密碼學(xué)專題 - 數(shù)學(xué)知識

2. 數(shù)論

這里僅列出一些對密碼學(xué)有用的思想炫掐，關(guān)于數(shù)論更詳細(xì)的知識請參考專業(yè)文獻。

2.1 模運算

本質(zhì)上子库，如果 $a = b + kn$ 對某些整數(shù) $k$ 成立舱权，那么 $a \equiv b \ (mod \ n)$ 。如果 $a$ 為正仑嗅， $b$ 為 0 ~ n宴倍，那么你可將 $b$ 看做 $a$ 被 $n$ 整除后的余數(shù)。有時 $b$ 叫做 $a$ 模 $n$ 的余數(shù) (residue)仓技。有時 $a$ 叫做與 $b$ 模 $n$ 同余 (congruent) (三元等號 $\equiv$ 表示同余)鸵贬。

從 $0 \sim n-1$ 的整數(shù)組成的集合構(gòu)成了模 $n$ 的完全剩余集 (complete set of residue)。這意味著脖捻，對于每一個整數(shù) $a$ 阔逼，它的模 $n$ 的余項是從 $0 \sim n-1$ 的某個數(shù)。

$a$ 模 $n$ 的運算給出了 $a$ 的余數(shù)地沮，余數(shù)是從 $0 \sim n-1$ 的某個整數(shù)嗜浮，這種運算稱為模變換 (modular reduction)涯保。例如， $5 \ mod \ 3 \ = 2$ 。

模運算就像普通運算一樣未荒，它是可交換的、可結(jié)合的和可分配的寨腔。而且率寡，簡化每一個中間結(jié)果的模 $n$ 運算，其作用與先進行全部運算再簡化模 $n$ 運算是一樣的冶共。
$(a+b) mod \ n = ((a \ mod \ n) + (b \ mod \ n)) mod \ n$

$(a-b) mod \ n = ((a \ mod \ n) - (b \ mod \ n)) mod \ n$

$(a \times b) mod \ n = ((a \ mod \ n) \times (b \ mod \ n)) mod \ n$

密碼學(xué)用了許多模 $n$ 運算，因為像計算離散對數(shù)和平方根這樣的問題很困難家卖，而模運算可將所有中間結(jié)果和最后結(jié)果限制在一個范圍內(nèi)庙楚，所以用它進行計算比較容易上荡。對一個 $k$ 位的模數(shù) $n$ ，任何加馒闷、減酪捡、乘的中間結(jié)果將不會超過 $2k$ 位長。因此可以用模運算進行指數(shù)運算而又不會產(chǎn)生巨大的中間結(jié)果纳账。雖然計算某數(shù)的乘方并對其取模的運算
$a^x \ mod \ n$

將導(dǎo)致一系列的乘法和除法運算逛薇，但有加速運算的方法：一種方法指在最小化模乘法運算的數(shù)量；另一種旨在優(yōu)化單個模乘法運算疏虫。因為操作步驟劃分后金刁，當(dāng)完成一串乘法，并且每次都進行模運算后议薪，指數(shù)運算就更快尤蛮，這樣就與一般取冪沒有多大差別，但當(dāng)用 200 位的數(shù)字進行運行時斯议，情況就不同了产捞。

例如，如果要計算 $a^8 \ mod \ n$ 哼御，不要直接進行七次乘法和一個大數(shù)的呐髁伲化簡：
$(a \times a \times a \times a \times a \times a \times a \times a) mod \ n$

相反焊唬，應(yīng)進行三次較小的乘法和三次較小的模化簡：
$((a^2 mod \ n)^2 mod \ n)^2 mod \ n$

以此類推看靠，
$a^{16} mod \ n = (((a^2 mod \ n)^2 mod \ n)^2 mod \ n)^2 mod \ n$

當(dāng) $x$ 不是 2 的冪次方時鸥滨，計算 $a^x \ mod \ n$ 稍微要難些⊥怪鳎可將 $x$ 表示成 2 的冪次方之和：在二進制中卿吐，25 是 11001，因此 $25=2^4 + 2^3 + 2^0$ 谨湘。故：
$a^25 \ mod \ n = (a \times a^{24})mod \ n = (a \times a^8 \times a^{16})mod \ n = (a \times ((a^2)^2)^2) \times (((a^2)^2)^2)^2) mod \ n = ((((a^2 \times a)^2)^2)^2 \times a) mod \ n$

注意，上面的公式利用了擅耽， $x^n \times y^n = (xy)^n$ 。

適當(dāng)利用存儲的中間結(jié)果询兴，只需要 6 次乘法：
$(((((((a^2 \ mod \ n) \times a)mod \ n)^2 mod \ n)^2 mod \ n)^2 mod \ n) \times a) mod \ n$

這種算法稱為加法鏈 (addition chaining)警儒，或二進制平方和乘法方法边琉。它用二進制表示了一個簡單明了的加法鏈变姨。算法的 C 語言描述如下：

unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) {
    unsigned long s, t, u;
    int i;

    s = 1; t = x; u = y;
    while (u)
    {
        if (u&1) s = (s * t) % n;
        u >>= 1;
        t = (t * t) % n;
    }
    
    return s;
}

另一種遞歸算法為：

unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) {
    unsigned long tmp;
    if (y == 1) return (x % N);

    if ((y & 1) == 0) {
        tmp = fast_exp(x, y/2, N);
        return ((tmp * tmp) % N);
    }
    else {
        tmp = fast_exp(x, (y-1) / 2, N);
        tmp = (tmp * tmp) % N;
        tmp = (tmp * x) % N;
        return (tmp);
    }
}

對應(yīng)的 python 實現(xiàn)如下。

def qe2(x, y, n):
    s = 1
    t = x
    u = y

    while (u):
        if (u&1):
            s = (s * t) % n
        u >>= 1
        t = (t * t) % n
    
    return s

另一種遞歸算法為：

def fast_exp(x, y, N):
    if (y == 1):
        return (x % N)

    if ((y & 1) == 0):
        tmp = fast_exp(x, y/2, N)
        return ((tmp * tmp) % N)
    else:
        tmp = fast_exp(x, (y-1) / 2, N)
        tmp = (tmp * tmp) % N
        tmp = (tmp * x) % N
        return (tmp)

如果用 $k$ 表示數(shù) $x$ 中位數(shù)的長度，這項技術(shù)平均可減少 $1.5k$ 次操作愧口。

2.2 整除性與素數(shù)

素數(shù)是這樣一種數(shù)：比 1 大耍属，其因子只有 1 和它本身巩检，沒有其他數(shù)可以整除它领舰。2 是一個素數(shù)冲秽，其他的素數(shù)如 73、2521民轴、2365347734399 和 $2^{756839}-1$ 等后裸。素數(shù)是無限的。密碼學(xué)祈搜，特別是公開密鑰密碼學(xué)常用大的素數(shù) (512 位容燕，甚至更大)官卡。

如果 $b$ 除以 $a$ 余數(shù)為 0，則稱 $a$ 是 $b$ 的一個因子 (記敘 $a|b$ 毛秘，讀作 “a整除b”)叫挟。比如，7 是 35 的一個因子奋献，記作 $7|35$ 秽荞。如果一個數(shù)只有 1 和它自身兩個正因子，我們就稱這個數(shù)是素數(shù)钦听。比如，13 是素數(shù)痪宰，兩個因子為 1 和 13乖订。最初幾個素數(shù)很容易找到：2乍构、3、5眠饮、7仪召、11钥庇、13...... 如果一個整數(shù)大于 1 且不為素數(shù)评姨，我們就稱為合數(shù)胁后。1 既不是素數(shù)也不是合數(shù)攀芯。

下面是關(guān)于整除性的一個簡單的引理。

引理 1：如果 $a|b$ 且 $b|c$ 年鸳，那么 $a|c$ 。

證明：如果 $a|b$ 膳算，那么存在整數(shù) $s$ 使得 $as = b$ (由 $b$ 能被 $a$ 整除可知 $b$ 是 $a$ 的倍數(shù))坎吻；如果 $b|c$ 瘦真，同樣存在整數(shù) $t$ 使得 $bt=c$ 诸尽。綜上可知您机， $c=bt=(as)t=a(st)$ 年局，所以 $a$ 為 $c$ 的一個因子矢否。

引理 2：如果 $n$ 為大于 1 的正整數(shù)且 $d$ 為 $n$ 除 1 之外最小的因子僵朗，那么 $d$ 是素數(shù)。

證明：首先顶吮，我們必須保證 $d$ 是被明確定義的粪薛。(如果對于某個 $n$ 违寿，除 1 之外不存在一個最小的因子，那么 $d$ 的定義就不恰當(dāng)巡揍，引理 2 就毫無意義菌瘪。) 由于 $n$ 也是 $n$ 的一個因子，而 $n>1$ 糜工，所以 $n$ 至少有一個大于 1 的因子捌木，也必然有一個大于 1 的最小因子。

為證明 $d$ 是素數(shù)澈圈，我們使用一種標(biāo)準(zhǔn)的數(shù)學(xué)技巧瞬女，稱為反證法努潘。為證明結(jié)論 X，反證法的一般思路是假設(shè) X 不成立报慕，接著從這個假設(shè)推出矛盾压怠；如果假設(shè) X 不成立能夠推出矛盾，那么 X 必須是正確的洋闽。

在這個例子中突梦，我們假設(shè) $d$ 不是素數(shù)宫患，那么 $d$ 肯定存在滿足 $1<e<d$ 的因子 $e$ 娃闲。但是從引理 1 可知匾浪，如果 $e|d$ 且 $d|n$ ，那么 $e|n$ 属拾，即 $e$ 也是 $n$ 的一個因子且 $e<d$ 。這樣就產(chǎn)生了矛盾栋齿，因為 $d$ 被定義為 $n$ 除 1 之外最小的因子，因此我們的假設(shè)是錯誤的谷丸，從而 $d$ 是素數(shù)。

定理 3 (毆幾里得)：素數(shù)有無窮多個揩慕。

證明：我們?nèi)匀皇褂梅醋C法來證明迎卤。假設(shè)素數(shù)的個數(shù)是有限的玷坠，那么一個包含所有素數(shù)的列表也是有限的，記為 $p_1,p_2,p_3,...,p_k$ 樟凄，這里 $k$ 表示素數(shù)的個數(shù)缝龄。定義 $n = p_1p_2p_3...p_k+1$ 挂谍，即 $n$ 為所有素數(shù)的乘積加上 1口叙。

考慮 $n$ 除 1 之外的最小因子，我們?nèi)杂? $d$ 來表示這個因子俺亮。由引理 2 可知， $d$ 為素數(shù)且 $d|n$ 铅辞；但是在那個有限的素數(shù)列表中斟珊，沒有一個素數(shù)是 $n$ 的因子，因為它們都是 $n-1$ 的因子旨椒， $n$ 除以列表中任何一個素數(shù) $p_i$ 都會有余數(shù) 1综慎，所以 $d$ 為素數(shù)且不在列表中勤庐。而列表在定義時就包含了所有素數(shù)的，這樣就出現(xiàn)了矛盾米罚，所以素數(shù)的個數(shù)是有限的這個假設(shè)是錯誤的丈探，從而可知素數(shù)有無窮多個。

2.3 最大公因子

兩個數(shù)互素 (relatively prime) 是指：當(dāng)它們除了 1 外沒有共同的因子隘竭。換句話說动看，如果 $a$ 和 $n$ 的最大公因子 (greatest common divisor) 等于 1精偿，那么可寫作：
$gcd(a,n) = 1$

數(shù) 15 和 28 是互素的霹期，15 和 27 不是，而 13 和 500 是鸭轮。一個素數(shù)與它的倍數(shù)以外的任何其他數(shù)都是互素的按厘。

計算兩個數(shù)的最大公因子最容易的方法是用毆幾里得算法 (Euclid's algorithm)束莫。毆幾里德在公元前 300 年所寫的《Elements》中描述了這個算法。這個算法并非由他發(fā)明享钞，歷史學(xué)家相信這個算法在當(dāng)時已有 200 年歷史狐肢。它是幸存到現(xiàn)在最古老的非凡的算法，至今它仍是完好的壶栋。

算法的 C 語言描述如下：

/* returns gcd of x and y */
int gcd(int x, int y) {
    int g;

    if (x < 0)
        x = -x;
    
    if (y < 0)
        y = -y;

    if (x + y == 0)
        exit(1);

    g = y;

    while (x > 0)
    {
        g = x;
        x = y % x;
        y = g;
    }
    
    return g;
}

這個算法可以推廣為返回由 m 個數(shù)組成的 gcd 數(shù)組。

/* return the gcd of x1, x2, ..., xm */
int multiple_gcd(int m, int *x) {
    size_t i;
    int g;

    if (m < 1)
        return 0;
    
    g = x[0];

    for (i = 1; i < m; ++i) {
        g = gcd(g, x[i]);

        /* optimization, since for random x(i), g==1 60% of the time: */
        if (g == 1)
            return 1;
    }

    return g;
}

對應(yīng)的 python 實現(xiàn)如下。

# returns gcd of x and y
def gcd(x, y):
    if (x < 0):
        x = -x
    
    if (y < 0):
        y = -y

    if (x + y == 0):
        exit(1)

    g = y

    while (x > 0):
        g = x
        x = y % x
        y = g
    
    return g

這個算法可以推廣為返回由 m 個數(shù)組成的 gcd 數(shù)組奸汇。

# return the gcd of x1, x2, ..., xm
def multiple_gcd(m, x):
    if (m < 1):
        return 0
    
    g = x[0]

    for i in range(m):
        g = gcd(g, x[i])

        # optimization, since for random x(i), g==1 60% of the time:
        if (g == 1):
            return 1

    return g

2.4 毆幾里得算法

求最大公因子 (GCD) 的算法。

2.5 求模逆元

記得逆元 (inverse) 嗎塘雳？4 的乘法逆元是 1/4妻顶，因為 $4 \times 1 / 4 = 1$ 沥潭。在模運算的領(lǐng)域，這個問題更復(fù)雜：
$4 \times x \equiv 1 (mod \ 7)$

這個方程等價于尋找一組 $x$ 和 $k$ 焊夸，以使：
$4x = 7k + 1$

這里 $x$ 和 $k$ 均為整數(shù)昌抠。

更為一般的問題是尋找一個 $x$ ，使得：
$1 = (a \times x) mod \ n$

也可寫作：
$a^{-1} \equiv x (mod \ n)$

解決模的逆元問題很困難拓挥。有時候有一個方案，有時候沒有。例如，5 模 14 的逆元是 3： $5 \times 3 = 15 \equiv 1 (mod \ 14)$ 琅攘。2 模 14 卻沒有逆元剧辐。

一般而論褂傀，如果 $a$ 和 $n$ 是互素的，那么 $a^{-1} \equiv x (mod \ n)$ 有唯一解；如果 $a$ 和 $n$ 不是互素的挎峦，那么 $a^{-1} \equiv x (mod \ n)$ 沒有解岖圈。如果 $n$ 是素數(shù)缓待，那么從 $1 \thicksim n-1$ 的每一個數(shù)與 $n$ 都是互素的铣除，且在這個范圍內(nèi)恰好有一個逆元厚宰。

一切順利《吡現(xiàn)在誉己，怎樣找出 $a$ 模 $n$ 的逆元呢丝蹭？有一系列的方法嘴脾。毆幾里得算法也能計算 $a$ 模 $n$ 的逆元奏司，有時候這叫做擴展毆幾里得算法 (extended Euclidean algorithm)结澄。

下面是用 C++ 寫的算法：

#include <stdlib.h>

#include <iostream>

using namespace std;

#define isEven(x)       ((x & 0x01) == 0)
#define isOdd(x)        (x & 0x01)
#define swap(x,y)       (x ^= y, y ^= x, x ^= y)

void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3) {
    // warning: u and v will be swapped if u < v
    int k, t1, t2, t3;

    if (*u < *v) swap(*u, *v);

    for (k = 0; isEven(*u) && isEven(*v); ++k) {
        *u >>= 1; *v >>= 1;
    }

    *u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u - 1; t3 = *v;
    
    do {
        do {
            if (isEven(*u3)) {
                if (isOdd(*u1) || isOdd(*u2)) {
                    *u1 += *v; *u2 += *u;
                }

                *u1 >>= 1; *u2 >>= 1; *u3 >>= 1;
            }

            if (isEven(t3) || *u3 < t3) {
                swap(*u1, t1); swap(*u2, t2); swap(*u3, t3);
            }
        } while (isEven(*u3));
        
        while (*u1 < t1 || *u2 < t2) {
            *u1 += *v; *u2 += *u;
        }

        *u1 -= t1; *u2 -= t2; *u3 -= t3;
    } while (t3 > 0);
    
    while (*u1 >= *v && *u2 >= *u) {
        *u1 -= *v; *u2 -= *u;
    }
    
    *u1 <<= k; *u2 <<= k; *u3 <<= k;
}

int main(int argc, char **argv) {
    int a, b, gcd;

    if (argc < 3) {
        std::cerr << "Usage: xeuclid u v" << std::endl;
        
        return -1;
    }

    int u = atoi(argv[1]);
    int v = atoi(argv[2]);

    if (u <= 0 || v <= 0) {
        std::cerr << "Arguments must be positive!" << std::endl;

        return -2;
    }

    // warning: u and v will be swapped if u < v
    ExtBinEuclid(&u, &v, &a, &b, &gcd);

    std::cout << a << " * " << u << " + (-"
            << b << ") * " << v << " = " << gcd << std::endl;

    if (gcd == 1)
        std::cout << "the inverse of " << v << " mod " << u << " is: " << u - b << std::endl;
    
    return 0;
}

此算法通過迭代運算來實現(xiàn)麻献，對于大的整數(shù)，其運行可能較慢。Knuth 指出這個算法完成的除法的平均數(shù)目是
$0.843 \times log_2(n) + 1.47$

2.6 求系數(shù)

毆幾里得算法可用于解決下面的一類問題：給出一個包含 $m$ 個變量 $x_1, x_2, ..., x_m$ 的數(shù)組，求一個包含 $m$ 個系數(shù) $u_1, u_2, ..., u_m$ 的數(shù)組千绪，使得
$u_1 \times x_1 + ... + u_m \times x_m = 1$

2.7 費馬小定理

如果 $m$ 是一個素數(shù)稿静，且 $a$ 不是 $m$ 的倍數(shù)，那么，根據(jù)費馬小定理 (Fermat's little theorem) 有：
$a^{m-1} \equiv 1 \ (mod \ m)$

2.8 歐拉函數(shù)

還有另一種方法計算模 $n$ 的逆元垦巴，但不是在任何情況下都能使用。模 $n$ 的余數(shù)化簡集 (reduced set of residues) 是余數(shù)完全集合的子集锰霜，與 $n$ 互素丽惶。例如，模 12 的余數(shù)化簡集是 ${1, 5, 7, 11}$ 檩坚。如果 $n$ 是素數(shù)赂乐，那么模 $n$ 的余數(shù)化簡集是從 $1 \thicksim n-1$ 的所有整數(shù)集合。對 $n$ 不等于 1 的數(shù)奋救，數(shù) 0 不是余數(shù)化簡集的元素秒际。

歐拉函數(shù) (Euler totient fuction)兵多，也稱為歐拉 $\varphi$ 函數(shù)您宪，寫作 $\phi(n)$ 达皿，它表示模 $n$ 的余數(shù)化簡集中元素的數(shù)目物邑。換句話說蝌矛， $\phi(n)$ 表示與 $n$ 互素的小于 $n$ 的正整數(shù)的數(shù)目 ( $n>1$ )衅金。

如果 $n$ 是素數(shù)惩琉，那么 $\phi(n)=n-1$ 伍玖；如果 $n=pq$ ，且 $p$ 和 $q$ 互素，那么 $\phi(n)=(p-1)(q-1)$ 蠕蚜。這些數(shù)字在隨后談到的公開密鑰系統(tǒng)中將再次出現(xiàn)扎狱，它們都來自于此。

根據(jù)費馬小定理的歐拉推廣射赛，如果 $gcd(a,n)=1$ 楣责，那么
$a^{\phi(n)} \ mod \ n = 1$

現(xiàn)在計算 $a$ 模 $n$ 很容易：
$x = a^{\phi(n)-1} \ mod \ n$

證明：
$(a \times x)mod \ n = (a \times a^{\phi(n)-1})mod \ n = a^{\phi(n)} \ mod \ n = 1$

例如诫隅，求 5 模 7 的逆元是多少逐纬？既然 7 是素數(shù)豁生， $\phi(7)=7-1=6$ 。因此甸箱，5 模 7 的逆元是
$5^{6-1} mod \ 7 = 5^5 mod \ 7 = 3$

計算逆元的兩種方法都推廣到在一般性的問題中求解 $x$ (如果 $gcd(a,n)=1$ )：
$(a \times x) mod \ n = b$

用歐拉推廣公式芍殖，解：
$x = (b \times a^{\phi(n)-1}) mod \ n$

用毆幾里得算法豌骏，解：
$x = (b \times (a^{-1} mod \ n)) mod \ n$

通常龟梦，毆幾里得算法在計算逆元方面比歐拉推廣更快计贰，特別是對于 500 位范圍內(nèi)的數(shù)躁倒。如果 $gcd(a, n) \neq 1$ 洒琢，并非一切都沒用了。這種一般情況而言象迎， $(a \times x) \ mod \ n = b$ 挖帘，可能有多個解或無解。

2.9 中國剩余定理

如果已知 $n$ 的素因子蜻底，那么就能利用中國剩余定理 (Chinese remainder theorem) 求解整個方程組，這個定理的最初形式是由 1 世紀(jì)的中國數(shù)學(xué)家孫子發(fā)現(xiàn)的要拂。

一般而言站楚，如果 $n$ 的素因子可分解為 $n = p_1 \times p_2 \times ... \times p_t$ ，那么方程組
$(x \ mod \ p_i) = a_i \qquad i=1,2,...,t$

有唯一解拉一，這里 $x<n$ (注意蔚润，有些素數(shù)可能不止一次地出現(xiàn)。例如嫡纠，p_1 可能等于 p_2)除盏。換句話說，一個數(shù) (小于一些素數(shù)之積) 被它的余數(shù)模這些素數(shù)唯一確定赏迟。

例如锌杀，取素數(shù) 3 和 5，取一個數(shù) 14糕再，那么 $14 \ mod \ 3 = 2, \quad 14 \ mod \ 5 = 4$ 突想。則小于 $3 \times 5 = 15$ 且具有上述余數(shù)的數(shù)只有 14究抓，即由這兩個余數(shù)唯一地確定了數(shù) 14刺下。

如果對任意 $a<p$ 和 $b<q$ ( $p$ 和 $q$ 都是素數(shù))橘茉，那么，當(dāng) $x < p \times q$ 時畅卓，存在一個唯一的 $x$ 翁潘，使得
$x \equiv a (mod \ p) 且 x \equiv b (mod \ q)$

為求出這個 $x$ 拜马，首先用毆幾里得算法找到 $u$ 箱歧，使得
$u \times q \equiv 1 (mod \ p)$

然后計算：
$x = (((a - b) \times u) mod \ p) \times q + b$

用 C 語言所寫的中國剩余定理如下：

/* r is the number of elements in arrays m and u;
m is the array of (pairwise relatively prime) moduli
u is the array of coefficients
return value is n such than n == u[k]%m[k] (k=0..r-1) and
    n < m[0]*m[1]*...*m[r-1]
*/

/* totient() is left as an exercise to the reader. */

int chinese_remainder(size_t r, int *m, int *u) {
    size_t i;
    int modulus;
    int n;
    modulus = 1;
    for (i = 0; i < r; ++i)
        modulus *= m[i];
    n = 0;
    for (i = 0; i < r; ++i) {
        n += u[i] * modexp(modulus / m[i], totient(m[i]), m[i]);
        n %= modulus;
    }
    
    return n;
}

中國剩余定理的一個推論可用于求出一個類似問題的解：如果 $p$ 和 $q$ 都是素數(shù)，且 $p < q$ 一膨，那么存在一個唯一的 $x < p \times q$ ，使得
$a \equiv x (mod \ p) 且 b \equiv x (mod \ q)$

如果 $a \geq b \ mod \ p$ 洒沦，那么
$x = (((a - (b \ mod \ p)) \times u) mod \ p) \times q + b$

如果 $a < b \ mod \ p$ 豹绪，那么
$x = (((a + p - (b \ mod \ p)) \times u) mod \ p) \times q + b$

2.10 二次剩余

如果 $p$ 是素數(shù)，且 $a < p$ ，如果
$x^{2} \equiv a \ (mod \ p) \qquad 對某些 x 成立$

那么稱 $a$ 是對模 $p$ 的二次剩余 (quadratic residue)瞒津。

不是所有的 $a$ 的值都滿足這個特性蝉衣。如果 $a$ 是對模 $n$ 的一個二次剩余，那么它必定是對模 $n$ 的所有素因子的二次剩余巷蚪。例如病毡，如果 $p = 7$ ，那么二次剩余是 1屁柏、2 和 4：
$1^2 = 1 \equiv 1(mod \ 7)$

$2^2 = 4 \equiv 4(mod \ 7)$

$3^2 = 9 \equiv 2(mod \ 7)$

$4^2 = 16 \equiv 2(mod \ 7)$

$5^2 = 25 \equiv 4(mod \ 7)$

$6^2 = 36 \equiv 1(mod \ 7)$

注意，每一個二次剩余在上面都出現(xiàn)了兩次八拱。

沒有 $x$ 值可滿足下列這些方程的任意一個：
$x^2 = 3 (mod \ 7)$

$x^2 = 5 (mod \ 7)$

$x^2 = 6 (mod \ 7)$

對模 7 的二次非剩余 (quadratic nonresidue) 是 3、5 和 6爹谭。

很容易證明旦棉，當(dāng) $p$ 為奇數(shù)時，對模 $p$ 的二次剩余數(shù)目恰好是 $(p-1)/2$ 真屯，且與其二次非剩余的數(shù)目相同。而且配深，如果 $x^2$ 等于二次剩余模 $p$ ，那么 $x^2$ 恰好有兩個平方根：其中一個在 $1 \thicksim (p-1)/2$ 之間左敌；另一個在 $(p+1)/2 \thicksim (p-1)$ 之間矫限。這兩個平方根中的一個也是模 $p$ 的二次剩余，稱為主平方根 (pricipal square root)咬扇。

如果 $n$ 是兩個素數(shù) $p$ 和 $q$ 之積，那么模 $n$ 恰好有 $(p-1)(q-1)/4$ 個二次剩余。模 $n$ 的一個二次剩余是模 $n$ 的一個完全平方堡妒。這是因為要成為模 $n$ 的平方皮迟，其余數(shù)必須有模 $p$ 的平方和模 $q$ 的平方尉尾。例如辨图，模 35 有 11 個二次剩余：1故河、4忧勿、9、11晌砾、14、15呕乎、16、21湿刽、25铃芦、29仁烹、30。每一個二次剩余恰好有 4 個平方根僚饭。