欧几里得逆运算java_miracl库的使用之——大数模逆运算

曾经终败给现在 2022-11-09 03:58 70阅读 0赞

miracl中有许多可以求乘法逆元的函数，在这里主要介绍函数xgcd()

1.函数介绍

2.涵盖内容

3.注意事项

一、xgcd：

函数原型：

int xgcd(x,y,xd,yd,z)

big x,y,xd,yd,z;

在大数库中，xgcd的计算公式是：

On exit z=gcd(x,y)=x.xd+y.yd

我一直百思不得其解，为什么这个函数可以用来计算模逆，直到发现了：拓展的欧几里得算法：

欧几里得算法是什么？

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b)

=d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。拓展的欧几里得算法其实又叫做辗转相除法，其实辗转相除法主要用来计算最大公因子，那么为什么可以计算乘法逆元呢？

回答如下： 如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。

当d=1时，有 ma + nb = 1 ，此时就可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。

\*

二、核心思想

摘记：

1)我们首先从欧几里得算法学起，欧几里得告诉我们gcd(a,b)=gcd(b,a mod b)；

2)对于不完全为 0 的非负整数 a，b，gcd(a，b)表示 a，b 的最大公约数，必然

存在整数对 x，y ，使得 gcd(a，b)=ax+by。

3)因此，当gcd(a，b)=1时，那么存在ax+by=1，此时有x就是a关于模b的乘法逆元，y也是b关于模a的乘法逆元。

在这里顺便证明一下：

证明拓展的欧几里得算法： 首先，对于整数a和整数b： 由拓展的欧几里得(Euclidean)算法：gcd(a,b)=ax+by

1：当a\*b=0时： 当a=0: gcd(a,b)=b; 同理当b=0时： gcd(a,b)=a; x=1，y存在，而可以取任何值，它们是存在的。

2:当a\*b!=0的时候： 假设gcd(a,b)=ax\[0\]+by\[0\]; 根据辗转相除法， gcd(a,b)=gcd(a,b mod

a); 则说明： gcd(a,b)

=ax\[0\]+by\[0\]

=ax\[1\]+(b-k\[1\]\*a)y\[1\] ——————k\[1\]是指b/a取整数部分。

=a(x\[1\]-k\[1\]y\[1\])x\[1\]+by\[1\] 所以： x\[0\]=x\[1\]-k\[1\]y\[1\] y\[0\]=y\[1\] 这说明x\[0\],y\[0\]的值是否存在，与x\[1\],y\[1\]是否存在相关。

当不停地使用2时，一定会出现a或者b为0，则就可以求出x以及y的值。

\*\*函数xgcd(x,y,xd,yd,z)中，就是使用拓展的欧几里得算法，从而计算出：

z=gcd(x,y)=xxd+yyd\*\*

三、注意事项

在使用xgcd求解乘法逆元的时候，必须要小心，因为相互不互素的数是没有乘法逆元的，所以使用前必须对此验证，当然也可以直接验证z，因为z=gcd(a,b);

使用xgcd(a,b,xd,yd,z)计算乘法逆元

当z=1时，xd就是a关于模b的乘法逆元

但是，yd不是关于模a的乘法逆元；

只有当xgcd(b,a,yd,xd,z)且z=1时，

yd才是b关于模a的乘法逆元

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关欧几里得算法

一.自然语言描述：计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。二.Jav

╰+哭是因爲堅強的太久メ/ 2024年03月23日 17:45/ 0 赞/ 81 阅读

相关欧几里得逆运算java_miracl库的使用之——大数模逆运算

miracl中有许多可以求乘法逆元的函数，在这里主要介绍函数xgcd() 1.函数介绍 2.涵盖内容 3.注意事项一、xgcd：函数原型： int xgcd(x

曾经终败给现在/ 2022年11月09日 03:58/ 0 赞/ 71 阅读

相关欧几里得算法

欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如： gcd (26, 15) 26 % 15 = 1 ... 11 15 % 11 = 1 ... 4

秒速五厘米/ 2022年10月01日 13:46/ 0 赞/ 237 阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 268 阅读

相关欧几里得推扩展欧几里得

欧几里得求整数a,b的最小公约数gcd(a,b)的算法。即欧几里得算法(俗称最小公倍数算法)。有一个重要的公式如下,这个公式的证明略,百度上有. (1) g

我会带着你远行/ 2022年06月13日 09:22/ 0 赞/ 269 阅读

相关欧几里得+扩展欧几里得（理解）

-------------------- 欧几里得： -------------------- 辗转相除法代码： typedef long long

妖狐艹你老母/ 2022年06月05日 05:39/ 0 赞/ 319 阅读

相关扩展欧几里得

GCD 定义欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。结论与证明对于a,b两个正整数（a>b），gcd(a,b)=gcd(a

以你之姓@/ 2022年03月20日 07:53/ 0 赞/ 290 阅读

相关数论杂谈——欧几里得算法及扩展欧几里得

数学是oi的重要基础，所以说数论在oi中占据了非常重要的地位，因此，学好数学，对于一个oier来说也是非常重要的。 oi中的数学，其实也就和数竞并没有什么区别。欧几里得法

落日映苍穹つ/ 2021年12月23日 23:55/ 0 赞/ 381 阅读

相关欧几里得算法和扩展欧几里得算法数论基础

　　这两个算法可以说是OI里数学模块最重要的基础了（如果位运算不算数学的话）。一.欧几里得算法（Euclidean Algorithm）　　模板水题：[LOJ P121

r囧r小猫/ 2021年12月12日 07:19/ 0 赞/ 342 阅读

相关欧几里得算法

一代码 package Euclid; / Copyright (C), 2020-2020, XXX有限公司 Fi

红太狼/ 2021年07月24日 16:01/ 0 赞/ 434 阅读