数论基本

整除

$a=mb$,则非零整数 b整除a,即a/b==m&&a%b==0&& mod b ==0，用$b|a$来表示，同样可以说 b 是 a 的一个因子

性质

1. $a|b 且 b|c，则a|c$

2. $若b|g,b|h,对于任意整数m和n，都有b|(mg+nh)，反之亦然$
   大多数数论上的证明都可以把形如$a|b$是式子展开为$a=kb$这样，比较容易。下面证明上面的那个引理。

$$证明：设g=xb,h=yb,则 mg+nh=xmb+nyb，显然 b|(b(xm+ny)),n和m为任意整数$$

推论

设a,b是两个不全为0的整数，q为整数，则$(a,b)=(a\pm bq,b)=(a,b\pm aq)。$

$$证明:令r=a \pm bq，那么a=b(\mp)q+r,则(a,b)=(b,r)=(a\pm bq,b)。同理..$$

欧几里得算法\辗转相除法

最大公因子\最大公约数

1. 定义c=gcd(|a|,|b|)=max[k,保证k|b且k|b]，则c为a和b的最大公约数\最大公因子。

$$令 k=gcd（m，n），j=gcd(n,m\mod n)，即证 k=j \\ 设 m=pn+(m \mod n)（除法定义）\\ 又因为 j|n 且 j|(m\mod n),则 j|m 成立，且 j 是 m 的一个因子，那么 j 就是 m 和 n 的一个公约数，但不一定最大，下面证明最大，由于 k 是 m 和 n 的最大公约数，就有 k\geq j\\ 由 m=pn+(m \mod n)可知，(m \mod n)=m-pn,又因为 k|m 且 k|(-pn)，则 k|(m \mod n)，k 是(m \mod n)和 n 的公约数数，可以得到 j\geq k,所有 k=j，gcd 算法正确。$$

1. $gcd(a,b)=1$，我们可以说a和b互素\互质。

模运算

就是 $m \mod n$和%意义是一样的，例如$73\mod 23 =4$和编程中的73%23=4是相同的，但是模运算有很多性质，比如同余$18 \equiv 11 \mod 7=>(18-1)|7$，意思是18和11模7的达到的结果相同。

性质

简单的例如传递性，交换律，还有上面定义就不说了，这里介绍主要运算性质。在密码学可能用到的的比较多。

1. $[(a \mod n )\pm(b \mod n)] \mod n = (a\pm b) \mod n$

2. $[(a \mod n )\times(b \mod n)] \mod n = (a \times b) \mod n$

第二条乘法运算可以化简大整数的模运算，例如求$11^7 \mod 13$：

$$11^4=11^2 \equiv 4^2 \mod 13$$ $$11^7=11 \times 4 \times 3 \equiv 132 \mod 13 \equiv 2 \mod 13$$

乘法逆元，加法逆

1. 在模运算的世界中，存在一个整数$y$，使得$(x+y)\mod n =0$，那么我们称$y$是$x$ 的一个加法逆元素，例如$(2+6)\mod 8 =0$,6 就是 2 的一个加法逆元素。

2. 若存在$xy \mod n=1$，则称$y$是 x 的乘法逆元，并不是所有的x都有乘法逆元，一般来说n是个素数就可以了，这一点后面文章会讨论。求一个数的乘法逆元，需要用到扩展的欧几里得算法。不过我们也可以用工具进行求解，例如在sagemath可以使用 inverse_mod(100,123457)来求得在模123457下的100乘法逆元，答案是8642，显然$100 \times 8642 \equiv 1 \mod 123447$。如果我们试图求得inverse_mod(100,123456),就会出错，inverse of Mod(100, 123456) does not exist。下面给出Python的代码

#扩展欧几里得算法
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
# 求逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

如果看得了扩展欧几里得算法，显然可知只有gcd(a,n)==1的情况下，a在模n中才有乘法逆元。 那么下面的运算法则也只有在a和n互素的情况下成立： $$ (a \times b)\equiv (a \times c)(\mod n) $$ 只需两边乘以a的乘法逆元即成立，gcd(a,n)!=1，那a就没有乘法逆元，改式就不成立了

剩余类和剩余类集

剩余类集是由剩余类组成的的集合，例如，模n的剩余类可以表示为[0],[1],[2]...[n-1],这里面[r]={a:a是一个整数，a mod n == r},显然，模n的剩余类一种有n个，每个剩余类中的元素数量是无穷多个。

定义：小于n的集合$Z_n = \{0,1,2,3...n-1\}$，对于一般模数n，若a和n有任何公因子，那用$a$去乘以$Z_n$中的数则不会得到一个完整的剩余类集。

令a=6 n=8，则有 $$ todo:latex表格 $$ 显然，若a和n互素，则能得到一个完全剩余类集，而在$Z_n$中就有一个乘法逆元

---

本页面的全部内容在 CC BY-NC-SA 4.0 协议之条款下提供，附加条款亦可能应用。

评论