精华内容
下载资源
问答
  • 介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
  • 当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
  • 包括完整的c语言实现扩展的欧几里得算法代码截图和相关代码说明以及程序截图
  • 算法合集之《欧几里得算法的应用》.pdf
  • 欧几里得算法

    2020-06-21 11:53:49
    欧几里得算法欧几里得算法自然语言的描述概念理解 欧几里得算法自然语言的描述 计算两个非负整数p和q的最大公约数:若q是0,则最大公约数为p。否则,将p除以q得到余数r,p和q的最大公约数即为q和r的最大公约数。 ...

    欧几里得算法自然语言的描述

    计算两个非负整数p和q的最大公约数:若q是0,则最大公约数为p。否则,将p除以q得到余数r,p和q的最大公约数即为q和r的最大公约数。

    概念理解

    1. 最大公约数

    最大公约数:也称最大公因数,是指两个或两个以上的整数之间存在的最大共有约数,也叫除数。例如:
    a=8 b=12
    则a的约数分别为:1,2,4,8
    b的约数分别为:1,2,3,4,6,12
    经过比较可得a与b的最大公约数为4
    注意: 0和任何数的最大公约数都是这个数本身

    例如:a=0,b=12,则它们的最大公约数为12

    1. 辗转相除法

    辗转相除法:又称欧几里得算法,其核心是:

    两个整数的最大公约数= 较小的那个数与两数相除的余数最大公约数
    由此可得以下假设:
    假设有两个数a,b,且a>b,则a和b的最大公约数等于b与a和b相除的余数的最大公约数
    知道余数为0,则根据第一点最大公约数中的注意项,我们就能得到其最大公约数


    由此不断反复,我们就可以得到一个迭代算法思想

    3.举例

    假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的:
    1997 / 615 = 3 (余 152)
    615 / 152 = 4(余7)
    152 / 7 = 21(余5)
    7 / 5 = 1 (余2)
    5 / 2 = 2 (余1)
    2 / 1 = 2 (余0)
    至此,最大公约数为1
    以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。

    4.证明

    证法一:
    a可以表示成a = kb + r(a,b,k,r皆为正整数,且r<b),则r = a mod b
    假设d是a,b的一个公约数,记作d|a,d|b,即a和b都可以被d整除。
    而r = a - kb,两边同时除以d,r/d=a/d-kb/d=m,由等式右边可知m为整数,因此d|r
    因此d也是b,a mod b的公约数
    假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。
    进而d|a.因此d也是a,b的公约数
    因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

    证法二:
    假设c = gcd(a,b),则存在m,n,使a = mc, b = nc;
    令r = a mod b,即存在k,使r = a-kb = mc - knc = (m-kn)c;
    故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn);
    则c为n与m-kn的公约数;
    假设d = gcd(n,m-kn), 则存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;
    故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc;
    由于gcd(a,b) = c, 故d = 1;
    即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;
    故得证gcd(a,b) = gcd(b,a mod b).## 功能快捷键

    5.使用程序代码编写如下:

    public static int gcd(int p,int q){
    	if(q == 0) return p;
    	int r = p % q;
    	return gcd(q,r);
    }
    
    展开全文
  • 密码学基础系列: 基于整数的欧几里得算法和扩展欧几里得算法 扩展域 GF(2n)GF(2^n)GF(2n) 上的多项式运算 扩展域 GF(2n)GF(2^n)GF(2n) 上的欧几里得算法和扩展欧几里得算法

    欧几里得算法

    图片来源: 随便谷歌的一个图片
    图片地址: https://jason-chen-1992.weebly.com/uploads/1/0/8/5/108557741/euclidean_3_orig.jpg

    密码学基础系列:

    • (一) 基于整数的欧几里得算法和扩展欧几里得算法
    • (二) 扩展域 G F ( 2 n ) GF(2^n) GF(2n) 上的多项式运算
    • (三) 扩展域 G F ( 2 n ) GF(2^n) GF(2n) 上的欧几里得算法和扩展欧几里得算法


    求两个整数的最大公约数,以及求整数的乘法逆元是密码学中最基本的算法。

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

    欧几里得算法(Euclidean Algorithm),即辗转相除算法,是求两个整数最大公约数(GCD, Greatest Common Devisor)最常用和高效的办法。

    关于辗转相除的原理和证明这里不再赘述,推荐参考:

    1. 《数论概论》原书第3版,第5章,整除性与最大公因数
    2. 《密码编码学与网络安全》第七版,第2.2节,欧几里得算法
    3. 《深入浅出密码学》,第6.3.1节,欧几里得算法

    以下是源码实现的递归和非递归版本。

    1. 递归版本

    /**
     * @description: 使用欧几里得算法(辗转相除)求最大公约数的递归版本
     * @param {int} a 整数a
     * @param {int} b 整数b
     * @return {*} 返回整数 (a, b) 的最大公约数
     */
    int int_gcd(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
        else
        {
            return int_gcd(b, a % b);
        }
    }
    

    2. 非递归版本

    /**
     * @description: 使用欧几里得算法(辗转相除)求最大公约数的非递归版本
     * @param {int} a 整数a
     * @param {int} b 整数b
     * @return {*} 返回整数 (a, b) 的最大公约数
     */
    int int_gcd(int a, int b)
    {
        int t;
    
        while (b != 0)
        {
            t = a % b;
            a = b;
            b = t;
        }
    
        return a;
    }
    

    为了和后面基于多项式的欧几里得算法求最大公因式区分,这里将函数命名为int_gcd,前缀 int 表示 integer

    2. 扩展欧几里得算法解线性方程 a x + b y = d = g c d ( a , b ) ax + by = d = gcd(a, b) ax+by=d=gcd(a,b)

    扩展欧几里得算法(Extend Euclidean Algorithm)的最大用途就是用于计算整数的乘法逆元。

    关于扩展欧几里得算法(EEA)的原理和和推导这里不再赘述,推荐参考:

    1. 《数论概论》原书第3版,第6章,线性方程与最大公因数
    2. 《密码编码学与网络安全》第七版,第2.3.6节,扩展的欧几里得算法
    3. 《深入浅出密码学》,第6.3.2节,扩展的欧几里得算法

    以下的源码基于扩展欧几里得算法实现求解线性方程:
    a x + b y = d = g c d ( a , b ) , 公式2.1 ax + by = d = gcd(a, b) \text{, 公式2.1} ax+by=d=gcd(a,b)公式2.1

    以下是源码实现的递归和非递归版本。

    1. 递归版本

    /**
     * @description: 使用扩展欧几里得算法(EEA)计算等式 a x ia + b x ib = gcd(a, b) 中的系数 ia, ib 和 gcd(a, b), 递归版本, 推导和证明参考: https://blog.csdn.net/lincifer/article/details/49391175
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @param {int} *ia 整数 a 的系数 ia
     * @param {int} *ib 整数 b 的系数 ib
     * @return {*} 返回整数 (a, b) 的最大公约数 gcd(a, b)
     */
    int int_gcd_ex(int a, int b, int *ia, int *ib)
    {
        int x, y;
        int q, r;
    
        if (b == 0)
        {
            *ia = 1;
            *ib = 0;
    
            return a;
        }
    
        r = int_gcd_ex(b, a % b, &x, &y);
    
        *ia = y;
        *ib = x - a / b * y;
    
        return r;
    }
    

    一般的书讲述扩展欧几里得算法(Extend Euclidean Algorithm)都是基于递推原理进行的。
    关于递归(非递推)版本的推导和证明,请参考参考:

    • https://blog.csdn.net/lincifer/article/details/49391175
      扩展欧几里得算法的递归证明

    2. 非递归版本

    /**
     * @description: 使用扩展欧几里得算法: Extend Euclidean Algorithm (EEA) 计算等式 a x ia + b x ib = gcd(a, b) 中的 ia, ib 和 gcd(a, b)
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @param {int} *ia 整数 a 的系数 ia
     * @param {int} *ib 整数 b 的系数 ib
     * @return {*} 返回整数 (a, b) 的最大公约数 gcd(a, b)
     */
    int int_gcd_ex(int a, int b, int *ia, int *ib)
    {
        int x, y, x0, y0, x1, y1;
        int q, r;
    
        /* 消除警告: "warning: ‘x’/‘y’ may be used uninitialized in this function" */
        x = y = 0;
    
        /* 初始化最初两项系数 */
        x0 = 1; y0 = 0;
        x1 = 0; y1 = 1;
    
        q = a / b;
        r = a % b;
    
        while (r != 0)
        {
            /* 计算当前项 x/y */
            x = x0 - q * x1;
            y = y0 - q * y1;
    
            /* 依次保存前两项到 x0/y0, x1/y1 */
            x0 = x1; x1 = x;
            y0 = y1; y1 = y;
    
            a = b;
            b = r; /* 前一次的余数 */
    
            q = a / b;
            r = a % b;
        }
    
        *ia = x;
        *ib = y;
    
        return b;
    }
    

    函数int_gcd_ex的返回值和int_gcd一样,都返回其参数 ab 的最大公约数,不同的是,除了返回最大公约数之外,还通过指针参数返回线性方程 2.1 中的 xy值。

    二者的函数原型如下:

    int int_gcd(int a, int b);
    int int_gcd_ex(int a, int b, int *x, int *y);
    

    3. 求整数的乘法逆元

    在第2节的公式 2.1 中,当 g c d ( a , b ) = 1 gcd(a, b) = 1 gcd(a,b)=1 时,有:
    a x + b y = 1 = g c d ( a , b ) ax + by = 1 = gcd(a, b) ax+by=1=gcd(a,b)

    等式两边同时 m o d   b mod\ b mod b,有: a x   m o d   b + b y   m o d   b ≡ 1   m o d   b ax\ mod\ b + by\ mod\ b \equiv 1\ mod\ b ax mod b+by mod b1 mod b,而 b y   m o d   b = 0 by\ mod\ b = 0 by mod b=0
    所以:
    a x ≡ 1   m o d   b ax \equiv 1\ mod\ b ax1 mod b
    因此,a 和 x 在模b 的前提下互为逆元。

    第2节的函数int_gcd_ex在求整数 a 和整数 b 最大公约数的同事,可以顺带求出 a 和 b 的乘法逆元。

    以下代码复用int_gcd_ex,求整数 a 基于整数 b 的乘法逆元:

    /**
     * @description: 基于扩展欧几里得算法计算整数 a 关于 整数 b 的乘法逆元
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @return {*} 返回整数 a 关于整数 b 的最小正整数乘法逆元, 乘法逆元不存在(gcd(a, b) != 1)则返回 0;
     */
    int int_inv(int a, int b)
    {
        int res, ia, ib;
    
        res = int_gcd_ex(a, b, &ia, &ib);
    
        /* gcd(a, b) != 1, 没有乘法逆元 */
        if (res != 1)
        {
            return 0;
        }
    
        /* 调整小于 0 的情况 */
        if (ia < 0)
        {
            ia += b;
        }
    
        return ia;
    }
    

    这里的函数名是integer inverse的简写,如果整数 a 和整数 b 的最大公约数为1(互素),则返回整数 a 关于整数 b 的最小正整数逆元,如果不能满足这个条件,则函数返回 0。

    上面的代码中,在求乘法逆元时,通过扩展欧几里得算法int_gcd_ex同时得到了整数 a 和整数 b 的逆元 ia 和 ib,但整数 b 的逆元 ib 并没有被使用,所以可以在int_inv函数中将int_gcd_ex的代码展开,去掉所有整数 b 逆元计算相关代码,得到的新的代码如下:

    /**
     * @description: 基于扩展欧几里得算法计算整数 a 关于 整数 b 的乘法逆元(展开 int_gcd_ex 后的优化版本)
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @return {*} 返回整数 a 关于整数 b 的最小正整数乘法逆元, 乘法逆元不存在(gcd(a, b) != 1)则返回 0;
     */
    int int_inv(int a, int b)
    {
        int x, x0, x1;
        int q, r, t;
    
        /* 消除警告: "warning: ‘x’/‘y’ may be used uninitialized in this function" */
        x = 0;
    
        /* 初始化最初两项系数 */
        x0 = 1;
        x1 = 0;
    
        /* 临时保存 b */
        t = b;
    
        q = a / b;
        r = a % b;
    
        while (r != 0)
        {
            /* 计算当前项 x */
            x = x0 - q * x1;
    
            /* 依次保存前两项到 x0, x1 */
            x0 = x1; x1 = x;
    
            a = b;
            b = r; /* 前一次的余数 */
    
            q = a / b;
            r = a % b;
        }
    
        /* gcd(a, b) != 1, 没有乘法逆元 */
        if (b != 1)
        {
            return 0;
        }
    
        /* 调整小于 0 的情况 */
        if (x < 0)
        {
            x += t;
        }
    
        return x;
    }
    

    优化的内容主要是减少整数 b 计算乘法逆元所使用相关变量 y, y0, y1 的赋值,减少这 3 个变量所占用的空间。实际加解密中,求逆元的代码并不会非常频繁被调用,因此这个优化带来的效率提升我认为比较有限。

    相比之下,我还是更喜欢调用int_gcd_ex求乘法逆元的版本,因为这个版本代码更简洁,思路更清晰。

    4. 完整代码和测试

    4.1 源码

    • 头文件gcd.h:
    /*
     * @        file: gcd.h
     * @ description: 整数和扩展域上多项式的最大公约数(gcd), 乘法逆元(multiple reverse)的计算
     * @      author: Yongqiang Gu
     * @        blog: https://blog.csdn.net/guyongqiangx
     */
    #ifndef __GCD_H__
    #define __GCD_H__
    #ifdef __cplusplus
    extern "C"
    {
    #endif
    
    /**
     * @description: 使用欧几里得算法(辗转相除)求最大公约数
     * @param {int} a 整数a
     * @param {int} b 整数b
     * @return {*} 返回整数 (a, b) 的最大公约数
     */
    int int_gcd(int a, int b);
    
    /**
     * @description: 使用扩展欧几里得算法: Extend Euclidean Algorithm (EEA) 计算等式 a x ia + b x ib = gcd(a, b) 中的 ia, ib 和 gcd(a, b)
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @param {int} *ia 整数 a 的系数 ia
     * @param {int} *ib 整数 b 的系数 ib
     * @return {*} 返回整数 (a, b) 的最大公约数 gcd(a, b)
     */
    int int_gcd_ex(int a, int b, int *ia, int *ib);
    
    /**
     * @description: 基于扩展欧几里得算法计算整数 a 关于 整数 b 的乘法逆元
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @return {*} 返回整数 a 关于整数 b 的最小正整数乘法逆元, 乘法逆元不存在(gcd(a, b) != 1)则返回 0;
     */
    int int_inv(int a, int b);
    
    #ifdef __cplusplus
    }
    #endif
    #endif
    
    • 源码文件int_gcd.c:
    /*
     * @        file: int_gcd.c
     * @ description: 整数的最大公约数(欧几里得算法 Euclidean Algorithm),和扩展欧几里得算法(Extend Euclidean Algorithm)求乘法逆元的实现
     * @      author: Yongqiang Gu
     * @        blog: https://blog.csdn.net/guyongqiangx
     */
    #include "gcd.h"
    
    ///**
    // * @description: 使用欧几里得算法(辗转相除)求最大公约数的递归版本
    // * @param {int} a 整数a
    // * @param {int} b 整数b
    // * @return {*} 返回整数 (a, b) 的最大公约数
    // */
    //int int_gcd(int a, int b)
    //{
    //    if (b == 0)
    //    {
    //        return a;
    //    }
    //    else
    //    {
    //        return int_gcd(b, a % b);
    //    }
    //}
    
    
    /**
     * @description: 使用欧几里得算法(辗转相除)求最大公约数的非递归版本
     * @param {int} a 整数a
     * @param {int} b 整数b
     * @return {*} 返回整数 (a, b) 的最大公约数
     */
    int int_gcd(int a, int b)
    {
        int t;
    
        while (b != 0)
        {
            t = a % b;
            a = b;
            b = t;
        }
    
        return a;
    }
    
    ///**
    // * @description: 使用扩展欧几里得算法(EEA)计算等式 a x ia + b x ib = gcd(a, b) 中的系数 ia, ib 和 gcd(a, b), 递归版本, 推导和证明参考: https://blog.csdn.net/lincifer/article/details/49391175
    // * @param {int} a 整数 a
    // * @param {int} b 整数 b
    // * @param {int} *ia 整数 a 的系数 ia
    // * @param {int} *ib 整数 b 的系数 ib
    // * @return {*} 返回整数 (a, b) 的最大公约数 gcd(a, b)
    // */
    //int int_gcd_ex(int a, int b, int *ia, int *ib)
    //{
    //    int x, y;
    //    int q, r;
    //
    //    if (b == 0)
    //    {
    //        *ia = 1;
    //        *ib = 0;
    //
    //        return a;
    //    }
    //
    //    r = int_gcd_ex(b, a % b, &x, &y);
    //
    //    *ia = y;
    //    *ib = x - a / b * y;
    //
    //    return r;
    //}
    
    /**
     * @description: 使用扩展欧几里得算法(EEA) 计算等式 a x ia + b x ib = gcd(a, b) 中的系数 ia, ib 和 gcd(a, b), 非递归版本
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @param {int} *ia 整数 a 的系数 ia
     * @param {int} *ib 整数 b 的系数 ib
     * @return {*} 返回整数 (a, b) 的最大公约数 gcd(a, b)
     */
    int int_gcd_ex(int a, int b, int *ia, int *ib)
    {
        int x, y, x0, y0, x1, y1;
        int q, r;
    
        /* 消除警告: "warning: ‘x’/‘y’ may be used uninitialized in this function" */
        x = y = 0;
    
        /* 初始化最初两项系数 */
        x0 = 1; y0 = 0;
        x1 = 0; y1 = 1;
    
        q = a / b;
        r = a % b;
    
        while (r != 0)
        {
            /* 计算当前项 x/y */
            x = x0 - q * x1;
            y = y0 - q * y1;
    
            /* 依次保存前两项到 x0/y0, x1/y1 */
            x0 = x1; x1 = x;
            y0 = y1; y1 = y;
    
            a = b;
            b = r; /* 前一次的余数 */
    
            q = a / b;
            r = a % b;
        }
    
        *ia = x;
        *ib = y;
    
        return b;
    }
    
    ///**
    // * @description: 基于扩展欧几里得算法计算整数 a 关于 整数 b 的乘法逆元
    // * @param {int} a 整数 a
    // * @param {int} b 整数 b
    // * @return {*} 返回整数 a 关于整数 b 的最小正整数乘法逆元, 乘法逆元不存在(gcd(a, b) != 1)则返回 0;
    // */
    //int int_inv(int a, int b)
    //{
    //    int res, ia, ib;
    //
    //    res = int_gcd_ex(a, b, &ia, &ib);
    //
    //    /* gcd(a, b) != 1, 没有乘法逆元 */
    //    if (res != 1)
    //    {
    //        return 0;
    //    }
    //
    //    /* 调整小于 0 的情况 */
    //    if (ia < 0)
    //    {
    //        ia += b;
    //    }
    //
    //    return ia;
    //}
    
    /**
     * @description: 基于扩展欧几里得算法计算整数 a 关于 整数 b 的乘法逆元(展开 int_gcd_ex 后的优化版本)
     * @param {int} a 整数 a
     * @param {int} b 整数 b
     * @return {*} 返回整数 a 关于整数 b 的最小正整数乘法逆元, 乘法逆元不存在(gcd(a, b) != 1)则返回 0;
     */
    int int_inv(int a, int b)
    {
        int x, x0, x1;
        int q, r, t;
    
        /* 消除警告: "warning: ‘x’ may be used uninitialized in this function" */
        x = 0;
    
        /* 初始化最初两项系数 */
        x0 = 1;
        x1 = 0;
    
        /* 临时保存 b */
        t = b;
    
        q = a / b;
        r = a % b;
    
        while (r != 0)
        {
            /* 计算当前项 x */
            x = x0 - q * x1;
    
            /* 依次保存前两项到 x0, x1 */
            x0 = x1; x1 = x;
    
            a = b;
            b = r; /* 前一次的余数 */
    
            q = a / b;
            r = a % b;
        }
    
        /* gcd(a, b) != 1, 没有乘法逆元 */
        if (b != 1)
        {
            return 0;
        }
    
        /* 调整小于 0 的情况 */
        if (x < 0)
        {
            x += t;
        }
    
        return x;
    }
    

    4.2 基于gtest的单元测试

    • 测试代码

    基于gtest的单元测试int_gcd_unittest.cc:

    // g++ int_gcd.c int_gcd_unittest.cc -o int_gcd -Igtest/include -Lgtest/lib -lgtest_main -lgtest -lpthread
    #include "gcd.h"
    #include <gtest/gtest.h>
    
    TEST(IntegerGCDTest, CompositeTest)
    {
        /* gcd(60, 0) = 60, gcd(0, 20) = 20 */
        EXPECT_EQ(60, int_gcd(60,  0));
        EXPECT_EQ(20, int_gcd( 0, 20));
    
        EXPECT_EQ(12, int_gcd(60, 24));
        EXPECT_EQ(11, int_gcd(55, 22));
        EXPECT_EQ( 3, int_gcd(33, 18));
        EXPECT_EQ( 3, int_gcd(27, 21));
        EXPECT_EQ( 6, int_gcd(84, 30));
        EXPECT_EQ(10, int_gcd(50, 30));
        EXPECT_EQ( 7, int_gcd(973, 301));
    
        EXPECT_EQ(77, int_gcd(7469, 2464));
        EXPECT_EQ(34, int_gcd(24140, 16762));
        EXPECT_EQ(35, int_gcd(4655, 12075));
        EXPECT_EQ(1078, int_gcd(1160718174, 316258250));
    }
    
    TEST(IntegerGCDTest, PrimeTest)
    {
        EXPECT_EQ(1, int_gcd(67, 12));
        EXPECT_EQ(1, int_gcd(29, 100));
        EXPECT_EQ(1, int_gcd(1759, 550));
        EXPECT_EQ(1, int_gcd(2689, 4001));
    }
    
    TEST(IntegerExtEuclideanTest, GCDTest)
    {
        int ia, ib;
    
        EXPECT_EQ(3, int_gcd_ex(33, 18, &ia, &ib));
        EXPECT_EQ(3, int_gcd_ex(18, 33, &ia, &ib));
    
        EXPECT_EQ(1, int_gcd_ex(100, 29, &ia, &ib));
        EXPECT_EQ(1, int_gcd_ex(29, 100, &ia, &ib));
    
        EXPECT_EQ(10, int_gcd_ex(50, 30, &ia, &ib));
    
        EXPECT_EQ(1, int_gcd_ex(1759, 550, &ia, &ib));
    }
    
    TEST(IntegerExtEuclideanTest, InverseTest)
    {
        int res, ia, ib;
    
        /* 198 x (-11) + 243 x 9 = 9 = gcd(198, 243) */
        res = int_gcd_ex(198, 243, &ia, &ib);
        EXPECT_EQ(  9, res);
        EXPECT_EQ(-11, ia);
        EXPECT_EQ(  9, ib);
    
        /* 1819 x 71 + 3587 x (-36) = 17 = gcd(1819, 3587) */
        res = int_gcd_ex(1819, 3587, &ia, &ib);
        EXPECT_EQ( 17, res);
        EXPECT_EQ( 71, ia);
        EXPECT_EQ(-36, ib);
    
        res = int_gcd_ex(100, 29, &ia, &ib);
        EXPECT_EQ(  1, res);
        EXPECT_EQ(  9, ia);
        EXPECT_EQ(-31, ib);
    
        res = int_gcd_ex(12, 67, &ia, &ib);
        EXPECT_EQ( 1, res);
        EXPECT_EQ(28, ia);
        EXPECT_EQ(-5, ib);
    
        res = int_gcd_ex(973, 301, &ia, &ib);
        EXPECT_EQ(  7, res);
        EXPECT_EQ( 13, ia);
        EXPECT_EQ(-42, ib);
    
        res = int_gcd_ex(1234, 4321, &ia, &ib);
        EXPECT_EQ(    1, res);
        EXPECT_EQ(-1082, ia);
        EXPECT_EQ(  309, ib);
    
        res = int_gcd_ex(24140, 40902, &ia, &ib);
        EXPECT_EQ(  34, res);
        EXPECT_EQ(-571, ia);
        EXPECT_EQ(337, ib);
    
        res = int_gcd_ex(1759, 550, &ia, &ib);
        EXPECT_EQ(   1, res);
        EXPECT_EQ(-111, ia);
        EXPECT_EQ( 355, ib);
    
        res = int_gcd_ex(550, 1769, &ia, &ib);
        EXPECT_EQ(   1, res);
        EXPECT_EQ( 550, ia);
        EXPECT_EQ(-171, ib);
    }
    
    TEST(IntegerInverseTest, InverseTest)
    {
        /* gcd(33, 18) = 3, no inverse */
        EXPECT_EQ(0, int_inv(33, 18));
        /* gcd(30, 50) = 10, no inverse */
        EXPECT_EQ(0, int_inv(30, 50));
    
        /* gcd(12, 67) = 1, 12 x 28 mod 67 = 1 */
        EXPECT_EQ(28, int_inv(12, 67));
    
        /* gcd(1759, 550) = 1, 1759 x 439 mod 550 = 1 */
        EXPECT_EQ(439, int_inv(1759, 550));
        EXPECT_EQ(355, int_inv(550, 1759));
    
        EXPECT_EQ(3239, int_inv(1234, 4321));
        EXPECT_EQ(0, int_inv(24140, 40902));
        EXPECT_EQ(550, int_inv(550, 1769));
    
        EXPECT_EQ(69, int_inv(29, 100));
        EXPECT_EQ(9, int_inv(100, 29));
    }
    
    • 测试结果
    [==========] Running 5 tests from 3 test suites.
    [----------] Global test environment set-up.
    [----------] 2 tests from IntegerGCDTest
    [ RUN      ] IntegerGCDTest.CompositeTest
    [       OK ] IntegerGCDTest.CompositeTest (0 ms)
    [ RUN      ] IntegerGCDTest.PrimeTest
    [       OK ] IntegerGCDTest.PrimeTest (0 ms)
    [----------] 2 tests from IntegerGCDTest (0 ms total)
    
    [----------] 2 tests from IntegerExtEuclideanTest
    [ RUN      ] IntegerExtEuclideanTest.GCDTest
    [       OK ] IntegerExtEuclideanTest.GCDTest (0 ms)
    [ RUN      ] IntegerExtEuclideanTest.InverseTest
    [       OK ] IntegerExtEuclideanTest.InverseTest (0 ms)
    [----------] 2 tests from IntegerExtEuclideanTest (0 ms total)
    
    [----------] 1 test from IntegerInverseTest
    [ RUN      ] IntegerInverseTest.InverseTest
    [       OK ] IntegerInverseTest.InverseTest (0 ms)
    [----------] 1 test from IntegerInverseTest (0 ms total)
    
    [----------] Global test environment tear-down
    [==========] 5 tests from 3 test suites ran. (0 ms total)
    [  PASSED  ] 5 tests.
    

    5. 其它

    洛奇工作中常常会遇到自己不熟悉的问题,这些问题可能并不难,但因为不了解,找不到人帮忙而瞎折腾,往往导致浪费几天甚至更久的时间。

    所以我组建了几个微信讨论群(记得微信我说加哪个群,如何加微信见后面),欢迎一起讨论:

    • 一个密码编码学讨论组,主要讨论各种加解密,签名校验等算法,请说明加密码学讨论群。
    • 一个Android OTA的讨论组,请说明加Android OTA群。
    • 一个git和repo的讨论组,请说明加git和repo群。

    在工作之余,洛奇尽量写一些对大家有用的东西,如果洛奇的这篇文章让您有所收获,解决了您一直以来未能解决的问题,不妨赞赏一下洛奇,这也是对洛奇付出的最大鼓励。扫下面的二维码赞赏洛奇,金额随意:

    收钱码

    洛奇自己维护了一个公众号“洛奇看世界”,一个很佛系的公众号,不定期瞎逼逼。公号也提供个人联系方式,一些资源,说不定会有意外的收获,详细内容见公号提示。扫下方二维码关注公众号:

    公众号

    展开全文
  • C语言实现欧几里得算法与扩展欧几里得算法1、欧几里得算法1.1 原理阐述欧几里得算法求最大公约数原理主要依赖于以下定理:gcd(a,b)=gcd(b,a%b)。其证明过程如下:a可以表示成a = kb + r,则r = a mod b假设d是a,b的...

    C语言实现欧几里得算法与扩展欧几里得算法

    1、欧几里得算法

    1.1 原理阐述

    欧几里得算法求最大公约数原理主要依赖于以下定理:gcd(a,b)=gcd(b,a%b)。其证明过程如下:a可以表示成a = kb + r,则r = a mod b假设d是a,b的一个公约数,则有d|a,d|b,而r = a - kb,因此d|r因此d也是(b,a mod b)的公约数因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

    1.3 C语言编程实现

    以下是C语言程序代码:

    #include

    long Eucli(long a,long b,long &n)

    {

    if(b==0) return a;

    {n=n+1;return Eucli(b,a%b,n);}

    }

    int main()

    {

    long a,b,n=0,d,t=0;

    printf("enter the first number:\n");

    scanf("%ld",&a);

    printf("enter the second number:\n");

    scanf("%ld",&b);

    if(a

    d=Eucli(a,b,n);

    printf("gcd=%ld\n",d);

    printf("迭代次数:%ld\n",n);

    return 0;

    }

    下图是用VC6运行代码时的截图。

    扩展欧几里得算法

    2.1 原理阐述

    扩展欧几里德算法是用来在已知a, b求解一组x和y,使它们满足等式: ax+by =?gcd(a, b) =d(解一定存在,根据数论中的相关定理)。即对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x和y,使得 gcd(a,b)=ax+by。

    2.2 算法设计

    扩展欧几里得算法,精髓在于对x和y的赋值。对于a' = b,b' = a % b 而言,我们求得 x,y使得 a'x + b'y = Gcd(a',b')由于b' = a% b = a - a / b * b 那么可以得到:a'x + b'y= Gcd(a',b') ,因而bx + (a - a / b * b),y = Gcd(a',b') = Gcd(a,b)进而可得ay +b(x - a / b*y) = Gcd(a,b)因此对于a和b而言,他们的相对应的p,q分别是y和(x-a/b*y)。具体流程图如下:

    2.3 C语言编程实现

    以下是C语言程序代码:

    #include

    long exEucli(long a,long b,long & x,long & y,long & n){

    if(b == 0){ x = 1; y = 0; return a;}

    n+=1;

    long r = exEucli(b, a%b, x, y,n);

    long t = y;y = x - (a/b)*y;x = t;

    return r;

    }

    int main()

    {

    long a,b,x,y,n=0,t;

    printf("enter the first number:\n");

    scanf("%ld",&a);

    printf("enter the second number:\n");

    scanf("%ld",&b);

    if(a

    exEucli(a,b,x,y,n);

    printf("gcd=%ld\n",a*x+b*y);

    printf("迭代次数:%ld\n",n);

    return 0;

    }

    下图是在VC6中运行代码时的截图。

    两种算法运行效率比较

    通过对两种算法的原理进行研究,再结合以上两张截图,我们发现,76512348两数进行最大公约数的求解中,两种递归算法的迭代次数都是12次。但是,有所不同的是,在欧几里得算法中,每次迭代进行的操作是对a和b求余数。而在扩展欧几里得算法中,每次迭代时,除了要做一次求商的之外,还要做一次乘法和减法。因此,运用欧几里得算法和扩展欧几里得算法对两个整数求最大公约数时,欧几里得算法更为高效。

    1

    1

    开始

    对a和b进行赋值

    b=t

    a=b

    t=mod(a,b)

    结束

    输出最大公约数b

    a%b=0

    N

    Y

    开始

    x=t

    y=x-(a/b)*y

    t=y

    结束

    输出最大公约数a*x+b*y

    b=0

    输入a和b

    展开全文
  • 公元前 300 年左右,欧几里得的一些智能数学的代码首先出现,它计算两个整数的最大公约数。
  • 此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
  • 扩展欧几里得算法求逆元
  • 欧几里得算法求最大公约数的c++代码,很完整,可以运行
  • 欧几里得算法欧几里得算法是用来求解两个不全为0的非负整数m和n的最大公约数的一个高效且简单的算法。该算法来自于欧几里得的《几何原本》。数学公式表达如下:对两个不全为0的非负整数不断应用此式:gcd(m,n)=gcd(n...

    欧几里得算法

    欧几里得算法是用来求解两个不全为0的非负整数m和n的最大公约数的一个高效且简单的算法。该算法来自于欧几里得的《几何原本》。数学公式表达如下:

    对两个不全为0的非负整数不断应用此式:gcd(m,n)=gcd(n,m mod n);直到m mod n为0时。m就是最大公约数

    证明:我们假设有a,b两个不全为0的数,令 a % b = r; 那么有 a = kb + r. 假设a,b的公约数是d。记做 d|a,d|b,表示d整除a和b。r = a - kb; 给这个式子两边同除以 d,有 r/d = a /d - kb / d,由于d是a ,b的公约数,那么r/d 必将能整除,即:b 和 a%b的公约数也是d。故:gcd(a,b) = gcd(b, a % b)。到此为止,已经证明了a和b的公约数和 b 和 a % b的公约数相等。直到a mod b为0的时候(因为即使 b > a,经过 a % b后,就变成计算gcd(b,a)。因此,a mod b的值会一直变小,最终会变成0),此时gcd(m,0) = m。因为0除以任何数都是0,所以m是gcd(m,0)的最大公约数。根据上面已经证明的等式gcd(a,b) = gcd(b, a % b)。可得:m就是最大公约数。定理得证。

    下面是C++代码实现欧几里得算法。

    #include

    using namespace std;

    int gcd(int m, int n);

    int main()

    {

    int m, n;

    cout << "请输入要计算的两个数,用空格隔开:\n";

    cin >> m >> n;

    cout << "最大公约数是:" << gcd(m, n);

    return 0;

    }

    int gcd(int m, int n)

    {

    int r;

    while (0 != n)

    {

    r = m % n;

    m = n;

    n = r;

    }

    return m;

    }

    扩展欧几里得算法

    欧几里得算法提供了一种快速计算最大公约数的方法。而扩展欧几里得算法不仅能够求出其最大公约数。而且能够求出m,n和其最大公约数构成的不定方程mx+ny=d的两个整数x,y(这里x和y不一定为正数)。

    在欧几里得算法中,终止状态是n == 0时,这时候其实就是gcd(m,0);我们想从这个最终状态反推出刚开始的状态。由欧几里得算法可知。gcd(m,n) = gcd(n,m mod n);那么有如下表达式:

    gcd(m,n) = m*x1+n*y1;

    gcd(n,m mod n) = n*x2+(m - m/n*n)*y2;(此处的m/n表示整除,例如:6/4 = 1;所以:m mod n = m % n = m - m/n*n)

    化简上式有:n*x2 + m * y2 - m/n*n*y2

    = m*y2 + n*(x2 - m/n*y2)

    与原式 gcd(m,n) = m*x1+n*y1;​​​​​​对比,容易得出:

    x1 = y2;

    y1 = x2 - m/n*y2;

    根据上面的递归式和欧几里得算法的终止条件n == 0,我们可以很容易知道最终状态是m * x1 + 0 * y1 = m;故:x1 = 1;根据上述的递推公式和最终状态,可以写出代码如下:

    #include

    using namespace std;

    int exgcd(int m, int n, int &x, int &y);

    int main()

    {

    int x, y;

    int m, n;

    int gcd;

    cout << "请输入两个数字:\n";

    cin >> m >> n;

    cout << "满足贝祖等式" << m << "*x + " << n << "*y = " << (gcd = exgcd(m, n, x, y)) << endl;

    cout << "最大公约数是:" << gcd << endl;

    cout << "其中一组解是:x = " << x << "; y = " << y << endl;

    system("pause");

    return 0;

    }

    int exgcd(int m, int n, int &x, int &y)

    {

    if (0 == n)//递归终止条件

    {

    x = 1;

    y = 0;

    return m;

    }

    int gcd = exgcd(n, m%n, x, y);//递归求解最大公约数。

    int temp = x;

    x = y;//回溯表达式1:x1 = y2;

    y = temp - m / n * y;//回溯表达式2:y1 = x1 - m/n * y2;

    return gcd;

    }

    上述的方程m*x+n*y=gcd(m,n);这个方程也被称之为“贝祖等式”。它说明了对a,b和它们的最大公约数d之间的线性丢番图方程。一定存在整数x,y使得m*x+n*y=gcd(m,n)成立。从这里也可以得出一个重要推论:

    a,b互质的充要条件是方程ax+by = 1必有整数解。

    现在来讨论一个更一般的方程:ax + by = c(a,b,c都是整数)。这个方程想要有整数解,那么根据扩展欧几里得算法我们知道,当且仅当m是d = gcd(a,b)的倍数时有解。同时有无穷多组整数解。

    我们知道了线性丢番图方程ax + by = c有整数解的条件,并且根据上述算法,也能求出一组丢番图方程的解。但是这组解很可能包含负数。我们通常的需求是最小的特解。也就是这个不定方程的最小正整数解。

    一般扩展欧几里得算法有如下应用:

    求解乘法逆元

    把a*x=1 ( mod p)称为a关于 1 mod p的乘法逆元。 它的解其实就相当于寻找方程 a*x+p*y=1 的解。根据乘法逆元的性质,只有当a与p互素,a关于模p的乘法逆元有解。如果时不互素,则无解。那么这个方程就是a,b互质的充要条件是方程ax+by = 1必有整数解。我们就可以使用扩展欧几里得算法求得其逆元。

    int inv(int m, int n, int & x, int & y)

    {

    int gcd = exgcd(m, n, x, y);

    if (1 != gcd)//说明乘法逆元不存在

    {

    return -1;

    }

    else

    {

    return (x + n) % n;//为了使余数一定为正数

    //模运算系统的特性

    }

    }

    这样就能求出两个互质的数的逆元了。

    最小正整数解

    设整数a,b,c;若方程ax+by = c的一组整数解为(x0,y0);那么它的任意组整数解都可以写成:(x0+kb',y0-ka').

    其中a' = a / gcd(a,b);b' = b / gcd(a,b);k取整数即可。

    int res(int a, int b, int c ,int &x, int &y)

    {

    int gcd = exgcd(a, b, x, y);//求出最大公约数以及满足等式mx+ny=gcd(m,n)的一组(x,y);

    if (0 != c % gcd)//如果c不是gcd(m,n)的倍数,该丢番图方程无整数解。

    {

    return -1;

    }

    x *= c / gcd;//将x转化为方程ax+by=c的解。

    //先求出x的最小值。根据通解公式x = x0+kb'; b'= b / gcd(a,b);

    b /= gcd;//求b'

    if (b < 0)

    {

    b = -b;//b为负数,则取绝对值

    }

    int r = x % b;//求出最小整数解

    if (r <= 0)

    {

    r += b;//求出最小正整数解

    }

    return r;

    }

    本文同步分享在 博客“zy010101”(CSDN)。

    如有侵权,请联系 support@oschina.cn 删除。

    本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

    展开全文
  • 扩展欧几里得算法

    2018-04-17 15:03:00
    在编写扩展欧几里得算法的前提下,计算了两个数的最大公因数,判断两数是否互素。
  • 欧几里得算法及扩展的欧几里得算法的C++实现。包括.cpp,.exe可执行文件。我的作业。对于密码学和C++初学者有用处,希望对大家有帮助。
  • 掌握欧几里得算法和扩展欧几里得算法的原理 2. 编写程序实现这两个算法 二、实验设备(环境)及要求 PC机, VC++等 三、实验内容与步骤 1、欧几里得算法(对代码中的主要内容进行分析讲解...
  • 欧几里得算法的应用 欧几里得算法的应用 欧几里得算法的应用
  • 欧几里得算法详解

    千次阅读 2021-01-24 14:16:52
    二、欧几里得算法的内容 欧几里得是快速找出两个数最大公约的一种算法。算法核心思想: 例如找A,B的最大公约数GCD(A,B),并且A>B 如果A=0,那么GCD(A,B)=GCD(0,B)=B; 如果B=0,那么DCD(A,B)=GCD(A...
  • 欧几里得算法和扩展的欧几里得算法C++递归实现 关于欧几里得算法的流程不再赘述,不清楚的可以搜得到。本篇主要通过C++代码利用递归的思想实现,参考书籍是《密码编码与信息安全:C++实践》。 1、欧几里得算法实现 ...
  • 广义欧几里得算法信息安全数学基础
  • 欧几里得算法:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的...
  • 扩展欧几里得算法推导

    千次阅读 2021-01-20 16:42:33
    扩展欧几里得算法推导过程 1 从简单的两个数a和b开始 欧几里得算法是用来求a与b的最大公约数的算法,也称辗转相除法,即以除数与余数反复做除法运算,当余数为0时,除数即为a与b的最大公约数 已知a和b,假设g为a与b...
  • 已知整数a,b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y,满足ax + by = gcd(a,b) 分析 设 a>b。 (1)显然当 b=0,gcd(a,b)= a。此时 x=1,y=0; (2)a>b>0 时 设 ax1+...
  • 出于对欧几里得的尊重,先简单介(cou)绍(ge)一(zi)下(shu).。欧几里得,古希腊人,数学家。他活跃于托勒密一世时期的亚历山大里亚,被称为“几何之父”。他最著名的著作《几何原本》是欧洲数学的基础,提出五大公设...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,442
精华内容 11,776
关键字:

欧几里得算法

友情链接: ccl_modular ASM.rar