若对于数字A,C 存在X,使A * X = 1 (mod C) ,那么称X为 A 对C的乘法逆元。
逆元的作用?让我们来看下面的例子:
12 / 4 mod 7 = ? , 很显然结果是3
我们现在对于数对 (4,7), 可以知道 X = 2是 4 对7的乘法逆元即2*4=1(mod 7)
那么我们有(12 / 4) * (4 * 2 ) = (?) * (1) (mod 7)
除法被完美地转化为了乘法
理论依据:
F / A mod C = ?
如果存在 A*X = 1 (mod C)
那么2边同时乘起来,得到 F * X = ? (mod C)
成立条件
(1) 模方程 A * X = 1(mod C) 存在解
(2) A | F (F % A == 0)
以下来百度百科:
若ax=1 mod f 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。
当a与f互素时,a关于模f的乘法逆元有唯一解。如果不互素,则无解。如果f为素数,则从1到f-1的任意数都与f互素,即在1到f-1之间都恰好有一个关于模f的乘法逆元。
例如,求5关于模14的乘法逆元:
14=5*2+4
5=4+1
说明5与14互素,存在5关于14的乘法逆元。
1=5-4=5-(14-5*2)=5*3-14
因此,5关于模14的乘法逆元为3。
分享到:
相关推荐
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
网络安全课程上机作业,用matlab编写的求解乘法逆元代码,如果有什么问题请留言。
试试吧!对于很多一直邱乘法逆元函数的人来说是一个非常好的选择
用C语言简单实现乘法逆元计算的代码(!只能计算正整数)
欧几米的算法乘法逆元算法.欧几米的算法乘法逆元算法
c/c++相关代码(cpp),乘法逆元有关模板整合(附有注释),顺便整合了了阶乘逆元,以及排列组合计算和Lucas的模板代码。
简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
很好的东西,很实用的东西,你懂的。基于Gf的多项式求乘法逆元,在很多时候都能够用到。
加密解密的基础,扩展欧几里得算法(辗转相除法)
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
matlab的M函数文件,附带了函数的使用说明了
乘法逆元,是指数学领域群G中任意一个元素a,都在G中有唯一的逆元a‘,具有性质a×a'=a'×a=e,其中e为该群的单位元
学信息安全的,一定要了解这个.乘法逆元是数论,密码学方面的
乘法逆元算法,扩展欧几里德,自己实现的,不过借鉴了网上的发达发达省份打发打发
用C实现乘法逆元,方法非常好
C语言简单实现乘法逆元计算的代码
Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
信息安全基础编程作业,双轨密码,钥控密码,乘法逆元,换位密码,Vigenere密码+源代码+文档说明 - 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才...
算法-乘法逆元(洛谷-P3811)(包含源程序).rar