欧几里得算法、扩展欧几里得算法(特解、应用、通解)

news/2024/3/28 20:16:52/文章来源:https://blog.csdn.net/qq_53413759/article/details/130331090

文章目录


最近实验中用到了仿射加解密算法,其中的解密操作是通过扩展欧几里得算法实现的,因此在这里对 欧几里得算法、扩展欧几里得算法 做一个完整的记录。

1. 欧几里得算法(也叫辗转相除法)


1.1 直接上模拟

现在求 6 和 16 的最大公约数,根据高中知识(其实我也忘了,现学的芭芭拉迪):
每一次将除式中的除数作为下一次的被除数,将余数作为下一次的除数,直到商为 0,此时的除数就是最大公约数:

  • 16 ➗ 6 = 2 ⋯ ⋯ \cdots\ \cdots   4
  • 6 ➗ 4 = 1 ⋯ ⋯ \cdots \ \cdots   2
  • 4 ➗ 2 = 2 ⋯ ⋯ \cdots\ \cdots   0

因此,最大公约数为 2;


1.2 几何理解

假设现在需要对 a, b (不妨假设 a >b) 求最大公约数,在几何上可以这样进行理解:

  • a , b a, b a,b 为矩形的边长,构造一个矩形 A A A
  • 以矩形的短边(这里为 b b b)构造正方形 B,然后计算这样的正方形 B 在矩形 A 中最多能够放置多少个;

这样就对问题进行了一个抽象:目标就是去寻找能够没有缝隙地铺满矩形 A A A 的正方形 B B B 的最大边长值;
假设上面的正方形 B B B 不能将矩形 A A A 铺满,那么接下来:

  • 用长边剩余的长度够构建正方形,继续去填补未被覆盖的部分;
  • 以此类推,直到找到一个能够刚好无缝隙地填满未覆盖部分的正方形,这个正方形的边长就是最大公约数;

这样会产生一个疑问,怎么保证填满未覆盖部分的正方形能够填满大的矩形呢?
我们通过作图来理解:
在这里插入图片描述
可以看到正方形 B B B 刚好填满了正方形 A A A 未覆盖的部分,并且显然从最右边的 A A A 与两个 B B B 的关系可以看出 A A A 的边长是 B B B 的两倍。
那么,如果用 B B B 来填充 A A A 的话,

  • 纵向可以刚好填满,
  • 而又因为 A A A 是正方形,因此横向也可以刚好填满

这就证明了:能填满未覆盖部分的 B B B 一定可以填满覆盖了的所有 A A A,这就是欧几里得算法的几何解释;
现在用函数 g c d ( b , a ) gcd(b, a) gcd(b,a) 来表示在长边为 a a a,短边为 b b b 的矩形中,刚好能够无缝隙地覆盖的最大正方形边长,那么有

  • 长边剩余部分的长度为 a % b a \% b a%b
  • 短边为 b b b
  • 上述几何解释告诉我们: g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a \% b) gcd(a,b)=gcd(b,a%b)

1.3 用代数方法证明 g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a \% b) gcd(a,b)=gcd(b,a%b)

1.3.1 左推右: g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a \% b) gcd(a,b)=gcd(b,a%b)

现在有一个除式: A ➗ B = C ⋯ ⋯ D A ➗ B = C \cdots\ \cdots D AB=C D,并且 A A A B B B 的最大公约数为 k k k,现在要求 k k k

  • 由题可设: A = a × k , B = b × k A = a × k,B = b × k A=a×kB=b×k
  • 又因为 D = A − B × C D = A - B \times C D=AB×C
  • 所以 D = k ( a − b × C ) D = k(a - b \times C) D=k(ab×C)
  • 由于 a , b , C , k a, b, C, k a,b,C,k 都是整数,因此 D D D 也是整数,且是 k k k 的倍数;
  • 所以,被除数、除数、余数都有相同的公约数 k k k,且一定是最大的(假设不是最大的,则这个数一定也是被除数和除数的公约数,这与假设中的 最大公约数 矛盾)

因此,左推右得证;

1.3.2 右推左: g c d ( b , a % b ) = g c d ( a , b ) gcd(b, a \% b) = gcd(a, b) gcd(b,a%b)=gcd(a,b)

这个跟左推右的证明思路一样,关于除式 A ➗ B = C ⋯ ⋯ D A ➗ B = C \cdots\ \cdots D AB=C D,假设 B B B D D D 的最大公约数为 m m m,现在要求 m m m

  • 由题可设: B = b × m , D = d × m B = b \times m, D = d \times m B=b×m,D=d×m
  • 又因为 A = B × C + D A = B \times C + D A=B×C+D
  • 所以 A = m ( b C + d ) A = m(bC + d) A=m(bC+d)
  • 由于 b , C , d , m b, C, d, m b,C,d,m 都是整数,因此 A A A 也是整数,且是 m m m 的倍数;

因此,右推左得证;


1.4 欧几里得算法(辗转相除法)代码

展开版:

int gcd(int a, int b) {if (!b) {return a;}return gcd(b, a % b);
}

简化版:

int gcd(int a, int b) {return (b) ? gcd(b, a % b) : a;
}

2. 扩展欧几里得算法

扩展欧几里得算法是在欧几里得算法的运行过程中,求出方程 a x + b y = c ax + by = c ax+by=c 的一组解的算法;

2.1 直接上模拟

对于上面我们对欧几里得算法进行的模拟过程:

  • 16 ➗ 6 = 2 ⋯ ⋯ \cdots\ \cdots   4
  • 6 ➗ 4 = 1 ⋯ ⋯ \cdots \ \cdots   2
  • 4 ➗ 2 = 2 ⋯ ⋯ \cdots\ \cdots   0

可以从下到上对这些式子进行变形:

  • 2 = 4 × 0 + 2 × 1 2 = 4 \times 0 + 2 \times 1 2=4×0+2×1
  • 2 = 6 × 1 + 4 × ( − 1 ) 2 = 6 \times 1 + 4 \times (-1) 2=6×1+4×(1)
  • 2 = 16 × ( − 1 ) + 6 × 3 2 = 16 \times (-1) + 6 \times 3 2=16×(1)+6×3

意思就是说,一定可以找到方程 g c d ( a , b ) = a x + b y gcd(a, b) = ax + by gcd(a,b)=ax+by 的一组解;


2.2 裴蜀定理

由上面的分析可以得到一个定理:
裴蜀定理:设 a, b 为正整数,则关于 x, y 的方程 ax + by = c 有整数解 当且仅当 c 是 gcd(a, b) 的倍数;
下面给出一个简要的证明:
∵ a x + b y = c ∴ a g c d ( a , b ) x + b g c d ( a , b ) y = c g c d ( a , b ) ∵ g c d ( a , b ) 肯定是 a , b 的因子 ∴ 等式左边肯定是一个整数 ∴ 等式右边也是整数 ∴ 不妨设 k = c g c d ( a , b ) ∴ c = k ⋅ g c d ( a , b ) ∴ c 是 g c d ( a , b ) 的倍数 \begin{aligned} & \because ax + by = c \\ & \therefore \frac{a}{gcd(a, b)}x + \frac{b}{gcd(a, b)}y = \frac{c}{gcd(a, b)} \\ & \because gcd(a, b) 肯定是 a, b 的因子 \\ & \therefore 等式左边肯定是一个整数 \\ & \therefore 等式右边也是整数 \\ & \therefore 不妨设 k = \frac{c}{gcd(a, b)} \\ & \therefore c = k \cdot gcd(a, b) \\ & \therefore c 是 gcd(a, b) 的倍数 \\ \end{aligned} ax+by=cgcd(a,b)ax+gcd(a,b)by=gcd(a,b)cgcd(a,b)肯定是a,b的因子等式左边肯定是一个整数等式右边也是整数不妨设k=gcd(a,b)cc=kgcd(a,b)cgcd(a,b)的倍数
充分性按照上面的思路反推即可;
因此,假设现在要求 a x + b y = c = k ⋅ g c d ( a , b ) ax + by = c = k \cdot gcd(a, b) ax+by=c=kgcd(a,b) 的一组解,只需求出 a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b) 的一组解 ( x ′ , y ′ ) (x', y') (x,y),然后令系数 x = k x ′ , y = k y ′ x = kx', y = ky' x=kx,y=ky 即可;


2.3 算法公式推导

现在看下面的方程:
b x 0 + ( a % b ) y 0 = g c d ( b , a % b ) bx_0 + (a \% b)y_0 = gcd(b, a \% b) bx0+(a%b)y0=gcd(b,a%b)
由于 g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a \% b) gcd(a,b)=gcd(b,a%b),因此有
b x 0 + ( a % b ) y 0 = g c d ( a , b ) bx_0 + (a \% b)y_0 = gcd(a, b) bx0+(a%b)y0=gcd(a,b)
因此有
b x 0 + ( a − ⌊ a b ⌋ × b ) y 0 = g c d ( a , b ) bx_0 + (a - \lfloor \frac{a}{b} \rfloor \times b)y_0 = gcd(a, b) bx0+(aba×b)y0=gcd(a,b)
整理得到
a y 0 + b ( x 0 − ⌊ a b ⌋ y 0 ) = g c d ( a , b ) ay_0 + b(x_0 - \lfloor \frac{a}{b} \rfloor y_0) = gcd(a, b) ay0+b(x0bay0)=gcd(a,b)
由于 a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b),对比两个方程,令对应系数相等可以得到:
{ x = y 0 y = x 0 − ⌊ a b ⌋ y 0 \left\{ \begin{aligned} & x = y_0 \\ & y = x_0 - \lfloor \frac{a}{b} \rfloor y_0 \end{aligned} \right. x=y0y=x0bay0
所以递归更新参数 x , y x, y x,y,即可得到答案;


下面看看递归终止条件是什么:
b = 0 b = 0 b=0 时有:
g c d ( a , b ) = a gcd(a, b) = a gcd(a,b)=a
此时对于方程 a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b),有
x = 1 , y = 0 x = 1, y = 0 x=1,y=0
此为递归终止条件;

2.4 上代码

// d 为最大公约数
int extgcd(int a, int b, int& x, int& y) {if (!b) {x = 1;y = 0;return a;}int d = extgcd(b, a % b, x, y);int x0 = x, y0 = y;x = y0;y = x0 - (a / b) * y0;return d;
}

简化版还可以在递归的时候交换一下 y y y x x x

int extgcd(int a, int b, int& x, int& y) {if (!b) {x = 1;y = 0;return a;}int d = extgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}

2.5 扩展欧几里得算法的应用

2.5.1 应用一:求解不定方程

这个过程就是求 a x + b y = c ax + by = c ax+by=c 的一组整数解,上面已经进行了模拟;

2.5.2 应用二:求乘法逆元

首先给出乘法逆元的定义:

a a a p p p 互质,则满足 ( a × x ) m o d p = 1 (a \times x)\ mod\ p = 1 (a×x) mod p=1 x x x a a a 在该条件下的逆元;

举个例子:求 7 模 11 的逆元,由于 7 × 8 = 5 × 11 + 1 7 \times 8 = 5 \times 11 + 1 7×8=5×11+1,因此有 ( 7 × 8 ) m o d 11 = 1 (7 \times 8)\ mod\ 11 = 1 (7×8) mod 11=1,因此 7 在该条件下的逆元为 8;

因此,现在给出 a a a p p p,求出的方程 a x + k p = 1 ax + kp = 1 ax+kp=1 的一组解 ( x 1 , k 1 ) (x_1, k_1) (x1,k1) 其中的 x 1 x_1 x1 就是 a a a 在该条件下的逆元;

要使用扩展欧几里得算法进行求解,需要满足 g c d ( a , p ) = 1 gcd(a, p) = 1 gcd(a,p)=1,即 a a a p p p 互质,一定注意这个条件!!!


2.6 拓展:扩展欧几里得算法的通解

上面的过程我们只是求出了方程 a x + b y = c ax + by = c ax+by=c 的一组特解,现在要求的是其通解,可参考下面的过程:

2.6.1 a g c d ( a , b ) \frac{a}{gcd(a, b)} gcd(a,b)a b g c d ( a , b ) \frac{b}{gcd(a, b)} gcd(a,b)b 互质

首先证明 a g c d ( a , b ) \frac{a}{gcd(a, b)} gcd(a,b)a b g c d ( a , b ) \frac{b}{gcd(a, b)} gcd(a,b)b 互质:

采用反证法
假设 a g c d ( a , b ) \frac{a}{gcd(a, b)} gcd(a,b)a b g c d ( a , b ) \frac{b}{gcd(a, b)} gcd(a,b)b 不互质,说明它们之间还有不等于 1 的公约数
假设这个公约数为 k ( k > 0 且 k ≠ 1 ) k(k > 0 且 k \neq 1) k(k>0k=1)
因此有 a g c d ( a , b ) = k ⇒ a = k ⋅ g c d ( a , b ) > g c d ( a , b ) \frac{a}{gcd(a, b)} = k \Rightarrow a = k \cdot gcd(a, b) > gcd(a, b) gcd(a,b)a=ka=kgcd(a,b)>gcd(a,b)
这就违反了 gcd(a, b) 求取的是最大公约数的约定;
因此 a g c d ( a , b ) \frac{a}{gcd(a, b)} gcd(a,b)a b g c d ( a , b ) \frac{b}{gcd(a, b)} gcd(a,b)b 互质;

2.6.2 求通解

假设 ( x , y ) 与 ( x 0 , y 0 ) 都是方程 a x + b y = c 的解,因此有: a x + b y = c ⋯ ⋯ ① a x 0 + b y 0 = c ⋯ ⋯ ② ① − ②,有: a ( x − x 0 ) = b ( y 0 − y ) 两边同时除以 g c d ( a , b ) a g c d ( a , b ) ( x − x 0 ) = b g c d ( a , b ) ( y 0 − y ) ∵ a g c d ( a , b ) 与 b g c d ( a , b ) 互质 ∴ x − x 0 = t ⋅ b g c d ( a , b ) → x = x 0 + t ⋅ b g c d ( a , b ) ∴ y 0 − y = t ⋅ a g c d ( a , b ) → y = y 0 − t ⋅ a g c d ( a , b ) \begin{aligned} 假设 (x, y) 与 &(x_0, y_0) 都是方程 ax + by = c 的解,因此有:\\ & ax + by = c \cdots \cdots ①\\ & ax_0 + by_0 = c \cdots \cdots ②\\ & ① - ②,有:a(x - x_0) = b(y_0 - y) \\ & 两边同时除以 gcd(a, b) \\ & \frac{a}{gcd(a, b)} (x - x_0) = \frac{b}{gcd(a, b)} (y_0 - y) \\ & \because \frac{a}{gcd(a, b)} 与 \frac{b}{gcd(a, b)} 互质 \\ & \therefore x - x_0 = t \cdot \frac{b}{gcd(a, b)} \rightarrow x = x_0 + t \cdot \frac{b}{gcd(a, b)} \\ & \therefore y_0 - y = t \cdot \frac{a}{gcd(a, b)} \rightarrow y = y_0 - t \cdot \frac{a}{gcd(a, b)} \\ \end{aligned} 假设(x,y)(x0,y0)都是方程ax+by=c的解,因此有:ax+by=c⋯⋯ax0+by0=c⋯⋯,有:a(xx0)=b(y0y)两边同时除以gcd(a,b)gcd(a,b)a(xx0)=gcd(a,b)b(y0y)gcd(a,b)agcd(a,b)b互质xx0=tgcd(a,b)bx=x0+tgcd(a,b)by0y=tgcd(a,b)ay=y0tgcd(a,b)a

欢迎补充~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_103220.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Handbook of MusicPsychology 音乐心理学手册 ( 多纳德·霍杰斯 Donald.A.Hodges) 笔记

由两个以上的音组成的结合音,除了该声波的波形,人耳会另外脑补出不存在的波形 频率相距较远的一些音与频率相距较近的一些音,前者累加的响度比后者要大 除了泛音部分,音的起声部分也是音色辨别的关键 音高、响度、音色、时值&a…

LINUX的系统管理与维护命令

文章目录 一、LINUX的系统管理与维护命令总结 一、LINUX的系统管理与维护命令 - Linux ls命令:显示指定工作目录下的内容 Linux pwd命令:显示当前工作目录 Linux cd命令:切换工作目录 Linux date命令:显示或设置系统时间 Linux su命令:切换用户 Linux clear命令:清除屏幕 Li…

Java编程设计语言-集合类

API(application programming interface)是JDK的重要组成部分,API提供了Java程序与运行它的系统软件(Java虚拟机)之间的接口,可以帮助开发者方便、快捷地开发Java程序 集合在程序设计中是一种重要的是数据结构,Java中提…

Semantic Kernel 知多少 | 开启面向 AI 编程新篇章

在 ChatGPT 火热的当下, 即使没有上手亲自体验,想必也对 ChatGPT 的强大略有耳闻。当一些人在对 ChatGPT 犹犹豫豫之时,一些敏锐的企业主和开发者们已经急不可耐地开展基于 ChatGPT 模型 AI 应用的落地探索。 因此,可以明确预见的是&#xf…

Java+Angular开发的医院信息管理系统源码,系统部署于云端,支持多租户

云HIS系统源码,采用云端SaaS服务的方式提供 基于云计算技术的B/S架构的云HIS系统源码,采用云端SaaS服务的方式提供,使用用户通过浏览器即能访问,无需关注系统的部署、维护、升级等问题,系统充分考虑了模板化、配置化、…

系统分析师之软件工程(十二)

目录 一、 软件开发生命周期 1.1 开发阶段工作细分 二、软件开发模型 2.1 瀑布模型 2.2 原型模型 2.3 增量模型与螺旋模型 2.4 V模型 2.5 喷泉模型 2.6 快速应用开发模型RAD 2.7 构件主装模型 2.8 统一过程 2.9 敏捷方法 三、逆向工程 四、净室软件工程 一、 软件…

斯坦福| ChatGPT用于生成式搜索引擎的可行性

文|智商掉了一地 随着 ChatGPT 在文本生成领域迈出了重要一步,Bing 浏览器也接入了聊天机器人功能,因此如何保证 Bing Chat 等搜索引擎结果的精确率和真实性也成为了搜索领域的热门话题之一。 当我们使用搜索引擎时,往往希望搜索结…

电子阅读器市场角力,AI成为关键变量

配图来自Canva可画 近年来,随着国家“书香型社会”建设政策的出台,公众的阅读需求正在逐年增加,各类读书产品和读书活动,也如同雨后春笋般涌现,人们的阅读体验日益得到丰富。比如,昨天世界读书日举行的“不…

更简单的存取Bean方式-@Bean方法注解

1.Bean方法存储 类注解是添加在某个类上的,那么方法注解是添加在某个方法前的 public class UserBeans {Beanpublic User user1(){User user new User();user.setUid(001);user.setUname("zhangsan");user.setAge(19);user.setPassword("123123");retur…

【分布式搜索引擎ES01】

分布式搜索引擎ES 分布式搜索引擎ES1.elasticsearch概念1.1.ES起源1.2.倒排索引1.2.1.正向索引1.2.2.倒排索引 1.3.es的一些概念1.3.1.文档和字段1.3.2.索引和映射1.3.3.mysql与elasticsearch 1.4.1安装es、kibana、IK分词器1.4.2扩展词词典与停用词词典 2.索引库操作2.1.mappi…

Springcloud连接nacos集群,nacos地址配置为nginx,报错:requst nacos server failed

先说下版本: Spring cloud: Hoxton.SR12 spring.cloud.alibaba: 2.2.9.RELEASE spring.boot: 2.3.12.RELEASE Linux Centos7 nacos-server:2.1.0 nginx: 1.20.2 环境说明: nacos正常搭建三个集…

supervisor安装

说明 Supervisor翻译过来是监管人,在Linux中Supervisor是一个进程管理工具,当进程中断的时候Supervisor能自动重新启动它。可以运行在各种类Linux/unix的机器上,supervisor就是用Python开发的一套通用的进程管理程序,能将一个普通…

【虚幻引擎】UE4/UE5科大讯飞文字合成语音

一、链接地址 链接:https://pan.baidu.com/s/15Qoc48x3DLpw4eW1qHXInQ 提取码:jqpx B站视频链接:https://space.bilibili.com/449549424?spm_id_from333.1007.0.0 二、案例介绍 第一步:首先进入讯飞开放平台注册一个账号&…

ThreadPoolExecutor源码阅读流程图

1.创建线程池 public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,BlockingQueue<Runnable> workQueue) {this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue,Executors.defaultThreadFactory(), def…

Automa函数学习(三)

从变量中获取数据 当我们想要用automa获取文本标签获取到网页的文本内容后,想要将获取到的文本内容当做参数往后面的标签里进行传递时就需要用到automa提供的传参格式 {{ variables.自定义参数名}} 举例: 先建立打开百度首页工作流 前面自定义的变量名为text,所以这里参数拼接…

开放式耳机有什么好处,盘点几款性能不错的开放式耳机

随着人们对生活质量要求的提高&#xff0c;大家在运动的时候都喜欢戴上耳机&#xff0c;享受运动的乐趣。但是传统耳机戴久了之后就会出现耳朵酸痛的情况&#xff0c;这是因为传统耳机佩戴方式是通过空气振动来传递声音&#xff0c;而人在运动时就会伴随着大量的汗水&#xff0…

深入学习RabbitMQ五种模式(一)

1.安装erlang 下载otp_win64_25.3.exe https://www.erlang.org/downloads erlang安装完成&#xff0c;需要配置erlang环境变量 ERLANG_HOMEE:\software\Erlang OTPPATH%PATH%;%ERLANG_HOME%\bin; 2.安装RabbitMQ 下载rabbitmq-server-3.11.13.exe https://www.rabbitmq.com/dow…

【Python 协程详解】

0.前言 前面讲了线程和进程&#xff0c;其实python还有一个特殊的线程就是协程。 协程不是计算机提供的&#xff0c;计算机只提供&#xff1a;进程、线程。协程是人工创造的一种用户态切换的微进程&#xff0c;使用一个线程去来回切换多个进程。 为什么需要协程&#xff1f; …

IntelliJ IDEA 接入ChatGPT (免费,无需注册)生产力被干爆了!

IntelliJ IDEA 接入ChatGPT 前言 : 今天给大家介绍一款好用的 IntelliJ IDEA ChatGPT 插件 可以帮助我们写代码&#xff0c;以及语言上的处理工作&#xff0c;以及解释代码。让我们的生产力大大提高&#xff01; 一. ChatGPT-Plus 功能介绍 支持最新idea版本AI询问功能,写好…

Adobe Photoshop 软件下载

Adobe Photoshop&#xff0c;简称“PS”&#xff0c;是由Adobe Systems开发和发行的图像处理软件。Photoshop主要处理以像素所构成的数字图像。 时至今日&#xff0c;Adobe Photoshop 已经成为当今世界上最流行、应用最广泛的图像处理软件。不但设计专业的学生要系统的学习这个…