毕达哥拉斯素数

毕达哥拉斯质bai数是指可以表示为 4n + 1 形式的质数,若直角三角形的三边均为整数,斜边为质数,其斜边的边长即为毕达哥拉斯质数.
前几个毕达哥拉斯质数为
5,13,17,29,37,41,53,61,73,89,97,101,109,113,… (OEIS中的数列A002144).
费马平方和定理陈述,毕达哥拉斯质数可以表示为二个平方数的和,其他质数除了2以外(2=1^2+1^2)都不能表示为二个平方数的和.毕达哥拉斯质数及2会在高斯整数的范数中出现,其他的质数不会是高斯整数的范数.
毕达哥拉斯质数可以表示为一个奇数的平方数与一个偶数的平方数的和:
毕达哥拉斯质数是可以表示为a^2+4b^2形式的质数.
依照二次互反律陈述,若p及q为奇质数,其中至少有一个为毕达哥拉斯质数,则 p是模q的二次剩余的充份必要条件是q是模p的二次剩余 .相反的,若p及q都不是毕达哥拉斯质数,则p是模q的二次剩余的充份必要条件是q不是模p的二次剩余.−1是是模p的二次剩余的充份必要条件是p是毕达哥拉斯质数(或2).
在p为毕达哥拉斯质数的域Z/p中,多项式x^2 = -1有二个解.

素数部分定理

1.素数本身只能被自身整除。也就是质数的约数只有两个,即1和本身。
2.所有大于3的素数,都可以用6n-5 和6n-1表达,或6n+1和6n+5来表示。
3.若”k”不是”6xy+x-y”的方程解,也就是”k≠6xy+x-y”,那么”6k-1″一定是个素数。 4.若”k”不是”6xy+-(x+y)”的方程解,也就是”k≠6xy+-(x+y)”,那么”6k+1″一定是个素数。
5.由3.和4.假设,素数集合是由两条元素不重复的独立集合。

6.质数的个数公式π(n)是不减函数。且素数的分布个数接近于x/ln (x),这是素数定理。
7.素数本身是不可能有传统意义上的通项公式。
8.任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,当代入1时候这种分解是无限的,去掉1时分解则是唯一的。
9.质数的个数是无限的。
10.所有大于10的质数中,个位数只有1,3,7,9。

11.若n为正整数,在n^2到(n+1)^2之间至少有一个质数。
12.若n为大于或等于2的正整数,在n到n!之间至少有一个质数
13.若质数p为不超过n(n≥4)的最大质数,则p>n/2。
14.两个连续素数最大间隔可以任意大。
15.任意大于5的奇数都可以表示为三个素数之和。

加密中数论基础知识,RSA加密算法及证明

记法

设n为正整数,a和b为整数,若a和b被n除后所得余数相同,
称a和b模n同余,记为a≡b(mod n);或  a≡b(% n)
此式被称为同余式。

或表达为:a % n =b % n  或 a mod n =b mod n;

若n能整除a则同余式表示为a ≡ 0(mod n)。

欧拉函数

对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数,记作φ(N)。即欧拉函数。

欧拉定理:

若N>2; a与N互质,则a^(φ(N))  ≡ 1 (mod N )

欧拉函数的性质:

(1)   p^k型欧拉函数:

若N是质数p(即N=p), φ(N)= φ(p)=p-p^(k-1)=p-1。

若N是质数p的k次幂(即N=p^k),φ(N)=p^k-p^(k-1)=(p-1)p^(k-1)。

(2)  mn型欧拉函数

若m,n互质,φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

(3)  特殊性质:

若n为奇数时,φ(2n)=φ(n)。

费马小定理:

设任意整数a和素数p互素 ,则 a^p-1 ≡ 1(mod p)

运算规则

模运算与基本四则运算有些相似,但是除法例外。其规则如下:

 (a + b) % p = (a % p + b % p) % p (1)

 (a - b) % p = (a % p - b % p) % p  (2)

 (a * b) % p = (a % p * b % p) % p (3)

 (a^b) % p =   ( (a % p)^b ) % p     (4)

结合率:

((a+b) % p + c) % p = (a + (b+c) % p) % p (5)

 ((a*b) % p * c)% p = (a * (b*c) % p) % p   (6)

交换率:

 (a + b) % p = (b+a) % p (7)

 (a * b) % p = (b * a) % p (8)

分配率:

 ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p (9)

重要定理

若a≡b (% p),则对于任意的c,都有(a + c) ≡ (b + c) (%p);(10)

若a≡b (% p),则对于任意的c,都有(a * c) ≡ (b * c) (%p);(11)

若a≡b (% p),c≡d (% p),则 (a + c) ≡ (b + d) (%p),(a - c) ≡ (b - d) (%p),

(a * c) ≡ (b * d) (%p),(a / c) ≡ (b / d) (%p); (12)

若a≡b (% p),则对于任意的c,都有ac≡ bc (%p); (13)

RSA中重要的推论

m 和 n 是互质的正整数,则:

(a^m) %n  =  ((a%n)^m) %n

推论证明

   a^m % n 
   =a*a ^(m-1) %n
   =(a%n) *(a ^(m-1) %n ) % n  //后续不断展开,一直至a ^0,即共有m项
   =((a%n)^m) %n 

推论中举例:

比如:2^3 mod 5
 = (2 mod 5)^ 3 mod5
 = 8 mod5
 = 3
还有:3^3 mod 2
= (3 mod 2) ^3  mod 2
=1^3 mod 2
=1

加密思路:加密本质上是对加密内容的字节数组进行加密。不是对字符的本身进行加密。这样,整数对整数就可以进行相关的变换,即加密了。

比如:"I love Rust,Julia & Python, they are so cool! "的字节数组为:
[73, 32, 108, 111, 118, 101, 32, 82, 117, 115, 116, 
44, 74, 117, 108, 105, 97, 32, 38, 32, 80, 121, 116, 
104, 111, 110, 44, 32, 116, 104, 101, 121, 32,
 97, 114, 101, 32, 115, 111, 32, 99, 111, 111, 108, 33, 32]

RSA加密算法为:

(1) 取两个大素数p,q (保密);
(2) 计算 n=p*q (公开), φ(n)=(p-1)*(q-1) (保密);
(3) 随机选取整数e,满足 gcd(e, φ(n))=1 (e与φ(n)互素)(公开);
(4) 计算 d 满足 d*e≡1 (mod φ(n)) (保密); (d为e的逆元,可通过扩展的欧几里得算法进行求解)
(5) {e,n}为公钥,{d,n}为私钥,也可以用{e,d}表示密钥对
(6) m为加密内容(如73),此时c为加密后的密文;
       加密时 c = m^e mod n 
       解密时 m = c^d mod n
(7) m为签名内容,
       签名时c = m^d mod n ;
       解密时 m = m^e mod n

为什么RSA算法能保证其安全性?

要破解m =>
必须知道  d或e =>
必须知道  φ(n) =>
必须知道  p及q;  =>
必须能破解 n=p*q =>
大质数因式分解的难度 => 公认

RSA证明

主要要证明m是否c^d mod n。由c = m^e mod n 。设M =m^e
证式
 =    c^d mod n
 =  (m^e mod n )^d mod n 
 =    (M mod n) ^d mod n
 =    M^d mod n                   //见上面的推论
 =    m^(d*e )mod n ; 
因为 d*e≡1 (mod φ(n)) 
得到:d*e =k *φ(n) +1 ; k是正整数。
上面证式还有,
 =    m^(k *φ(n) +1 ) mod n
 =    m^(k *φ(n))*m  mod n     // 
 =    (m^(k *φ(n))mod  n ) *(m mod n)  mod n         //  乘法 
 =    1 * m mod n  // 由欧拉定理
 =    m
 证毕。
 所以解密的公式是对的。

埃拉托斯特尼筛法

求解第N个素数,求第 10,0000、100,0000、1000,0000 … 个素数(要求精确解)。

埃拉托斯特尼筛法(Sieve of Eratosthenes),这是一种非常古老但是非常有效的求解𝑝𝑛pn的方法,其原理非常简单:从2开始,将每个素数的各个倍数都标记成合数。其原理如下图所示: