RSA算法(二):数论知识(小学)

原创 小赛艇  2018-06-02 00:39  阅读 925 次

3 数论知识

本段以尽量简单的形式介绍与RSA相关的数论知识,其实带余除法、整除、因数、质数、合数、最大公因数、最小公倍数都是小学知识~

3.1 带余除法

很简单,就是我们一开始学习的除法,比如9÷2=4...1,把它写成乘法形式:9=2×4+1,再把它抽象成字母:

对于任意整数a,b(b≠0),存在唯一的整数q,r,使得:

a=b×q+r (0≤r<|b|)

其中q称作,b称作余数

然后我们规定一个新的运算mod,a mod b=r,即求a除以b的余数。

例 86 mod 9 = 5 (86=9×9+5)

3.2 整除

3.2.1 定义

整除顾名思义,就是当a除以b余数为0时,称b整除a,或a能被b整除。记为b|a。

例 81 mod 9 = 0,则81能被9整除。偶数能被2整除,奇数反之,0能被非0整数整除。

3.2.2 性质

整除的等价形式:a=kb (k为整数)

整除的基本性质:

(1) 若a|b, b|a 则 a=±b

例 3|-3,-3|3 3=-(-3)

(2) 若a|b, b|c 则 a|c

例 3|9,9|45 3|45

(3) 若a|b, a|c 则 a|bx+cy (x,y为任意整数)

例 3|27,3|54 3|(27*5+54*4)

这些性质都很简单理解,只需要用整除的等价形式a=kb即可证明,不做赘述。

3.3 因数

3.3.1 因数

对于整数x,能整除它的(正)整数称为因数,一般只考虑因数为正整数的情况。即a|x,则a是x的因数。

3.3.2 质数 合数

因数只有1和它本身的正整数称为质数,否则称为合数。1既不是质数也不是合数。

例 2,3,5,7,11,13都为质数,9,18,35为合数

3.3.3 分解质因数

把一个合数分解成几个质因数相乘,称为分解质因数。任意大于1的整数可以分解成质因数的形式:\(n=p_1^{a_1}p_k^{a_k}...p_k^{a_k}\)。

例 176=2^4×11^1

不考虑顺序问题,分解形式唯一。即大于1的整数a只能分解成\(n=p_1^{a_1}p_k^{a_k}...p_k^{a_k}\)这些质因数相乘,不能分解成另外一些质因数相乘。

3.3.3 最大公因数

即两个整数共有的最大因数,记为(a,b)。对于多个整数求最大公因数,可以先求其中两个整数的最大公因数,即(a,b,c)=((a,b),c)

例 32和28,32=2^5,有因数1,2,4,8,16,32 ,28=2^2×7,有因数1,2,4,7,14,28 ,则它们的最大公因数为4,所以(32,28)=4

可以使用辗转相除法、更相减损术来计算(a,b),也可以将a,b分解质因数计算(a,b)。

如果(a,b)=1,则称a与b互质

例 任意两个相邻的大于1的整数n,n+1互质

3.3.4 最小公倍数

即两个整数共有的倍数中最小的正数,记为[a,b]

例 25和15,25的部分倍数为50,75,100,15的部分倍数为15,30,45,60,75,则它们共有的最小倍数为75,所以[25,15]=75

对正整数a,b有(a,b)[a,b]=|ab|

例 25和15,(25,15)=5,[25,15]=75,25×15=375,5×75=375。即(25,15)[25,15]=25×15=375

所以要求两个整数的最小公倍数,先求最大公因数(a,b),再用|ab|除以(a,b)即可。

这篇文章复习了一下小学数论知识,接下来将会介绍"高级"一点的基础数论知识。

本文地址:https://xsaiting.com/rsa-2.html
版权声明:本文为原创文章,版权归 小赛艇 所有,转载请保留出处!
喜欢请点赞/打赏/分享这篇文章哦!

发表评论


表情