我有以下的模方程:
327𝑥≡ ℎ*327*327*𝑥 ≡ ℎ*327 ≡ 1 (mod 1009) and so
𝑥 ≡ ℎ*327x ≡ ℎ*1 ≡ ℎ (mod 1009).
So I have to find out what ℎ is.
3*327=981≡-28(mod1009)
我不明白的是3是怎么推导出来的,你用什么公式来求3的
我知道-28%1009=981,但我不知道作者是如何推导出知道乘以3得到一个答案,从而创建一个mod来获得这个数字的。这里的任何帮助都将不胜感激
完整的公式在这里,我知道这可以用EGCD解决,但我试图理解作者是如何以他所做的方式解决这个问题的:
The question:
In [1505]: (327*327*108)%1009
Out[1505]: 327
Only 108 (as far as i know( will return 327. So the equation is:
(327*327*x)%1009 = 327. What is the quickest way to solve for this step by step.
( What i don't understand is how the author solved for the 3 here in the step listed below ( 3*327 =981 ≡−28 (mod 1009) )
The Answer ( which worked )
gcd(327,1009)=1 so there is an ℎ so that 327∗ℎ≡1(mod1009) so if 327*327*𝑥≡327(mod1009) then
327𝑥≡ℎ*327*327*𝑥≡ℎ*327≡1(mod1009) and so
𝑥≡ℎ*327𝑥≡ℎ*1≡ℎ(mod1009).
So I have to find out what ℎ is.
3 * 327 = 981 ≡ −28 (mod 1009)
327=28 * 12 − 9 so
327≡(−3 * 327) * 12 − 9 ( mod 1009 )
378 * 327≡−9 (mod 1009)
28=3 * 9 + 1
-3 * 327 ≡ 3 * (-37 * 327)+1 (mod 1009)
108* 327≡1 (mod 1009)
So ℎ≡108 and 𝑥≡108 (mod 1009).
=====
And indeed 108* 327 *327=35316 *327= (1009 *35+1) *327=1009 *(35 *327)+327.
好的,根据回答,我提出了这个程序,它似乎验证了结果:
def getmod4(A, N):
multiplier = N//A
a = A * multiplier
b = -(N - a)
va = b%N
assert va == a
# or, the next e,d can be done by a // b ??
e = a // b #math.gcd((va|1)-1, (b|1)-1)
#f = -(va//e)
c = math.gcd((A|1)-1, (b|1)-1)
c = abs(b)//c - c
d = abs(b) * c - A
assert ((-multiplier * A) * c - d)%N == A
print(f"Equation: {abs(b)} * {c} - {d}: {abs(b) * c - d}")
print(f"Verification: ((-{multiplier}*{A}) * {c} - {d})%{N} = {((-multiplier*A) * c - d)%N}")
return abs(b) * c - d
结果:
In [3079]: getmod4(327,1009)
Equation: 28 * 12 - 9: 327
Verification: ((-3*327) * 12 - 9)%1009 = 327
Out[3079]: 327
In [3081]: getmod4(261,10099)
Equation: 181 * -20 - -3881: 261
Verification: ((-38*261) * -20 - -3881)%10099 = 261
Out[3081]: 261
这只是division with remainder
计算1009/327,得到大约3.085626911。这说明1009=3*327+R,其中余数R小于327
相关问题 更多 >
编程相关推荐