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. 模运算举例

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矛盾

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

欧几里得算法的原理

不妨设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≠0，如果m是所有正的公倍数中最小的，那么m叫做a和b的最小公倍数，记为m=lcm(a,b)
$$

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

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

同余

费马小定理

模逆元

二次剩余

一个整数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

以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)

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

中国剩余定理