CRYPTO中的数论基础（更新中）

本文持续更新中

数论简介：

数论（number theory），是纯粹数学的分支之一，主要研究整数的性质。

模运算

1. 模运算规则

a mod b (b>0，且a,b均为整数) 相当于许多编程语言中的a % b,表示a作为被除数，b作为除数时，计算所得到的余数

这里强调,除数b必须是正整数，而被除数a可以是负整数

2. 整除的概念

如果a mod b= 0，则称b整除a，记作b|a

如：15/5=3，则5|15

3.整除的性质

1
2
3
1.若a|b, a|c, 则a|(b+c)
证明：

1
2.若a|b，则对任意c(c≠0)，a|bc
1
3.对任意非零整数a，±a|a=±1
1
4.若a|b，b|a，则|a|=|b|
1
5.a|b,a|c⇔∀x,y∈Z ,a|(bx+cy)
1
6.如果a|b,a|c, gcd(b,c)=1,那么a|bc,反过来也成立
1
7.若m≠0,则a|b⇔(m⋅a)|(m⋅b)
1
8.x,y∈Z,且∃a,b 使ax+by=1,a|n,b|n⇒(a⋅b)|n

4. 模运算举例

15点是下午3点，19点是晚上7点，这其实就运用了模运算（x mod 12）

a为负整数时怎么算呢？

例如：-11 mod 4

我们可以让-11不停加上4

-11+4=-7，-7+4=-3，-3+4=1

所以-11 mod 4 = 1（即-11=4*(-3)+1）

最大公约数

1.公约数和最大公约数的概念

设整数a,b 如果存在整数d,使d|a,d|b,则称d是a和b的公因子(或公约数)

如果 d>0 ,且a和b的所有公因子都整除d,则称d是a和b的 最大公约数 ，记作gcd(a,b)

哎为什么这里没有限制公因子是正整数还是负整数嘞？

因为公因子可正可负可为0！

3和6的公因子:+1,-1,+3,-3

其中gcd(3,6) = 3

再有就是说，求最大公约数时可以把负号直接去掉来求:

1
gcd(-3,6) = gcd(3,6) = 3 ; gcd(-3,-6) = gcd(3,6) = 3

互素

定义：

1
如果gcb(a,b) = 1,称a和b互素

存在这样一个定理:

1
如果gcd(a,b) = d，那么存在整数m,n 使得a=md,b=nd,且gcd(m,n)=1

例如gcd(4,6)=2 ,m=2,n=3,m和n互质

证明：

1
2
3
4
如果gcd(m,n)=t >1，
即m,n有大于1的公约数
那么gcd(a,b)=td,
与gcd(a,b)=d矛盾

欧拉函数

定义：对于正整数n，φ (n) = 集合{1,2,…,n}中与n互质的数的个数。

  1. 若n是质数

    φ(n)=n−1

  2. 若n是质数的幂(n=pᵏ，k≥1)

    φ(pᵏ)=pᵏ−pᵏ⁻¹

  3. 若n是任意正整数（质因数分解为n=p₁^k₁⋅p₂^k₂⋅…⋅pₘ^kₘ）

    欧拉函数是积性函数：若a和b互质（GCD(a,b)=1），则φ(ab)=φ(a)⋅φ(b)。因此：φ(n)=n⋅(1−1/p₁)⋅(1−1/p₂)⋅…⋅(1−1/pₘ)

算术基本定理

任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积.

埃拉托斯特尼筛法（埃氏筛）求范围内素数

根据上面算术基本定理我们可以知道，一个合数一定是一个比它小的素数的倍数. 我们观察以下一串数字

2 3 4 5 6 7 8 9 10 11 12 13 14 15

去除2的倍数(>2)之后得到：

2 3 5 7 9 11 13 15

去除3的倍数(>3)后得到：

2 3 5 7 11 13

发现仅仅两次筛选就筛去了这串数字中的所有合数

并且观察算术基本定理，一个合数的素因数一定存在，且应当是小于它本身的

即我们采取从小到大将每个质数的倍数都筛去的方法，当我们遍历到65537这个质数时，可以说小于65537的所有合数都已经被筛选掉了

于是我们先认为从2开始所有的数都是素数，从2开始由小到大，将其所有的倍数标记为合数。在一定范围内重复此过程

埃氏筛法的python实现（以n<=100为例）

1
2
3
4
5
6
7
8
9
10
11
12
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)  #先假设全部是素数
    p = 2
    while (p * p <= n):
        if (is_prime[p] == True):
            for i in range(p * p, n + 1, p):  #将所有p的幂，标为合数
                is_prime[i] = False
        p += 1
    primes = [p for p in range(2, n + 1) if is_prime[p]]
    return primes
n = 100
print(sieve_of_eratosthenes(n))

欧几里得算法(辗转相除法)计算最大公约数

欧几里得算法的原理

不妨设a>=b>=0

1.b=0时,gcd(a,0)=a 任何数都是0的因子，所以这里是a

2.b!=0时，求gcd(a,b)，许多情况下我们可以写出

1
a=q*b+r

​ 假设gcd(a,b)=t, 那么上式写为：

1
m*t=q*n*t+r
1
r=(m-q*n)t

​

由此得到：t也是余数r的因子。这个结论对a和b的任意因子都成立，显然也对最大公因子成立

所以我们知道

1
gcd(a,b)=gcd(b,r)

计算过程

通过不断缩小问题规模，把求两个数的最大公约数转化为更简单的情况。

  1. 若较小的数是0，答案就是较大的数
    • 比如求gcd(8,0)=8，因为所有数都能整除0
  2. 若两数都不为0，用除法转换问题：
    • 用大数除以小数：70 ÷ 15 = 4 余 10（写作70 = 4×15 +10）
    • 此时gcd(70,15) = gcd(15,10)（关键转换！）
    • 继续对新数对重复这个过程

实操

​ gcd(70,15)=gcd(15,10)=gcd(10,5)=gcd(5,0)=5

  1. 70 ÷ 15 = 4 余10 → 转为求gcd(15,10)
  2. 15 ÷ 10 = 1 余5 → 转为求gcd(10,5)
  3. 10 ÷ 5 = 2 余0 → 转为求gcd(5,0)
  4. 出现0时，答案就是剩下的5

代码实现

1
2
3
4
5
6
7
8
9
def gcd(a,b):
    while b!=0:
        t = a % b
        a = b
        b = t
    return a
a = ？
b = ？
print(gcd(a,b))

扩展的欧几里得算法

扩展欧几里得算法是欧几里得算法的升级版，它不仅计算两个数的最大公约数（GCD），还能找到一组关键系数（称为贝祖系数），使得这两个数的线性组合等于它们的最大公约数。

贝祖定理：

1
若 d=gcd⁡(a,b)，则存在整数 s,t使得 as+bt=d
1
2
特别地，若 gcd⁡(a,b)=1，则方程 as+bt=1 有解（即 a 和 b 互质时存在逆元）。
推论：方程 as+bt=v 有解当且仅当 d∣v（即 v 是 d 的倍数）。

而扩展的欧几里得算法就是用来计算上述定理中的s和t

原理：

根据欧几里得算法的逆过程，这里以gcd(70,15)为例

前文已经写出了欧几里得算法的过程，我们只需根据它一步一步回代

1
5=15×1−10×1
1
2
3
其中 10=70×1+15×(−4)，代入得：

5=15×1−(70×1+15×(−4))×1=70×(−1)+15×5

代码实现

1
2
3
4
5
6
7
8
9
10
11
def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        d, s_prime, t_prime = extended_gcd(b, a % b)
        s = t_prime
        t = s_prime - (a // b) * t_prime
        return (d, s, t)

d, s, t = extended_gcd(70, 15)
print(f"gcd(70,15)={d}, 系数 s={s}, t={t}")

==============================================================================================

​ 施工区域

最小公倍数

引入：天干地支纪年法中，天干有10个，地支有12个

我们知道60年1甲子，天干循环一次周期是10，地支循环周期是12；

从一次出现甲子到下一次出现甲子，不仅需要天干中出现甲，地支中出现子，则刚好需要天干循环整数次，地支循环整数次，显然，这就变成了一个最小公倍数问题，每60年能让天干循环6次，地支循环5次

设a,b∈Z，如果m∈Z分别是a和b的倍数，m称为a和b的公倍数设a,b∈Z，如果m∈Z分别是a和b的倍数，m称为a和b的公倍数

a,b≠0，如果m是所有正的公倍数中最小的，那么m叫做a和b的最小公倍数，记为m=lcm(a,b)a,b≠0，如果m是所有正的公倍数中最小的，那么m叫做a和b的最小公倍数，记为m=lcm(a,b)

如果a=0或者b=0：lcm(a,b)=0如果a=0或者b=0：lcm(a,b)=0

lcm(a,b)=ab/gcd(a,b)

同余

两个整数 除以同一个整数，若得相同余数，则二整数同余

1
2
3
若整数a、b除以正整数m所得的余数相同，则称a与b关于模m同余，记为a≡b(modm)。用数学语言可表述为：若m∣(a−b)（即a−b能被m整除），则a≡b(modm)。

m称为同余的模

同余的运算性质

  1. 加法同余

    1
    若a≡b(mod m)且c≡d(mod m)，则a+c≡b+d(mod m)

  2. 减法同余

    1
    若a≡b(mod m)且c≡d(mod m)，则a−c≡b−d(mod m)

  3. 乘法同余

    1
    若a≡b(mod m)，c≡d(mod m)，有a⋅c≡b⋅d(mod m)

  4. 幂运算同余

    1
    若a≡b(mod m)，则对任意正整数n，有aⁿ≡bⁿ(mod m)

费马小定理

1
若 p 是一个质数，且 a 是一个不被 p 整除的整数（即 gcd(a,p)=1），则有：aᴾ⁻¹≡1(modp)

模逆元

概念

模逆元可以视为在模运算下的倒数，

1
2
对于整数a和正整数m，如果存在整数x使得：a⋅x≡1(mod m)
则称x是a模m的逆元，记作x≡a⁻¹(mod m)。

模逆元的存在是有条件的，假设有gcd(a,m)=1,那么a在模m的情况下有逆元，否则逆元不存在

计算模逆元

观察上面扩展的欧几里得算法，有表达式

1
a⋅x+m⋅y=gcd(a,m)

在满足模拟元存在的条件下，gcd(a,m)=1.对该式两边同时mod m，得到

1
a⋅x≡1(mod m)

显然，我们可以利用扩展的欧几里得算法来计算模逆元

模逆元的性质

1.唯一性：条件一定的情况下，模逆元是唯一的

2.可逆性：若x是a模m的逆元，那么a也是x模m的逆元

3.乘积的逆元等于逆元的乘积

1
(a⋅b)⁻¹≡a⁻¹⋅b⁻¹(mod m)

二次剩余

一个整数x对另一个整数p的二次剩余指的是计算x² mod p的结果（x的平方除以p得到的余数）

1
2
3
当存在一个整数x使得x² ≡ a mod p,称a是模p的二次剩余

当不存在一个整数x使得x² ≡ a mod p,称a是模p的二次非剩余

它还有这样的运算性质：

1
2
3
4
5
二次剩余 * 二次剩余 = 二次剩余

二次剩余 * 二次非剩余 = 二次非剩余

二次非剩余 * 二次非剩余 = 二次剩余

检验整数是否是二次剩余参见下文勒让德符号

勒让德符号

勒让德符号(Legendre Symbol)提供了一种有效的方法来确定整数a是否是模奇数素数p的二次余数

勒让德符号-维基百科

image-20250207182502113

我们可以给出证明

由费马小定理ap−1≡1(modp)ap−1−1≡0(modp)(ap−12+1)(ap−12−1)≡0(modp)则有ap−12=±1(modp)由费马小定理a^{p-1}\equiv1\pmod{p}\\ a^{p-1}-1\equiv0\pmod{p}\\ (a^{\frac{p-1}{2}}+1)(a^{\frac{p-1}{2}}-1)\equiv0\pmod{p}\\ 则有a^{\frac{p-1}{2}}=\pm1\pmod{p}\\

先假定存在x，使得$x^2 \equiv a \pmod{p} $

(x2)p−12−ap−12≡0(modp)(x^2)^{\frac{p-1}{2}} - a^{\frac{p-1}{2}} \equiv 0 \pmod{p}\\

那么存在整系数多项式，使得

xp−x=(x2−a)xP(x)+(−1)xx^p - x = (x^2-a)xP(x) + (-1)x

我们有定理，模p下x的n次多项式方程有解（且有n个解）

当且仅当存在整系数多项式q(x)和r(x)，使得xp−x=f(x)q(x)+pr(x)x^p-x = f(x)q(x) + pr(x)

那么可以断言，当ap−12≡1a^{\frac{p-1}{2}}\equiv1时，满足条件x2−a≡0(modp)x^2-a \equiv 0 \pmod{p} 有两个解；

当ap−12≡−1a^{\frac{p-1}{2}}\equiv-1时,x2−a≡0(modp)x^2-a \equiv 0 \pmod{p} 无解

以cryptohack中的题目为例：

题目要求：

Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.

给定1024bit的质数和10个整数，找到二次剩余并且计算它的模平方根，取较大的一个作为flag

image-20250208144201545

我们首先根据勒让德符号，得到哪一个整数是二次剩余。代码如下：

1
2
3
4
5
6
7
8
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = []#篇幅有限，省略掉了
for i in ints:
    a_p = pow(i,(p-1)//2,p)
    if(a_p == 1):
        print(i)
        a = i
print(a,"为二次剩余")

这里提一句，python判断是否是二次剩余的写法：

1
2
3
4
if pow(n,(p-1)//2,p) == 1:
	print("二次剩余")
if pow(n,(p-1)//2,p) == p - 1:
	print("二次非剩余")

第三行写的是p-1，因为python的pow函数计算结果不会为负。

之后求它的模平方根，需要用到一定的代数运算。

1
2
3
4
5
6
7
#求a模p意义下的平方根
#因为a**[(p-1)/2] ≡ 1 (mod p)
#所以a**[(p+1)/2] ≡ a (mod p)
#所以a**[(p+1)/4] ≡ a**(1/2) (mod p)
# 计算a**[(p+1)/4] mod p
print(pow(a,(p+1)//4,p))
#注意这里需要确定(p+1)/4是整数，即p mod 4 = 3

Tonelli-Shanks算法

**Tonelli-Shanks算法(托内利-尚克斯算法)**可以计算模素数下的平方根。

python实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def legendre_symbol(a, p):
    """计算勒让德符号 (a/p)"""
    return pow(a, (p - 1) // 2, p)

def tonelli_shanks(n, p):
    """Tonelli-Shanks算法求解 x^2 ≡ n (mod p)"""
    assert legendre_symbol(n, p) == 1, "n 不是模 p 的二次剩余"

    # 处理 p ≡ 3 (mod 4) 的特殊情况
    if p % 4 == 3:
        return pow(n, (p + 1) // 4, p)

    # 找到 q 和 s，使得 p-1 = q * 2^s，且 q 为奇数
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1

    # 找到一个非二次剩余 z
    z = 2
    while legendre_symbol(z, p) != -1:
        z += 1

    # 初始化变量
    m = s
    c = pow(z, q, p)
    t = pow(n, q, p)
    r = pow(n, (q + 1) // 2, p)

    while t != 0 and t != 1:
        # 找到最小的 i 使得 t^(2^i) ≡ 1 (mod p)
        t2i = t
        i = 0
        for i in range(1, m):
            t2i = pow(t2i, 2, p)
            if t2i == 1:
                break

        # 更新变量
        b = pow(c, 2**(m - i - 1), p)
        m = i
        c = pow(b, 2, p)
        t = (t * c) % p
        r = (r * b) % p

    return r

# 示例用法
n = 10
p = 13
result = tonelli_shanks(n, p)
print(f"x^2 ≡ {n} (mod {p}) 的一个解是 x ≡ {result} (mod {p})")

也可以使用各种库，如sympy

1
2
3
4
5
6
from sympy.ntheory.residue_ntheory import nthroot_mod

a = 
p = 
result = nthroot_mod(a,2,p)
print(result)

这里nthroot_mod函数相当于计算x² ≡ a (mod p)

关于常用库的常用函数的文章火热筹备中。

中国剩余定理

中国剩余定理（Chinese Remainder Theorem, CRT）指出，如果一组线性同余方程的模两两互质，那么这组方程有唯一解。

1
2
3
4
5
6
7
8
9
x≡a₁ mod n₁

x≡a₂ mod n₂

……

x≡aₙ mod nₙ

则存在唯一解x≡amodN，其中N=n₁⋅n₂⋅...⋅nₙ

image-20250709162505240

阶乘取模

计算n! mod p（其中n是正整数，p是素数）的问题

大组合数取模

组合数，又称二项式系数

先来复习一下高中的组合数

假如我们需要在5个苹果中选2个出来，有两种问法

  1. 假如考虑顺序：N = 5 * 4
  2. 假如不考虑顺序，对于挑选出来这两个苹果（a，b），在考虑顺序的情况下显然当作(a,b)和(b,a)记了两次，也就是记了k!次，我们应当对全排列的结果分母加上k!来消除顺序影响

于是对于不考虑顺序的情况，n个选k个的问题，我们得到公式

image-20250710104940251

接下来我们来研究对p取模的两种情形

1.p是素数——Lucas定理

2.p是合数——exLucas定理

image-20250709162505240