第四章——密码学的数学引论

一.数论

1.素数

 200以内的素数：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

算术基本定理：

任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1＜P2＜P3…＜Pt是素数，其中αi>0.

eg. 91 = 7 × 13 ; 3600 = 24 × 32 × 52

根据定理，17是素数，18不是素数。

欧几里得算法——求最大公约数

基本思想：

为了求两个正整数a,b的最大公约数，首先将两个正整数中较大者赋给 a ，较小者赋给b, 然后循环使用R=a mod b ， 直到模运算的余数b=0结束，则前一个余数就是二者的最大公约数。

证明：a=kb+r≡r mod b    →  a mod b=a-kb 

          设d是a，b的公因子，即d|a , d|b, 所以d|kb.

          由d|a和d|kb，得d|(a mod b)，   故d是b和a mod b的公因子。

a和b的公因子集合与b和(a mod b)的公因子集合相同，故它们两组的最大公因子也相同。 

                                  gcd(55,22)=gcd(22,11)=gcd(11,0)=11
                                  gcd(11,10)=gcd(10,1)=1

                                                   gcd(1970,1066)的计算过程

因此，gcd(1970,1066)=2

算法实现：

def gcd(a,b):
# *************begin************#
    if a<b:
        t=a
        a=b
        b=t
    while a%b!=0:
        temp=a%b
        a=b
        b=temp
    return b
 
# **************end*************#
a = int(input("请输入值a:"))
b = int(input("请输入值b:"))
r = gcd(a,b)
print(r)

扩展的欧几里得算法——求乘法逆元

参考文章：扩展欧几里得算法求逆元python代码实现(含递归与非递归算法)_扩展欧几里得算法 非递归-CSDN博客

基本思想 ：

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。因此，有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数；然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的一组整数特解。

以下是扩展欧几里得算法的python实现：

算法实现：

1.递归
 

#扩展欧几里得算法 
def ext_gcd(a, b):    
    if b == 0:          
        return 1, 0, a     
    else:         
        x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)        
        x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立         
        return x, y, gcd
 

 2.非递归

print("请输入一个整数：")
a = int(input())
print("请输入模？")
m = int(input())
 
if a < m:
    a, m = m, a
    x1, x2,x3= 1, 0, a
    y1, y2,y3= 0, 1, m
    while y3 != 0:
        Q = x3//y3
        t1, t2, t3 = x1 - Q*y1, x2 - Q*y2, x3 - Q*y3
        x1, x2, x3 = y1, y2, y3
        y1, y2, y3 = t1, t2, t3
    print(x2)
else:
    x1, x2, x3 = 1, 0, a
    y1, y2, y3 = 0, 1, m
    while y3 != 0:
        Q = x3 // y3
        t1, t2, t3 = x1 - Q*y1, x2 - Q*y2, x3 - Q*y3
        x1, x2, x3 = y1, y2, y3
        y1, y2, y3 = t1, t2, t3
    print(x1)
 

以下是两种方法的运行验证结果

说明以上代码正确有效。 

中国剩余定理

基本思想

        原理

注意：若x0为上述同余方程组的解，则x0¢=x0+105*k(k∈z) 也为上述同余方程组的解。

     有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组

  

以方程（1）为对象，相当于解一个这样的同余方程  35y≡1(mod 3)，为什么呢？

原因是，从（1）的模数及条件知，x应同时是5和7的倍数，即应是35的倍数，于是可以假设x＝35y有：

  35y≡1(mod 3) 相当于35y=(33y+2y)=2y≡1(mod)3
解出y=2（mod3）
于是x=35*2 =70(mod105)

类似地得到（2）、（3）方程的模105的解21、15。

例题：

x≡1 mod 2

x≡2 mod 3

x≡3 mod 5

解：

M=2×3×5=30，记Mj=M/mj，则

M1=15, M2=10, M3=6

15y1≡1mod2,     y1=1

10y2≡1mod3,     y2=1

 6y3≡1mod5,      y3=1

故, x=1×15×1+2×10×1+3×6×1=53≡23mod30

算法实现：

import math
 
 
def Get_Mi(m_list, m):
    M_list = []
    for mi in m_list:
        M_list.append(m // mi)
    return M_list
 
 
def Get_resMi(M_list, m_list):
    resM_list = []
    for i in range(len(M_list)):
        resM_list.append(Get_ni(M_list[i], m_list[i])[0])
    return resM_list
 
 
def Get_ni(a, b):
    if b == 0:
        x = 1
        y = 0
        q = a
        return x, y, q
    ret = Get_ni(b, a % b)
    x = ret[0]
    y = ret[1]
    q = ret[2]
    temp = x
    x = y
    y = temp - a // b * y
    return x, y, q
 
 
def result(a_list, m_list):
    for i in range(len(m_list)):
        for j in range(i + 1, len(m_list)):
            if 1 != math.gcd(m_list[i], m_list[j]):
                print("不能直接利用中国剩余定理")
                return
    m = 1
    for mi in m_list:
        m *= mi
    Mi_list = Get_Mi(m_list, m)
    Mi_inverse = Get_resMi(Mi_list, m_list)
    x = 0
    for i in range(len(a_list)):
        x += Mi_list[i] * Mi_inverse[i] * a_list[i]
        x %= m
    return x
 
 
if __name__ == '__main__':
    print("请输入ai，以逗号分隔：")
    a_list = list(map(int, input().split(",")))
    print("请输入mi，以逗号分隔：")
    m_list = list(map(int, input().split(",")))
    print("最终结果为：")
    print(result(a_list, m_list))

二.群论

        

1.群的概念:

        是由一个非空集合G组成，在集合G中定义了一个二元运算符“*”，并满足以下性质的代数系统，记为｛G, * ｝

1.封闭性                             *为乘法时，称为乘法群   逆元（a-1）

2.服从结合律                     *为加法时，称为加法群   逆元（-a）

3.有单位元

4.逆元

注：如果是可交换的，则成称为Abel群

2.群的基本概念

 

3.群的性质

三.有限域理论