首页  

密码学数论基础     所属分类 cryptography 浏览量 91
一、整除
定义:
a、b是两个整数,b≠0 ,如果存在一个整数m使等式a=m*b成立,则称b整除a,记为b|a,a是被除数,b是除数

性质:
·若b|a,c|b,则c|a;
·若b|g,b|h,则对任意整数m,n有b|(mg+nh)

二、素数
定义:
一个大于q且只能被1和它本身整除的整数,称为 素数(质数)否则称为 合数

性质:
·若p是素数,p|ab,则p|a或p|b。
·若p是素数,a是任意整数,则有p|a(整除)或gcd(p,a)=1(互素),即素数与任意数之间可能是整除或互素的关系

三、最大公约数
定义:
最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个

性质:
欧几里得定理
设a,b,c,q是任意不全为0的整数,且
a=qb+c,其中q是整数,则有:
◆gcd(a, b)= gcd(b, c)
◆或写成gcd (a, b)=gcd (b, a mod b)
即被除数和除数的最大公因子与除数和余数的最大公因子相同。例如:
◆gcd(18, 12)= gcd(12, 6) = gcd(6, 0)=6
◆gcd(11, 10)= gcd(10, 1)= gcd(1, 0)=1

四、模运算与同余
定义:
模运算:设n是正整数,a是整数, 如果用n除a,得商为q,余数为r,即a =qn+r, 0Sr m|(a-b)
a ≡ b(mod m),b ≡ c(mod m),则a ≡ c(mod m)

五、欧拉函数
定义:
n是一个正整数,小于n且与n互素的正整数的个数称为n的欧拉函数,记为φ(n) 
如小于6且与6互素的数只有1和5,因此φ(6)=2

性质:
若n是素数,则φ(n)=n-1;
若n=pq,p、q是素数且p≠q,则φ(n)=(p-1)(q-1);
若gcd(m,n)=1,则φ(m)φ(n)=φ(mn)
若n=p₁a₁p₂a₂…pa,其中p₁,p₂,…,p为素数,a₁,a₂,…,a为正整数,则有:φ(n) = n(1-1/p₁)(1-1/p₂)…(1-1/p)

欧拉定理:
若a和n都是正整数,且gcd (a, n)=1,则有aφ(n) mod n=1,即aφ(n)≡1(mod n)

欧拉定理的应用:求解 3102 mod 11
解:因为gcd(3,11)=1,则有310mod 11=1
所以 310*10 mod 11=110=1,3100+2 mod 11=32 mod 11=9
推论:若a与n互素,则a与aφ(n)-1互为乘法逆元

六、费马小定理
定义:
如果p是一个质数,而整数a不是p的倍数,则有a(p-1)≡1(mod p)

七、扩展欧几里得定理
定义:
对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b) = ax+by

·当b=0时,gcd(a,b)=a,此时x=1,y=0;
·当ab!=0时,设ax₁+by₁=gcd(a,b),欧几里得原理有gcd(a,b)=gcd(b,a%b)
则有,gcd(b,a%b)=bx₂+(a%b)y₂
即bx₂+(a%b)y₂=ax₁+by₁
ax₁+by₁=bx₂+(a-[a/b]*b)y₂=x₂b+y₂a-[a/b]y₂b=y₂a+(x₂-[a/b]y₂)b
可以得到:x₁=y₂,y₁=x₂-[a/b]y₂
将上面思想以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归结束

八、乘法逆元
定义:
如果满足下列等式,则称x是a模p的乘法逆元:ax≡1 (mod p)且gcd(a,p)=1(a与p互质),通常记为:x = a-1 mod p
一个数可能存在多个乘法逆元,也可能没有乘法逆元

乘法逆元的求法:
费马小定理
当p为质数时,由费马小定理得a(p-1)≡1(mod p),为了求ax≡1 (mod p)中a模p的乘法逆元x,因为a与p互质,a*ap-2≡1 (mod p),则x=ap-2
扩展欧几里得
ax≡1 (mod p)可以写成ax+py=1的形式,则可以用扩展欧几里得算法解出二元一次方程解出x

九、中国剩余定理
一般来讲,p₁,…,p为素数
k ≡ a₁(mod p₁)
k ≡ a₂(mod p₂)
…
k ≡ a(mod p)
有解
﹛x₁ ≡ 1( p₁),x₁ ≡ 0( p₂),…,x₁ ≡ 0( p) ﹜
﹛x₂ ≡ 0( p₁),x₂ ≡ 1( p₂),…,x₂ ≡ 0( p) ﹜
…
﹛x ≡ 0( p₁),x ≡ 1( p₂),…,x ≡ 1( p) ﹜

k = a₁x₁ + a₂x₂ + … + ax (mod p₁p₂…p)

例如:
k ≡ a(mod 3)
k ≡ b(mod 4)
k ≡ c(mod 5)
→k = ax + by + cz (mod 105)
﹛x ≡ 1(3),x ≡ 0(5),x ≡ 0(7) ﹜ x = 70
﹛y ≡ 0(3),y ≡ 1(5),y ≡ 0(7) ﹜ y = 21
﹛z ≡ 0(3),z ≡ 0(5),z ≡ 1(7) ﹜ z = 15
→k = 70a + 21b + 15c (mod 105)

十、威尔逊定理
(p-1)! ≡ -1(mod p),(p-2)! mod p =1 ,p为质数

上一篇     下一篇
快乐因子多巴胺分泌排行

康波周期

密码学基础

k8s知识点

k8s知识点总结

docker知识点总结