数论知识

本文主要介绍整除、质数和合数、同余定理、模逆元素、欧几里得除法、欧拉函数、欧拉定理、费马小定理、中国剩余定理（孙子定理）。

简介

最近学习了公钥算法，涉及了一些数论中的知识。对一些数论的基础知识做一下总结。

• gcd是最大公约数。
• lcm是最小公倍数。

一、整除

a,b是任意的两个整数，b不为0，存在整数q，使得a=qb。记作：b|a

二、质数和合数

除了平凡约数±1和±n之外，n没有其他的因数。则n是质数（质数又称为素数），否则是合数。例如（3、7、11、13都是素数）

• 1既不是素数也不是合数。
• 两个数互质：没有除1以外的公因子。如果a与n的最大公因子为1，可写成gcd(a，n)=1。
• 素数有无穷多个

素数在密码学中的地位还是非常高的。

三、同余定理

• 给定一个正整数，a，b是两个整数，m|a-b，则a、b模m同余，记作a≡b(mod n)。

• 定理：设m是一个正整数，a，b是两个正整数，则a≡b(modm)的充要条件是存在一个整数k，使得a=b+km。

• 对于正整数n，整数a1 , a2, b1, b2，如果
  a1≡a2 (mod n). b1≡b2 (mod n)
  则我们可以得到如下性质:
  a1＋b1= a2+ b2 (mod n)
  a1·b1= a2·b2 (mod n)

模逆元素

对整数 a 和正整数 n，a 对模数 n 的模逆元素是指满足以下条件的整数 b。
ab≡1(mod n)

a对模数 n 的模逆元素不一定存在，a 对 模数 n 的模逆元素存在的充分必要条件是 a 和 n 互质

四、Euclid（欧几里得）除法

a，b是两个整数，b>0。存在唯一的q、r使得：a=qb+r。可以用欧几里得算法（又称为辗转相除法）求两个数的最大公因子。

可以利用辗转相除法求最大公因子

gcd(a,b)=gcd(a−b,b)

eg：gcd(4864,3458)=38
4864 = 3458+1406
3458 = 21406+646
1406 = 2646+114
646 = 5114+76
114 = 176+38
76 = 2*38

如果用绝对值最小余数代替最小非负余数。运算的次数可能会减少，从而可以减少计算的时间。

六、欧拉（Euler）函数

设n是一个正整数，则n个整数0，1，…，m-1中与m互素的整数的个数，记作Φ(n)
eg：Φ(2)=1；Φ(1)=1

• 若p是素数则 Φ( p )=p-1
• 若p和q是不同的素数，则Φ( p*q )=(p-1)(q-1)=Φ( p )Φ( q )

欧拉定理

对于每个互质的a与n，即gcd(a,n)=1，可以得到：a^Φ(n) ≡1(mod)n

七、费马小定理

如果p是一个质数，而整数a不是p的倍数（即gcd(a,p)=1），则有a^（p-1）≡1（mod p）或者a^ϕ(m)≡ 1 mod (m)。
费马小定理是欧拉定理的特殊情况

八、中国剩余定理CRT

最早见于《孙子算经》(中国南北朝数学著作，公元420-589年)，叫物不知数问题，也叫韩信点兵问题。又称孙子定理。

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

其实是求解一个一次同余方程组

求解的过程可以参考以下链接: 中国剩余定理（CRT ）
作者写的非常的简单通俗易懂。

总结

对于这部分的学习，作者也只是简单的入门，里面涉及到的知识点非常的基础。推荐一个好用的工具：sagemath。

参考文章： 密码学基础1：RSA算法原理全面解析
中国剩余定理（CRT ）