欧几里算法和扩展的欧几里得算法

欧几里得算法

算法简介

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

算法流程

举个栗子：

算法实现

关于欧几里得算法的实现可以适应递归和迭代两种思路，下面我们依次进行介绍：

迭代思路：适应while循环判断并辗转相除。

unsigned int Gcd(unsigned int M,unsigned int N)
{
    unsigned int Rem;
    while(N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}

递归思路：通过递归的方法实现辗转相除

unsigned int MaxCommonFactor(int a,int b)
{
    if(a % b == 0)
        return b;
    return MaxCommonFactor(b, a % b);
}

同时提供python的代码实现方法：

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

扩展欧几里得算法

算法简介

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。

通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

算法流程

欧几里得算法求取最大公因子

设整数a,b不同时为零，则存在一对整数m,n，使得gcd(a.b) = am+bn

2. 推出相邻式子的x和y关系

首先已知：gcd(a，b) = ax+by和gcd(a,b)=gcd(b,a%b)

其中：a%b=a-(a//b)*b //指取商的整数部分

根据：gcd(a,b)=ax+by=gcd(b,a%b) = bx’+(a-(a//b)*b)y’ = ay’+b(x’– a//by’)

注意：上式是关于两个相邻的关系得出的，即x和y为上面的式子，x’和y’为下面的式子。我们可以通过下面的式子求取上面式子的x,y值。

推得：

x = y’
y = x’ – a//b*y’

扩展欧几里得算法

所谓扩展欧几里得算法就是将上文提到的相邻式关系推广到多式子，而后由下向上依次求解。

注意：初始的x’ = 1,y’=0.

代码实现

使用代码实现算法，思路很简单：利用代码将推得的数学公式实现即可。所以最重要的还是公式的推导。

递归思路：每一次递归都会得出那一层公式的x,y,gcd。

#扩展欧几里得算法 
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

递归C语言：

#include<stdio.h>
long exEuclid(long a, long b, long &x, long &y) {
/***********************Begin**************************/

   if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int res = exEuclid(b,a % b, x, y);//递归方式求解
    int t=x;
    x=y;
    y = t-a/b * y;
    return res;

/*************************End**************************/
}
int main() {
	long a, b, x=0, y = 0, t;
	scanf("%ld %ld", &a, &b);  //测试集输入a、b，要求exEuclid函数的输出与a、b输入的顺序无关
	if(a > b) {
		t = a;
		a = b;
		b = t;
	}
	printf("%ld %ld %ld", x, y, exEuclid(a, b, x, y)); 
	//使得函数exEuclid返回gcd(a,b),依次输出x、y、gcd，使得等式a*x+b*y=gcd(a,b)
	return 0;

乘法逆元的求解

何为乘法逆元

乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a’=a’×a=e，其中e为该群的单位元。

求解思路

乘法逆元的求解可以适应扩展欧几里得算法得到。

前面我们得到：gcd(a,b) = ax+by,而求解a关于b的逆元即为：ax = 1 mod b,即ax = bk+1，x就是a的逆元。

代码实现

迭代思路：注意判断输入的大小，以使用不同的系数、

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)

有限域运算

有限域简介

加法运算

乘法运算

X乘法

注：x乘法可以将复杂的多项式乘法分解为简单的多个x乘法相加的形式，可以很大程度上简化计算。其中多项式加法就是按位异或。

代码实现

先是x乘法的实现：

#include <stdio.h>
#include <stdlib.h>
unsigned char XTIME(unsigned char x) 
{
//*******************Begin*******************
    unsigned char temp, result;
    int x1 = 0x1b;  // 特征多项式呀
    temp = x << 1;
    if (x > 64)  // 最高位为1
    {
        result = temp ^ x1;  // 按位异或
        return result;
    }
    else      // 最高位不为1
        return temp;

    
//*********************End********************
}

int main()
{
	unsigned char a;
	scanf("%x",&a);
	printf("0x%x\n",XTIME(a));
	return 0;
}

再是多项式乘法实现：

#include<stdio.h>

unsigned char XTIME(unsigned char x) {
//*******************Begin*******************
  return ((x << 1) ^ ((x & 0x80) ? 0x1b : 0x00));  

//********************End********************
}

unsigned char multiply(unsigned char a, unsigned char b) {
//*******************Begin*******************
    unsigned char temp[8] = { a };  
    unsigned char tempmultiply = 0x00;  
    int i = 0;  
    for (i = 1; i < 8; i++) {  
        temp[i] = XTIME(temp[i - 1]);  
    }  
    tempmultiply = (b & 0x01) * a;  
    for (i = 1; i <= 7; i++) {  
        tempmultiply ^= (((b >> i) & 0x01) * temp[i]);  
    }  
    return tempmultiply;  
//********************End********************
}

int main() {
    unsigned char array[20];
    scanf("%x%x",&array[0],&array[1]);
    unsigned char q=array[0];
    unsigned char w=array[1];
    printf("%x\n", multiply(q, w));
    return 0;
}

中国剩余定理

定理简介

代码实现

# -*- coding: UTF-8 -*-
def Get_Mi(m_list, M):  # 获取所有的Mi
    M_list = []
    for mi in m_list:
        M_list.append(M // mi)
    return M_list


def Get_ei_list(M_list, m_list):  # 取所有的Mi的逆元
    ei_list = []
    for i in range(len(M_list)):
        ei_list.append(Get_ei(M_list[i], m_list[i])[0])
    return ei_list


def Get_ei(a, b):  // 使用扩展欧几里得算法求解逆元
    # 计算ei

    if 0 == b:
        x = 1
        y = 0
        q = a
        return x, y, q
    xyq = Get_ei(b, a % b)
    x = xyq[0]
    y = xyq[1]
    q = xyq[2]
    temp = x
    x = y
    y = temp - a // b * y
    return x, y, q


def crt(a_list, m_list):
    # 计算中国剩余定理，返回计算结果
    M = 1  # M是所有mi的乘积
    for mi in m_list:
        M *= mi
    Mi_list = Get_Mi(m_list, M)
    Mi_inverse = Get_ei_list(Mi_list, m_list)
    x = 0
    for i in range(len(a_list)):  # 开始计算x
        x += Mi_list[i] * Mi_inverse[i] * a_list[i]
        x %= M
    return x

if __name__ == '__main__':
    a_list = list(map(int, input().split(",")))
    m_list = list(map(int, input().split(",")))
    print(crt(a_list, m_list))

素性检验

素性检验简介

素性检验就是判断一个数算法为素数。

在密码学算法中我们往往会选取一个素数，如何判断选取的数是素数呢？下面我们介绍几种简单的方法及其代码实现。

求余法

根据素数的定义，除了能被1和它本身整除而不能被其他任何数整除的数。根据素数定义只需要用2到n-1
去除n，如果都除不尽，则n是素数，否则，只要其中有一个数能整除则n不是素数.

代码实现：

改进算法:n不是素数，则n可表示为a*b，其中2≤a≤b≤n-1,则a， b中必有一个数满足：1<x≤sqrt(n)，因而，只需要用2~sqrt(n)去除n，这样就得到一个复杂度为O(sqrt(n))的算法。

代码实现：

def is_prime(num):
    if num > 1:
        if num == 2:
            print("Yes")
            return 1
        if num % 2 == 0:
            print("No")
            return 0
        for i in range(3, int(math.sqrt(num) + 1), 2):
            if num % i == 0:
                print("No")
                return 0
        print("Yes")
        return 1
    print("No")
    return 0

艾托拉斯筛法

将素数预先保存到一个素数表中，当判断一个数是否为素数时，直接查表即可。

其实现步骤如下:

找出sqrt(100)内是素数[2,3,5,7]
（2）去掉2的倍数值
（3）去掉3的倍数值
（4）去掉5的倍数值
（5）去掉7的倍数值
（6）删除1

代码实现：

def Evidence(number):
    p=[2,3,5,7]  # 为小素数集合
    q=[]                # 用于存储全部的数，然后筛选
    for i in range(8,int(math.sqrt(number))+1):   # 找开方后范围的质数
        flag=0
        for j in range(2,i): 
            if i%j==0:
                flag=1
                break
        if flag==0:
            p.append(i)

    for k in range(2,number+1): # 全部的数，然后进行筛选
        q.append(k)
    for i in p:
        for j in q:
            if j % i == 0://去除倍数值

                q.remove(j)
    for i in range(len(q)):
        p.append(q[i])
    print(p)

并发编程判断

利用并发编程来进行素数的判断，可以一次判断很多数。

代码如下：


from concurrent.futures import ProcessPoolExecutor
import math

# 素性判断函数，求余法
def is_prime(num):  
    if num > 1:
        if num == 2:
            return True
        if num % 2 == 0:
            return False
        for x in range(3, int(math.sqrt(num) + 1), 2):
            if num % x == 0:
                return False
        return True
    return False

# 通过调用is_prime，设计并发函数实现对多个大素数的判断
def main():
    with ProcessPoolExecutor() as exeu:
        for i in exeu.map(is_prime, PRIMES):
            print(i)
            
if __name__ == '__main__':
    PRIMES=list(map(int,input().split(",")))
    main()