Crypto入门 （八）数论基础
前言：
现代密码学与数论密不可分，根据CTF训练营一书指出，在Crypto方面有潜力得人分为两种：一种是数学专业得学生，他们有着很好得理论基础，对数论知识得分析能力极强，需要锻炼自己得编程能力，将理论知识转换成应用能力：另一种是编程能力较强得选手，特别擅长数据处理和并行计算等，他们要适当得学一些数学基础类课程和密码学课程，特别是要对数论方面得知识进行深度学习。
可见，学好数论与能不能成为一名Crypto选手有很大关系，下面我将讲述一些基础数论知识，为后面进行讲解RSA原理、ECC原理做个铺垫。本文主要参考斯坦福大学得密码学，数论基础
Number Theory（数论）：
we will use a bit of number theory to construct: (我们将使用一点数论来构建：)
(1) key exchange protocols（密钥交换协议）
(2) Digital signatures（数字签名）
(3) public-key encryption （公钥加密）
From here on:
(1) N denotes a positive integer （N代表正整数)
(2) P denote a prime (P代表素数）
Notation(符号）： Z ={ 0，1，2，....，N-1}
Can do addtion and multiplication modulo N. (可以加 、乘 、模运算N）
arithmetic(算术运算）
Examples: let N = 12
9+8 = ? in Z12
这题结果是什么呢：？ = （9+8）mod 12，mod就是取余，我们知道9+8=17，故取余后为5，因此这题？号处填5
5x7 = ？ in in Z12
那么这题呢：5x7mod12=35mod12 = 11mod 12 = 11 或者= -1 mod 12 = 12 -1 =11
5-7 = ？ in Z12
5-7=-2 -2mod12=12-2=10
Greatest common divisor(最大公约数）
Def: For ints. x,y : gcd(x,y) is the greatest common divisor of x,y (g(x,y)是x,y得最大公约数)
Example：gcd(12,18) = 6
Fact: for all ints. x,y there exist ints. a,b such that (最大公约数等于两个整数a、b进行如下运算）
ax + by = gcd(x,y)
例如：2x12 - 1x18 = 6
a,b can be found efficiently using the extended Euclid alg.(a , b可以用扩展欧几里得算法高效发现）
if gcd(x,y) = 1 we say tha x and y are relatively prime 如果两个数x,y 他们得最大公约数是1，我们就说这两个数互质
gcd(3,5)=1
Modular inversion 模逆
over the rationals,inverse of 2 is 1/2. what about Z? 有理数2得逆是1/2，那Z呢
Def: The inverse of x in Z is an element y in ZN s.t.
x*y=1 mod N
y is denoted x-1
如：3 x 5 = 1 mod 14,所以3是5得逆，5也是3得逆，一般得，当N为奇数得时候，2得逆是 (N+1/)2
Which elements have an inverse in ZN? 那什么元素有逆
Lemma: x in ZN has an inverse if and only if gcd(x,N) =1 ,当且仅当 x和N互质得时候
proof： gcd(x,N) = 1,那么存在a,b 使得 ax + bN =1 in ZN
我们对这个式子两边取模N运算，那么由于 bN mod N = 0 ,所以 ax = 1 in ZN
此时x得逆是a
gcd(x,N) > 1 可以推出，gcd(ax ,N) > 1 从而推出 ax 不等于 1 in ZN
则a不可能是x得模逆
More natation：
Def： Z* N （set of invertible elements in ZN)={ x属于 ZN:g(x,N) = 1}
Z*12 ={1，5，7 ，11}
对于任意x in Z* N 可以发现 x得逆，通过扩展欧几里得算法
Solving modular linear equations 求解模线性方程
Solve: ax + b = 0 in ZN
Solution x = -b a-1 in ZN
我们可以通过扩展欧几里得算法求a得逆
先讲这么多后面得有空再补
参考链接：
https://www.bilibili.com/video/BV1Ht411w7Re?from=search&seid=6920352408663749476