毕达哥拉斯素数

毕达哥拉斯质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开始,将每个素数的各个倍数都标记成合数。其原理如下图所示:

程序编码就是对数学逻辑的具体实现

为什么你的代码一坨坨?其实来自你有那么多为什么你要这样写代码!
为什么你的代码那么多for循环?因为没有合理的数据结构和算法逻辑。
为什么你的代码那么多ifelse?因为缺少设计模式对业务场景的运用。
为什么你的程序应用复杂对接困难?因为没有良好的系统架构拆分和规划。
为什么你的程序逻辑开发交付慢返工多?因为不具备某些业务场景的开发经验。
为什么你的程序展现都是看上去不说人话?因为没有产品思维都是程序员逻辑的体现。
最终,所有的这些不合理交织在一起,就是你能看到的一坨坨的代码!所以,要想把代码写好、写美,写到自己愿意反复欣赏,那么基本需要你有一定的:基础能力(数据结构、算法逻辑、设计模式)、应用能力(系统架构、开发经验)、拓展能力(产品思维),这三方面综合起来才能更好的开发程序。

数据结构:数组、链表、红黑树 算法逻辑:哈希、扰动函数、负载因子、拉链寻址、

其实我们所开发的业务程序,哪怕是CRUD也都是对数学逻辑的具体实现过程。只不过简单的业务有简单的数学逻辑、复杂的业务有复杂的数学逻辑。数学逻辑是对数据结构的使用,(例如:把大象装进冰箱分几步)合理的数据的结构有利于数据逻辑的实现和复杂程度。

在我们常用的API中,HashMap 就是一个非常好的例子,既有非常好的数据结构的使用,也有强大的数学逻辑的实现。为此也让 HashMap 成为开发过程中非常常用的API,当然也成为面试过程中最常问的技术点。

完善的产品设计需要有对付杠精的思维

如:树上10只鸟开一枪还剩下几只,你会想到什么

  1. 开枪人有没有幻觉?
  2. 枪是真的吗?
  3. 手抢是无声的吗?
  4. 枪声大吗?
  5. 这个城市打鸟犯不犯法?
  6. 确定那只鸟被打死了?
  7. 树上的鸟有没有聋子?
  8. 有没有被关在笼子里或者绑在树上的鸟?
  9. 旁边还有其他树吗?
  10. 鸟是不是真的?
  11. 有残疾或者飞不动的鸟吗?
  12. 打鸟的人眼睛花没花?
  13. 保证是10只吗?
  14. 有没有那种不怕死的鸟?
  15. 会不会一枪打死两只或者更多?
  16. 所有的鸟都可以自由活动飞离树以外吗?
  17. 打死以后挂在树上还是掉下来了?

汉明距离

汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如: 1011101 与 1001001 之间的汉明距离是 2。 2143896 与 2233796 之间的汉明距离是 3。 “toned” 与 “roses” 之间的汉明距离是 3。

汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。

对于固定的长度 n,汉明距离是该长度字符向量空间上的度量,很显然它满足非负、唯一及对称性,并且可以很容易地通过完全归纳法证明它满足三角不等式。 如果把a和b两个单词看作是向量空间中的元素,则它们之间的汉明距离等于它们汉明重量的差a-b。如果是二进制字符串a和b,汉明距离等于它们汉明重量的和a+b或者a和b汉明重量的异或a XOR b。汉明距离也等于一个n维的超立方体上两个顶点间的曼哈顿距离,n指的是单词的长度。 给予两个任何的字码,10001001和10110001,即可决定有多少个相对位是不一样的。在此例中,有三个位不同。要决定有多少个位不同,只需将exclusive OR运算加诸于两个字码就可以,并在结果中计算有多个为1的位。

曼哈顿距离

欧氏距离是人们在解析几何里最常用的一种计算方法,但是计算起来比较复杂,要平方,加和,再开方,而人们在空间几何中度量距离很多场合其实是可以做一些简化的。曼哈顿距离就是由 19 世纪著名的德国犹太人数学家赫尔曼·闵可夫斯基发明的(图 1)。


赫尔曼·闵可夫斯基


赫尔曼·闵可夫斯基在少年时期就在数学方面表现出极高的天分,他是后来四维时空理论的创立者,也曾经是著名物理学家爱因斯坦的老师。

曼哈顿距离也叫出租车距离,用来标明两个点在标准坐标系上的绝对轴距总和。

欧氏距离里的距离计算:

曼哈顿距离中的距离计算:

曼哈顿距离中的距离计算公式比欧氏距离的计算公式看起来简洁很多,只需要把两个点坐标的 x 坐标相减取绝对值,y 坐标相减取绝对值,再加和。

从公式定义上看,曼哈顿距离一定是一个非负数,距离最小的情况就是两个点重合,距离为 0,这一点和欧氏距离一样。曼哈顿距离和欧氏距离的意义相近,也是为了描述两个点之间的距离,不同的是曼哈顿距离只需要做加减法,这使得计算机在大量的计算过程中代价更低,而且会消除在开平方过程中取近似值而带来的误差。不仅如此,曼哈顿距离在人脱离计算机做计算的时候也会很方便。

胡不归问题

胡不归问题,是一个非常古老的数学问题,曾经是历史上非常著名的“难题”。近年来陆续成为各地中考模拟题的小热门考点,学生不易把握,今天给大家普及讲解一下。

话说,从前有一小伙子外出务工,某天不幸得知老父亲病危的消息,便立即赶路回家.小伙子略懂数学常识,考虑到“两点之间线段最短”的知识,就走布满沙石的路直线路径,而忽视了走折线虽然路程多但速度快的实际情况,当赶到家时,老人刚咽了气,小伙子追悔莫及失声痛哭.邻居告诉小伙子说,老人弥留之际不断念叨着“胡不归?胡不归?…”

这个问题引起了人们的思索,小伙子能否节省路上时间提前到家?如果可以,他应该选择一条怎样的路线呢?这就是流传千百年的“胡不归问题.

如图,A是出发点,B是目的地,直线AC是一条驿道,而驿道靠目的地一侧全是砂土,为了选择合适的路线,根据不同路面速度不同(驿道速度为a米/秒,砂土速度为b米/秒),小伙子需要在AC上选取一点D,再折往至B.

上述数学解释用到了三角函数知识将两个线段的系数权重都化为1,从而降低了求最值难度。聪明的同学或许一下就发现转化成了我之前讲过的“将军饮马(小河取水)”模型,进而作对称求得最值。