GENIA

Cryptohack wp(1) - Modular Arithmetic

2024-09-18

Modular Arithmetic - 简单算术

Greatest Common Divisor

对于两个素数 a 和 b，如果 gcd(a,b) = 1 ，那么可以说 a 和 b 互质。

如果 a 和 b 都是素数，那 a 和 b 一定互质。

如果 a 是素数并且 b < a，那么 a 和 b 也是互质的。

问：如果 a 是素数并且 b > a，为什么 a 和 b 不一定互质？

答：因为 b 可能是 a 的倍数。

用于计算最大公约数的最常见算法是 欧几里得 算法，就是我们古代的辗转相除法（《九章算术》中出现）。

辗转相除法基于如下原理：

两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

循环计算，使这两个数不断缩小直至余数为 0。剩下的数即为最大公约数。

以 a = 12，b = 8 为例：

12 / 8 = 1 …… 4

8 / 4 = 2 …… 0

所以 4 是最大公约数。

问：求 gcd（a,b) , a = 66528, b = 52920

66528 / 52920 = 1 …… 13608

52920 / 13608 = 3 …… 12096

13608 / 12096 = 1 …… 1512

12096 / 1512 = 8 …… 0

所以结果是 1512。

用代码来实现：

1
2
3
4
5
6
7
8
9
10
def gcd(a,b):
	if a >= b:
		x,y = a,b
	else:
		x,y = b,a
	while y != 0:
		z = x % y
		x = y
		y = z
	return x

Extended GCD

通过扩展欧几里得算法，我们在得到正整数 a 和 b 的最大公因数的同时，还可以求出满足裴蜀定理的整数 u 和 v 。

扩展欧几里得算法利用了带余除法所得的商，在辗转相除的同时也能得到裴蜀等式中的u、v两个系数。且以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。

复习：矩阵的初等变换

扩展欧几里得算法在原来得基础上引入了 s 和 t 两组序列：

具体如下例：

用初等变换（这里只用到了列与列之间的第三种初等变换）表示：

问：有两个质数 p = 26513 , q = 32321 , 已知 $p\cdot u + q\cdot v = \gcd(p,q)$，求出 u 和 v

首先 p 和 q 是两个质数，那么它们的公约数一定是 1。但是我没感觉这能给计算带来什么便利。

代码跑一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def gcd_extend(x,y):
    if x > y:
        a,b = x,y
    else:
        a,b = y,x
    s_a,s_b = 1,0
    t_a,t_b = 0,1
    while b!= 0:
        c = a % b
        d = a // b
        a = b
        b = c
        s_c = s_a - d*s_b
        s_a = s_b
        s_b = s_c
        t_c = t_a - d*t_b
        t_a = t_b
        t_b = t_c
    return s_a,t_a

u,v = gcd_extend(26513,32321)
print(f"u = {u},v = {v}")

结果是 ：u = -8404, v = 10245

扩展欧几里得算法的一个重要应用是计算模逆元，而求出模逆元是RSA算法中获取公钥、私钥的必要步骤。

Modular Arithmetic 1

同余的概念

如果两个整数 a 和 b 除以同一个整数 得到的余数相同都等于 m，则可以称 a 和 b 同余。

记作 $a\equiv b \pmod{m}$ 。即 $a-b = km$ 。

也有一种特殊情况，当 m 整除 a 时（a 能被 m 完全整除，没有余数，也记作 $m \mid a$），a 在模 m 下与 0 同余。

记作 $a\equiv 0 \pmod{m}$ 。

这题口算一下就行，x = 5，y = 8146798528947 % 17 = 4

显然更小的是 4。

Modular Arithmetic 2

模数运算

对一个数取模，相当于用这个数除以模数并取余数。比如 7 mod 3 = 1。

模数p为素数

则 $0$ 到 $p-1$ 这些数的集合构成一个“域”，数学上称为 $\mathbb{F}_p$ 。

在这个域里，对于集合中的每一个元素 $a$ ，加法和乘法都有对应的“反元素” $b_+$ 和 $b_*$ ，实现 $a + b_+ = 0$ , $a \cdot b_* = 1$ 。

模数p为非素数

则 $0$ 到 $p-1$ 这些数的集合只能构成一个“环”，环中加法仍然有反元素，但乘法不一定有。

因为我没学过数论，这里关于域和环的定义我是云里雾里的，首先我不清楚为什么环不一定有乘法逆元，其次我并不知道数集构成域或环与p是否为素数能建立一种怎样的关系，它又和和费马小定理有什么联系。暂时先跳过吧。

费马小定理

这个定理属于数论。假设 a 是一个整数，p是一个素数，那么 $a^p - a$ 是 p 的倍数。

可以记作：$a^p \equiv a \pmod{p}$

如果 a 不是 p 的倍数，这个定理可以写成一个常用形式：$a^{p-1} \equiv 1 \pmod{p}$

如果 a 是 p 的倍数，则有：$a^{p-1} \equiv 0 \pmod{p}$

费马小定理的逆叙述是不成立的，也就是说，如果 $a^p - a$ 是 p 的倍数，并不能保证 p 是一个素数。

问：已知素数 p = 65537, 计算 $273246787654^{65536} \bmod 65537$

273246787654 不是 65537 的倍数，所以这个结果为 1。

Modular Inverting

对于由素数 p 个元素构成的有限域 $\mathbb{F}_p$ ，其中的每个元素 g，存在一个数字 d，使得 $g \cdot d \equiv 1 \pmod{p}$。就是说 g 和 d 相乘的结果对 p 取模后等于 1。数字 d 就是 g 的乘法逆元。

问：已知 $3\cdot d \equiv 1 \pmod{13}$ ，利用费马小定理求出 d

根据费马小定理，当 p 为素数时，有：$a^p \equiv a \pmod{p}$

根据同余的基本法则，当 除数 与 模数 互质时，同余两边可以同时除以该除数。

若 $a \equiv b \pmod{m}$，$\gcd(d,m)=1$，则 $\dfrac{a}{d} \equiv \dfrac{b}{d} \pmod{m}$ 。

因为 13 为素数，且 3 小于 13，因此在题设情况下，a 和 p 一定是互质的。

所以有：$a^{p-1} \equiv 1 \pmod{p}$ ，进一步变化为：$a \cdot a^{p-2} \equiv 1 \pmod{p}$

与 $3\cdot d \equiv 1 \pmod{13}$ 相对照，很容易得到 $d_0 = 3^{11} = 177147$ 。

$d_0$ 还并不算是最简的，我们需要再将其 mod 13 得到最后的结果 $d = d_0 \bmod 13 = 9$ 。

Quadratic Residues

模平方根

对于给定的奇素数 p ，若 $a^2 \equiv b \pmod{p}$ ，则称 a 是 b 的模平方根。（a 和 b 都要求是 $\mathbb{F}_p$ 中的数）

要求出有限域 $\mathbb{F}_p$ 中任意一个一个整数 b 的模平方根，按照我们现有的知识水平，只有从 1 开始一个一个试到 p-1，看看是否有符合条件的 a。

题目直接给出了结论，即并不是 $\mathbb{F}_p$ 中的任何一个整数都有模平方根，只有大概一半的集合元素可以找到满足条件的 a。

在数论中的同余理论中，如果存在 a 满足以上条件，也可以说 b 是模 p 的二次剩余。

反过来说，如果不存在 a 满足以上条件，我们就说 b 是模 p 的二次非剩余。

问：已知 $p=29$，$ints=[14,6,11]$，我们需要找出 ints 列表中唯一的模 p 的二次剩余，并计算出它的模平方根。

暂时不会别的算法，暴力求解一波。

1
2
3
4
5
6
7
8
9
10
p = 29
ints = [14,6,11]
flag = 0
for i in range(3):
    for j in range(1,p):
        if (j*j)%p==ints[i]:
            flag = 1
            print(f"quadratic residue:{ints[i]}, square root:{j}")
    if flag == 1:
        break

输出：

1
2
quadratic residue:6, square root:8
quadratic residue:6, square root:21

提交模平方根中更小的一个，那就是 8。

Legendre Symbol

通过二次剩余定理，我们知道了模平方根的概念。也了解了并不是有限域 $\mathbb{F}_p$ 中的所有的整数都存在模平方根。

如果模数 p 较小时，我们可以通过暴力遍历的方式判断哪些元素是 p 的二次剩余，但当 p 增大到一定数量级之后，该方法就不再合理了。

二次（非）剩余的简单性质

1
2
3
Quadratic Residue * Quadratic Residue = Quadratic Residue
Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

类似于同或的性质。把二次剩余看作 1 ，二次非剩余看作 -1 ，也满足以上条件。

勒让德符号（二次特征）

这是一种用来判断整数是否为奇素数 p 的二次剩余的有效方法。

勒让德符号的定义：

该符号遵循以下规则：

因此我们只需要计算 $\left(\dfrac{a}{p}\right)$ 就可以判断 a 是否是 p 的二次剩余。

问：给定1024位素数 p 和10个整数，找到 p 的二次剩余，然后计算其模平方根。已知 $p \equiv 3 \pmod 4$ 。

计算 $a^{\frac{p-1}{2}} \pmod p$ ，求出 p 的二次剩余。

计算得到 ints 中只有一个数属于 p 的二次剩余。而 $p \equiv 3 \pmod 4$ 。

因为 $p \equiv 3 \pmod 4$ ，所以 $p = 4k+3$ ，$p+1=4k+4$ ，$p-1=4k+2$。k 是整数。

已知 a 是二次剩余，所以有：

$$
a^{\frac{p-1}{2}} \equiv 1 \pmod p
$$

$$
a^{2k+1} \equiv 1 \pmod p
$$

根据同余的基本性质：若 $a \equiv b \pmod p$，则 $ka \equiv kb \pmod p$，得到 $a^{2k+2} \equiv a \pmod p$。

则 $x^2 = (\pm a^{k+1})^2$，所以 $x = \pm a^{\frac{p+1}{4}}$。

那这题就直接出结果了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 
    45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 
        17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 
        14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 
        4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 
        85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 
        50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 
        96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 
        4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 
        18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

Quadratic_Residue = []
for i in ints:
    if pow(i, (p-1)//2, p) == 1:
        Quadratic_Residue.append(i)

print(pow(Quadratic_Residue[0],(p+1)//4,p))

'''
[85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771]
93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526
'''

Modular Square Root

所有的非 2 素数 p ，也就是奇素数，都遵循两种情况：$p \equiv 1 \pmod 4$ 或者 $p \equiv 3 \pmod 4$ 。

对于后一种情况，可以通过费马小定理推导出一个模平方根的直接计算式。但是对于前一种情况没有更快捷的方式。

而 Tonelli-Shanks 算法就是一种通用的方法。

Tonelli-Shanks 算法不适用于复合（非素数）模量。求平方根模复合在计算上等价于整数分解，是一个难题。

Tonelli-Shanks 算法的实现

  1. 通过欧拉检验判断 $a$ 是否为二次剩余，计算 $a^{\frac{p-1}{2}} \pmod p$，如果结果是 $p-1$ （在模运算中，$-1$ 就等同于 $p-1$），则模平方根不存在。如果结果为 1，继续。

  2. 将 $p-1$ 分解为 $2^e \cdot s$ ，$e$ 是一个整数，$s$ 是一个奇数。

  3. 找出一个数 $q$ ，使得 $q^{\frac{p-1}{2}} \equiv -1 \pmod p$ ，也就是说需要找出一个 $p$ 的二次非剩余。

  4. 初始化变量：

    $x = a^{\frac{s+1}{2}}$

    $b=a^s \pmod p$

    $g=q^s \pmod p$

    $r=e$

  5. 进入循环阶段，不断更新变量，直到找到平方根：

    • 找到最小的 $m$，使其满足 $b^{2^m} \equiv 1 \pmod p$ ，$0 \leq m \leq r-1$ 。

    • 如果 $m=0$ ，说明当前的 $x$ 已经是正确的平方根，可以直接返回结果。

    • 如果 $m\neq 0$ ，则继续更新变量：

      $x = x \cdot g^{2^{r-m-1}}$

      $b = b \cdot g^{2^{r-m}}$

      $g = g^{2^{r-m}}$

      $r = m$

  6. 直到 $m=0$ 或 $b=1$ ，循环终止，返回 $x$ 作为模平方根。

  7. 如果 $x$ 是模平方根，$p-x$ 也是。

问：计算一个 2048 位的素数 p 下二次剩余 a 的模平方根。

在 Sage 中有封装好的函数可以使用，如下：

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
sage: from sage.rings.finite_rings.integer_mod import square_root_mod_prime
sage: a = 8479994658316772151941616510097127087554541274812435112009425778595495
....: 35970024447040064240374705856680712781416539664021584419232790045411625797
....: 94874320167693299707670467350912498986780880616347965595567049598464241318
....: 20416048436501387617211770124292793308079214153179977624440438616958575058
....: 36119397568662004643987730833998929560453786749368387277884392177130730560
....: 27763987869783538662316614533760567719720697763989990137695889361948593449
....: 41268223184197231368887060609212875507518936172060702209557124430477137421
....: 84713068260166696869165144723691701863490240770479732850946185484243201500
....: 9878011354022108661461024768
sage: p = 3053185186199433325267593511148795069441433276390908351413376986135096
....: 08950765046872613698157357425494287891383008430820865500590828351414545266
....: 18160634109969195486322015775943030060449557090064811940139431735209185996
....: 45473916355591072649359722264685550644560295368952740536220792699044239170
....: 50146047770386858805275374898453591015524422928043984726423566093048106807
....: 31556542002301547846635101455995732584071355903010856718680732337369128498
....: 65525527700364366903169451685139050592341671060121261844310984404151494240
....: 19696291589754570790269063043287490399972629603012091581759200518906209470
....: 63936347307238412281568760161
sage: mod_a = Mod(a, p)
sage: square_root_mod_prime(mod_a, p)
2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120
sage: p-236233930768304863832777329858048929893213750552050038833827105205373474
....: 78623517796473141768179533590718715600411252899192471460749071516127626408
....: 68199621186559522068338032600991311882224016021222672243139362180461232646
....: 73246584884042545825793088785658337960096776173859678287785131848935567982
....: 28131551230457052851120994481464267551101600025155924188504321036418158110
....: 71548456284263507805589445073657565381850521367969675699760755310784623577
....: 07644003774768176030243492493211364006173877760119462224419275802418085391
....: 62444272540654419625572825728491627727407989896479486452073497374574454404
....: 05057156897508368531939120
....:
28169512554311284614348161812907461395482195258388583125795498809297226147214152907614055638917789190356917578259717792167302913007927989841763977292434488782635964253677743342038748567333074043589267896292373028724763808006697707070301035339291758998923066001985927788808579330075671953036025191791621915640175242425390397212674797332132801882880223506177201168864920484993546017284338829512010922075018689505381642887042980971582058343875078178836965895987271392081926458392283354971823611423820865651283490761548053384731721391637064349021755899877224522161311561209530712702153163501623531290150340903913036821041

Chinese Remainder Theorem

中国剩余定理给出了以下的一元线性同余方程组：

假设整数 $m_1, m_2, \dots, m_n$ 其中任意两数互质，则对于任意的整数 $a_1, a_2, \dots, a_n$ ，方程组 $S$ 有解。

其通解可以通过以下方式构造得到：

  1. 设 $M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i$ ，其中 $m_i$ 是整数 $m_1, m_2, \dots, m_n$ 的乘积，并设 $M_i = M / m_i, \quad \forall i \in {1, 2, \cdots, n}$，即 $M_i$ 是除 $m_i$ 以外的 $n-1$ 个整数的乘积。
  2. 设 $t_i = M_i^{-1}$ 为 $M_i$ 模 $m_i$ 的数论倒数：$\quad t_i M_i \equiv 1 \pmod{m_i}, \quad \forall i \in {1, 2, \cdots, n}$
  3. 方程组 $S$ 的通解形式为：$x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + kM = kM + \sum_{i=1}^n a_i t_i M_i, \quad k \in \mathbb{Z}$ 。在模 $M$ 的意义下，方程组 $S$ 只有一个解：$\quad x = \sum_{i=1}^n a_i t_i M_i$ 。

问：已知 $x \equiv 2 \pmod 5$，$x \equiv 3 \pmod{11}$，$x \equiv 5 \pmod{17}$，求一个整数 a 满足 $x \equiv a \pmod{935}$ 。

根据中国剩余定理：

$$
M = 5\times11\times17 = 935
$$

$$
M_1 = 187,\ m_1 = 5
$$

$$
M_2 = 85,\ m_2 = 11
$$

$$
M_3 = 55,\ m_3 = 17
$$

根据费马小定理：如果 a 不是 p 的倍数且 p 为素数，有 $a^{p-1} \equiv 1 \pmod{p}$ ，那么 $a \cdot a^{p-2} \equiv 1 \pmod{p}$ 。

求出：

$$
t_1 = 187^3 \bmod 5 = 3
$$

$$
t_2 = 85^9 \bmod 11 = 7
$$

$$
t_3 = 55^{15} \bmod 17 = 13
$$

$$
x = 2\cdot 3\cdot 187 + 3\cdot 7\cdot 85 + 5\cdot 13\cdot 55 = 6482
$$

$$
a = 6482 \bmod 935 = 872
$$

Adrien’s Signs

已知题目条件，其中 $e$ 是在 $[1, p]$ 区间内取的随机整数：

$$
a = 288260533169915
$$

$$
p = 1007621497415251
$$

$$
n = a^e \bmod p
$$

若 $b=1$，则 $final = n$；若 $b=0$，则 $final = -n \bmod p = p-n$。其中 final 数组已知，求 b 序列。

经过程序判断，a 不是素数，p 是素数，a 与 p 互质。

Tags: 数学 密码学
← 数据结构-图-模板代码 nju-os M1 →