有限域(Finite field)中计算倒数(Multiplicative Inverse)是否会出现负数?求12437模24357的倒数(Multiplicative Inverse)?

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/03 00:15:19

有限域(Finite field)中计算倒数(Multiplicative Inverse)是否会出现负数?求12437模24357的倒数(Multiplicative Inverse)?
有限域(Finite field)中计算倒数(Multiplicative Inverse)是否会出现负数?
求12437模24357的倒数(Multiplicative Inverse)?

有限域(Finite field)中计算倒数(Multiplicative Inverse)是否会出现负数?求12437模24357的倒数(Multiplicative Inverse)?
设12437x≡1(mod 24357)
推出12437x-1=y24357
即12437x-y24357=1
这是二元一次不定方程
该方程有整数解当且仅当12437与24357互素
用辗转相除法求得12437与24357的确互素,
且-5041*12437+2574*24357=1(x和y的一个特解)
于是x≡-5014(mod 24357)
即x≡19343(mod 24357)