你的位置：
首页
>
IT圈
>
分数求模(取余)过程 乘法逆元
2024年6月2日发(作者：郁悦媛)
分数的模运算
在ECC加密算法中需要用到对分数的模运算，但大多的资料只给结果没有给计算过程，就
连初等数论书上面也找不到计算
方法，搜索了一下，终于在网上找到了相关资料，用的思路其实还是整数模运算的，直接
copy下来
下面是“分数”模运算的定义：
b, m互质（互为素数）
k = a/b (mod m) <=> kb = a (mod m)
这里求 x = 1/17 (mod 2668)
<=>
17x = 1 (mod 2668)
<=>
17x = 2668k + 1 （k∈整数）
取合适的k使得17|(2668k+1) 【应该是17能被(2668k+1)整除,也即17x mod 2668 = 1】
这里刚好17 | (2668 + 1)
所以k = 1, x = (2668+1)/17 = 157
当然，当k = 1 + 17n 时，
x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n
也符合条件（n任意整数）
但如果限定 2668 > x > 0，x是唯一的。
分数求模（取余）过程
[原创 2008-03-20 20:13:27]
字号：大 中 小
貌似分数是这样取余的，好好学习，天天向上！
计算a/x(mod n)
a/x (mod n)=a*x^-1(mod n)
计算1/x mod n
=x^(-1) mod n
就是求y，满足：
yx = 1 mod n
y是有限域F(n)上x的乘法逆元素
可用扩展的欧几里得算法求乘法逆元
int ExtEnclid(int
d
,int
f
)
这里的d就相当
于x，f相当于n
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(d>f) d=d+f-(d=f); //交换d和f使得d x1=1,x2=0,x3=f;
y1=0,y2=1,y3=d;
while(1)
{
if(y3==0) return 0; //没有逆元,gcd(d,f)=x3
if(y3==1) return y2; //逆元为y2,gcd(d,f)=1
k=x3/y3;
k=x3/y3
比如
t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
5/3=1；15/4=3
x1=y1,x2=y2,x3=y3;
y1=t1,y2=t2,y3=t3;
}
}
int main()
{
int d,f,res;
printf("you can try d=550 f=1769, d^-1 = 550, press ctrl+Z ");
printf("intput the d and f value:n");
2024年6月2日发(作者：郁悦媛)
分数的模运算
在ECC加密算法中需要用到对分数的模运算，但大多的资料只给结果没有给计算过程，就
连初等数论书上面也找不到计算
方法，搜索了一下，终于在网上找到了相关资料，用的思路其实还是整数模运算的，直接
copy下来
下面是“分数”模运算的定义：
b, m互质（互为素数）
k = a/b (mod m) <=> kb = a (mod m)
这里求 x = 1/17 (mod 2668)
<=>
17x = 1 (mod 2668)
<=>
17x = 2668k + 1 （k∈整数）
取合适的k使得17|(2668k+1) 【应该是17能被(2668k+1)整除,也即17x mod 2668 = 1】
这里刚好17 | (2668 + 1)
所以k = 1, x = (2668+1)/17 = 157
当然，当k = 1 + 17n 时，
x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n
也符合条件（n任意整数）
但如果限定 2668 > x > 0，x是唯一的。
分数求模（取余）过程
[原创 2008-03-20 20:13:27]
字号：大 中 小
貌似分数是这样取余的，好好学习，天天向上！
计算a/x(mod n)
a/x (mod n)=a*x^-1(mod n)
计算1/x mod n
=x^(-1) mod n
就是求y，满足：
yx = 1 mod n
y是有限域F(n)上x的乘法逆元素
可用扩展的欧几里得算法求乘法逆元
int ExtEnclid(int
d
,int
f
)
这里的d就相当
于x，f相当于n
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(d>f) d=d+f-(d=f); //交换d和f使得d x1=1,x2=0,x3=f;
y1=0,y2=1,y3=d;
while(1)
{
if(y3==0) return 0; //没有逆元,gcd(d,f)=x3
if(y3==1) return y2; //逆元为y2,gcd(d,f)=1
k=x3/y3;
k=x3/y3
比如
t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
5/3=1；15/4=3
x1=y1,x2=y2,x3=y3;
y1=t1,y2=t2,y3=t3;
}
}
int main()
{
int d,f,res;
printf("you can try d=550 f=1769, d^-1 = 550, press ctrl+Z ");
printf("intput the d and f value:n");