主页
Featured image of post ACM学习笔记——线性同余方程……

ACM学习笔记——线性同余方程……

数论——乘法逆元、线性同余方程……

文章字数:3631
预计阅读时长: 分钟

该笔记还未完成整理,待日后继续整理……

该笔记目前直接复制的之前的笔记,还未调整格式。页面格式、内容、链接等可能存在混乱错误……

0x00 前提知识

同余

$\equiv$:是数论中表示同余的符号。
用法:$a \equiv b \pmod n$

定义

  • 最基本的定义:两个数$a,b$对另一个数$n$的取余都相同。
  • 衍生定义:$(a-b) \bmod n = 0$

记作:$a \equiv b \pmod n$,表示$a,b$对$n$同余。

如:
$7 \bmod 3 = 1$
$10 \bmod 3 = 1$
则:$7 \equiv 10 \pmod 3$

性质

以下部分为个人总结,名称不一定准确。

  1. 自反性:$a \equiv a \pmod m$。
  2. 对称性:若$a \equiv b \pmod m$,则$b \equiv a \pmod m$。
  3. 传递性:若$a \equiv b \pmod m$,$b \equiv c \pmod m$,则$a \equiv c \pmod m$。
  4. 替换性:对于$M \equiv ab \cdot x \pmod m$,若$ab \equiv c \pmod m$,则$M \equiv c \cdot x\pmod m$。
  5. 加减可移项性:若$a \pm b \equiv c \pmod m$,则$a \equiv c \mp b \pmod m$
  6. 线性运算:如果$a \equiv b \pmod m$,$c \equiv d \pmod m$,那么有:
    1. $a \pm c \equiv b \pm d \pmod m$。
    2. $ac \equiv bd \pmod m$。
      推论:若$a \equiv b \pmod m$,则有$an \equiv bn \pmod m (n\in Z, n \ne 0)$。
  7. 模数的除法:若$ac \equiv bc \pmod m$,$\gcd(m,c)=d$,则$a \equiv b \pmod{m/d}$;
    特别地,当$\gcd(m,c)=1$时,有$a \equiv b \pmod m$。
  8. 模数的乘法:若$a \equiv b \pmod m$,则有$ak \equiv bk \pmod{mk}$,其中$k$为大于零的整数;
    推论:若$a \equiv b \pmod m$,$d$为$a,b$及$m$三者的任一正公约数,则$a/d \equiv b/d \pmod{m/d}$。
  9. 传递性2:若$a \equiv b \pmod m$,且$d \mid m$,则$a \equiv b \pmod d$。

参考自“wcwcwch”的「同余的性质」

其他点

需要注意的是:
负数也可以进行取模,因此也存在同余。

如:
$-36 \bmod 15$,
用除法表示为$-36 \div 15 = -3 \cdots 9$(验算:$15*-3+9=-36$),
即$-36 \bmod 15 = 9$,

所以$-36 \equiv 24 \pmod{15}$。

由于这个符号很新颖和陌生,导致在学习的时候理解上产生了很大的障碍,
因此需要尽快适应这个符号的使用方法。

首先需要知道的是:同余代表的是一种关系,而非运算。
因此才会采用类似于等号的符号来表示。
但这种等于,并不是像$2=2$这样直接就可以判断,
而是要经过稍微的运算,两边同时取模后等于,才叫同余。

然后对于这个符号,有很多种不同的理解方式,
建议自己确定一个自己习惯的理解方式并一直用下去。
个人所采用的是:$a \equiv b \pmod m$,代表$a \bmod m = b \bmod m$。

需要牢记一个转换式: $$a \equiv b \pmod m \implies a = mk + b (k∈Z)$$

整除

$\mid$:是数论中的表示整除符号。
用法:$a \mid d$

注意:
这里的整除就是整除,不是被整除。
如上例:是$a$整除$b$,或说$b$被$a$整除。

如:
$2\mid14$
则是$2$整除$14$,$14$被$2$整除。

整除也代表两者大除小余数为$0$,故同余还可以写为:
$m \mid (a-b)$
$\implies (a-b) \bmod n = 0$
$\implies a \equiv b \pmod n$

学习顺序

  1. 裴蜀定理
  2. 扩展欧几里得
  3. 初步认识线性同余方程
  4. 认识乘法逆元并求解
  5. 求解线性同余方程

其中:

  • 1、2为$\gcd$内容
  • 3、4、5为本章(线性同余方程)内容。

0x01 初步认识

定义

形如$f(x) \equiv 0 \pmod m$的方程称为同余方程,
其中$f(x)=a_nx^n+a_{n-1}x^{n_1}+\cdots+a_1x+a_0$。

记:$f(x)$最高次数为$n$,则称为$n$次同余方程。
特别的:当$n=1$时,称为一次同余方程,又称线性同余方程。

即:
形如$ax \equiv b \pmod m$的方程
被称为线性同余方程(Congruence Equation)。

如:
$12x \equiv 9 \pmod {15}$
解得:$x=\cdots,-3,2,7,12,17,\cdots,5n+2(n∈Z)$

当$x=-3$时,$12*-3=36$,$-36 \bmod 15 = 9$,满足方程。
当$x=2$时,$12*2=24$,$24 \bmod 15 = 9$,满足方程。
当$x=7$时,$12*7=84$,$84 \bmod 15 = 9$,满足方程。

同样,对于这个方程,
我们也需要对其快速建立自己的理解方法。

个人理解方法是:
当$x$取某一值时,则$ax$对$m$取模的结果就是$b$。


与普通的一元线性方程不同的是:
普通的一元线性方程肯定存在唯一解(如$2x+3=5$);
而线性同余方程若有解,需要存在一定条件

有解条件

对于线性同余方程$ax \equiv b \pmod m$,其存在解的条件是:
$b$能够被$a$与$m$的最大公约数整除。

表示为: $$\gcd(a,m) \mid b$$

如上例中:
$12x \equiv 9 \pmod {15}$

因为$\gcd(12,15)=3$,而$3$能整除$9$,
即$\gcd(12,15) \mid 9$,
所以有解。

如:
$3x \equiv 5 \pmod 6$,

因为$\gcd(3,6)=3$,而$3$不能整除$5$,
故该同余方程无解,
也就是说无论你$x$取何值,都不能满足$3x$对$6$取模后值为$5$。


注意到,若$x_0$是线性同余方程$ax \equiv b \pmod m$的一个解,
那么对于$x_n \equiv x_0 \pmod m$,$x_n$也是该线性同余方程的解。
或者说$mk+x_0(k∈Z)$均为解。

如上例中:
$12x \equiv 9 \pmod {15}$

$x_0=2$时为一解,
因此$15k+2(k∈Z)$均为解,即$2,17,32,\cdots$均为解。

$x_0=7$时为一解,
因此$15k+7(k∈Z)$均为解,即$7,22,37,\cdots$均为解。

$x_0=12$时为一解,
因此$15k+12(k∈Z)$均为解,即$12,27,42,\cdots$均为解。

因此对于线性同余方程的解的个数,我们定义为:
在$0 \sim (m-1)$中解的个数。

如上例中:
$12x \equiv 9 \pmod {15}$

解的个数就为$3$个,分别为$2,7,12$。

解的性质

对于线性同余方程$ax \equiv b \pmod m$,记$\gcd(a,m)=d$
若存在解,则会满足以下性质:

  1. 对于$x_0$为该线性同余方程的任意一解,记,
    则通解可以表示为$\frac{m}{d}k + x_0 (k∈Z)$。

    如上例中:
    $12x \equiv 9 \pmod {15}$
    $d=\gcd(12,15)=3$

    得到一解$x_0=2$,
    则通解可以表示为$5k+2(k∈Z)$。

  2. 解的个数恰为$d$个。

    如上例中:
    $12x \equiv 9 \pmod {15}$

    则在$0 \sim 14$范围中,解为$2,7,12$。
    个数为$d=\gcd(12,15)=3$,即$3$个。

  3. 唯一解定理
    当$d=1$时,该同余方程有且仅有唯一解。

0x02 乘法逆元

定义

如果一个线性同余方程$ax \equiv 1 \pmod m$,存在解$x$,
则$x$称为$a \bmod m$的逆元,记作$a^{-1}$。

如:
$5x \equiv 1 \pmod{14}$,

当$x=3$时,$15 \bmod 14 = 1$,满足方程。
所以$3$为$5$关于$14$的逆元。

性质

对于一个线性同余方程$ax \equiv 1 \pmod m$,
记$a$关于$m$的逆元$x$为$a^{-1}$。

  1. 存在充要条件:$a,m$互素,$\gcd(a,m)=1$。
  2. 唯一性:$a^{-1}$在$[0,m-1]$范围内唯一。

    证明:

    我们先假设$a$有两个不相等逆元:$a'$ 和$a''$,
    那么一定有:$aa' \equiv aa'' \equiv 1 \pmod m$

    不妨设$a'∈[0,m-1]$,$a'<a''$且$a''-a'=k$,
    那么由于$a\ne0$,所以$k$一定是$k \equiv 0 \pmod m$ ,即$k=cm(c∈Z,c\ne0)$(见最上的转换式
    所以$a''=a' + cm(c∈Z,c\ne0)$,
    所以$a'‘∈[cm,(c+1)m-1] (c∈Z,c\ne0)$,一定不在$[0,m-1]$范围内,
    所以$a$在$[0,m-1]$范围内只能有一个逆元。

  3. 完全积性:$a^{-1} \cdot b^{-1} = (a \cdot b)^{-1}$
  4. $\gcd(a^{-1},m)=1$。
  5. ${(a^{-1})}^{-1} \equiv a \pmod m$

作用

1. 对除法取模

首先对于取模运算,存在以下性质:
$(a + b) \bmod p = ((a\bmod p) + (b\bmod p)) \bmod p$ (对)
$(a - b) \bmod p = ((a\bmod p) - (b\bmod p)) \bmod p$ (对)
$(a \times b) \bmod p = ((a\bmod p) \times (b\bmod p)) \bmod p$ (对)

$(a \div b) \bmod p = ((a\bmod p) \div (b\bmod p)) \bmod p$ (错)

如:
$(100/50)\bmod20 = 2$
$\nRightarrow((100\bmod20)/(50\bmod20))\bmod20=0$

因此如果对于一些题目,如果运算要求求余,但该运算为除法,
我们就不能直接像加减乘运算一样拆开求余

但如果被除数,除数也超范围,那是不是只能用高精度了?
并不是这样,我们可以利用乘法逆元来拆开求余


乘法逆元又称为数论倒数。
既然这么称呼,那么乘法逆元就跟倒数有相似之处。

对于普通的数学运算$a \div b$,
其也可以写成$a \times \frac{1}{b}$。

因此对于求余运算$(a/b) \bmod m$,
其也可以写成$(a \cdot b^{-1}) \bmod m$,

这时便可以拆开求余为$((a\bmod m) \cdot (b^{-1}\bmod m))\bmod m$。


即存在性质: $$a/b \bmod m = a \cdot b^{-1} \bmod m$$

*参考自“Aloof__”的「乘法逆元的作用(逆元的作用是什么)」。*

证明

根据逆元的定义,存在: $$b \cdot b^{-1} \equiv 1 \pmod m$$

同余式两边同乘$a$,得到: $$ab \cdot b^{-1} \equiv a \pmod m$$

同余式两边同除$b$,得到: $$a \cdot b^{-1} \equiv a/b \pmod m$$

得证。

2. 线性同余方程的反函数

对于线性同余方程$ax \equiv b \pmod m$,
表示为函数的形式即为$f(x) = ax \bmod m$。

如果知道函数值$f(x)$,
那么反求解$x$的方法为:$x = f(x) \cdot a^{-1}$。

需要满足$x<m$,
否则为$x \equiv f(x) \cdot a^{-1} \pmod m$。

如:
$2x \equiv f(x) \pmod{11}$。 当$x = 13$时,$f(x) = 4。

$2$对$11$的逆元是$6$,
$4 \times 6 = 24$。

$24 \equiv x(13) \pmod{11}$,
而不是$24 = x(13)$。


主要应用于CTF中仿射加密的解密。

证明

很简单的证明。

$$ax \equiv f(x) \pmod m$$ $$ax \cdot a^{-1} \equiv f(x) \cdot a^{-1} \pmod m$$ $$x \equiv f(x) \cdot a^{-1} \pmod m$$ 得证。

求解方法

待补充!……