0


密码学基础知识-数论(从入门到放弃)

数论知识

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


文章目录


简介

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

  • 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 = 2
646+114
646 = 5114+76
114 = 1
76+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 )


本文转载自: https://blog.csdn.net/qq_43589852/article/details/127411431
版权归原作者 小熊的学习笔记 所有, 如有侵权,请联系我们删除。

“密码学基础知识-数论(从入门到放弃)”的评论:

还没有评论