密码学的一些数学基础

二次剩余

0x1 勒让德符号

$${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\quad 0\quad 如果{\displaystyle a\equiv 0{\pmod {p}}} \\ +1\quad 如果{\displaystyle a\not \equiv 0{\pmod {p}}}a\not \equiv 0{\pmod {p}},且对于某个整数{\displaystyle x,x^{2}\equiv ;a{\pmod {p}}}\quad \\ -1\quad 如果不存在整数{\displaystyle x}x,使得{\displaystyle x^{2}\equiv ;a{\pmod {p}}}\end{cases}}}$$

简单来说就是一个快速判断是否是二次剩余的标志

勒让德符号的公式

$${\displaystyle \left({\frac {a}{p}}\right)=\pm 1\equiv a^{\frac {p-1}{2}}{\pmod {p}}.}$$

计算二次剩余

当$p\equiv3{\pmod4}$时,有$p+1\equiv0{\pmod4}$,那么可以用下面的方法求二次剩余

$$ (\pm a^{\frac{p+1}{4}})^2 \equiv a^{\frac{p-1+2}{2}}\equiv a^{\frac{p-1}{2}}\cdot a{\pmod p}$$

由于选择的a是有二次剩余的,所以有
$$ a^{\frac{p-1}{2}}\equiv1{\pmod p} $$

那么

$$x=\pm a^{\frac{p+1}{4}},x^2\equiv a{\pmod p}$$

实际做题的时候可以用sage直接解$x^n \equiv a{\pmod n}$

0x2 利用二次剩余来计算一般二次同余式

设二次同余式为
$$ax^2+bx+c\equiv0\pmod{p}$$

两边同乘$4a$再加$b^2$得到

$$4a^2x^2+4abx+b^2\equiv b^2-4ac\pmod{p}$$

化简得到

$$(2ax+b)^2\equiv b^2-4ac\pmod{p}$$

即形如最简二次同余式

$$x^2\equiv d\pmod{p}$$

对于二次最简同余式就可以分情况讨论,可以参考这篇文章

多元coppersmith

sagemath里的small_roots方法只支持单变量的方程,但github上有大佬已经写出了理论上支持n元多项式的coppersmith脚本

多元coppersmth