加密相关算法

欧拉函数:

定义:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n).则

欧拉定理:

定义:如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:a^φ(n)%n=1

费马小定理:

定义:假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成:a^(p-1)%n=1

模反元素(乘积逆元):

定义:两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1:a*b%n=1,这时,b就叫做a的”模反元素”。

RSA算法原理:

原理:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥

欧几里德算法(gcd):

又称辗转相除法,用于计算两个整数a,b的最大公约数

扩展欧几里得算法(egcd):

基本思路:对于不全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by

https://blog.csdn.net/qwe6112071/article/details/53576584