美文网首页三月听我说
利用扩展的欧几里得算法求逆元

利用扩展的欧几里得算法求逆元

作者: 夜斗丶 | 来源:发表于2019-01-10 16:02 被阅读2次

首先说一下逆元的定义。
存在一个数a使得ax对y进行取余运算,得到的值是一,则成为a是x的逆元。在数学中记做
a * x = 1(mod p)
例如x = 4,y = 11,3
x = 1(mod y),34=12,12 mod 11 = 1,3就是x的逆元。
对于求逆元这一操作在计算机领域主要用于非对称加密,如我们常见的RSA加密算法等。
那应该求得这个逆元呢,我们知道,再求两个数的最大公约数的时候可以用欧几里得算法。
在欧几里得算法中,通过辗转相除,当余数为0的时候最后的除数就是两个数的最大公约数。
而在其扩展算法中,我们已知两个数的最大公约数,我们已知 a
x = 1(mod p),
展开就是 ax mod p = 1,首先我们先求 p = x1 * a + p1,然后p = a,a = p1,迭代下去
知道pi = 1(i表示出了i次)为之,然后就可以得出 1 = p - xi * a,此时的a和p已经不是我们初始的a和p了,我们需要往前推,推到 1= y
p + xa 为止,此时得出的x就是a的逆元,当然如果逆元x为负数,或者比p大,要对其就行取余操作。
举个例子 11 = 1(mod 20)求11的逆元
20 = 1
11 + 9 此时x1 = 1, a = 11,p = 20,p1 = 9,执行p = a,a = p1
11 = 19 + 2 x2 = 1,a = 9,p2 = 2。
9 = 2
4 + 1 p3 = 1,
1 = 9-24。
从上述式子中可以得知 9 = 20-11
1 = 20-11-2
4
同时 2 = 11 -9
1 = 20 -11 -4(11-9)
已知 9 = 20 - 11
1 = 20 -11 -4
(11-(20-11))
1 = 20 -11 -4(11-20+11)
合并同类项得
1 = 5
20 - 911
1 = y
20 + x * 11
x为a的逆元 x = -9
x对p取余,x = 11
验证 11 * 11 = 121,121 mod 20 = 6 --- 1
到此 计算结束

相关文章

  • 组合数求解

    扩展欧几里得算法原理求解逆元的方法(本文采用扩展欧几里得算法进行求解)求组合数的两种方法Lucas定理

  • 利用扩展的欧几里得算法求逆元

    首先说一下逆元的定义。存在一个数a使得ax对y进行取余运算,得到的值是一,则成为a是x的逆元。在数学中记做a * ...

  • 扩展欧几里得算法

    资料 欧几里得算法 扩展欧几里得算法 扩展欧几里得算法应用 欧几里得算法 欧几里得算法用于求两个数的最大公约数 证...

  • 扩展欧几里得算法

    扩展欧几里得算法(Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)的扩展...

  • 算法学习(2)----丢番图方程

    之前一篇随笔"算法学习(1)----扩展欧几里得算法"记录了对朴素欧几里得算法和扩展欧几里得算法的学习和认识...

  • 求逆元

  • 扩展欧几里德算法

    扩展欧几里得算法(英语:Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)...

  • 学习知识

    O(n) 求[1,p-1]所有逆元

  • 组合数 模板

    Lucas定理 mod小于10^5 逆元求组合数

  • ComSec作业三--编程题(AES)

    GF(2^8)内的乘法 测试截图: 求乘法逆元

网友评论

    本文标题:利用扩展的欧几里得算法求逆元

    本文链接:https://www.haomeiwen.com/subject/xerarqtx.html