我很困扰这个使用整数和分数模10乘法的密码学问题。
以下是方程式:
7 * (4/11) mod 10 =?
我知道应该将它转换为整数,因为模运算符不能用于分数,但我无法解决这个问题。显然,
7 * (4/11) = 28/11,
但是我无法得到分数的模10。老师想要精确答案,而不是小数。任何帮助都将不胜感激!
我很困扰这个使用整数和分数模10乘法的密码学问题。
以下是方程式:
7 * (4/11) mod 10 =?
我知道应该将它转换为整数,因为模运算符不能用于分数,但我无法解决这个问题。显然,
7 * (4/11) = 28/11,
但是我无法得到分数的模10。老师想要精确答案,而不是小数。任何帮助都将不胜感激!
请看这里: "有没有可能对分数进行模运算" 在 math.stackexchange.com 上。
定义模函数的一种自然方式是
a (mod b) = a − b ⌊a / b⌋
其中 ⌊⋅⌋ 表示 floor 函数。这是 Graham、Knuth、Patashnik 的著名书籍 Concrete Mathematics 中使用的方法。
这将给你 1/2(mod3)=1/2。
为了解决您的问题,您有 a = 7 * (4/11) = 28/11
,和 b = 10
。
a / b
= (28/11)/10 = 0.25454545...
⌊a/b⌋
= 0
b ⌊a/b⌋
= 0 * 0 = 0
a - b ⌊a/b⌋
= 28/11 - 0 = 28/11
这意味着你的答案是28/11。
Wolfram Alpha 同意我的观点 并给出28/11
作为精确结果。Google也同意,但将其作为十进制数2.54545454.....给出。
一个分数是一个精确的答案而不是一个小数。
(28 mod 10)/(11 mod 10)
。 - Cœur确实,8是正确答案。
7*4/11 mod 10
的意思是我们要看 7*4*x mod 10
,其中x是模数10下11的模反元素,也就是说 11*x mod 10 = 1
。
对于 x=1
是成立的 (11*1 mod 10 = 1
)
因此 7*4*x mod 10
变成了 7*4*1 mod 10
,结果为 28 mod 10 = 8
(mod 10)
时,意味着每个项都使用隐含的mod 10
运算进行评估。
1/2 mod 10
未定义,因为2和10不互质。
所以,这是讲师给出的正确答案。我不知道他是怎么想出来的:
7 4/11 mod 10 = ((7 4) mod 10)(11−1 mod 10) mod 10
= (28 mod 10)(1 mod 10) mod 10
= (8)(1) mod 10
= 8 mod 10
from fractions import Fraction
from math import fmod
print (fmod(Fraction(28, 11), 10))
结果将是2.545454545454。所以我猜8是错误的。
x/y mod 10
等于[x mod (10*y)]/y
(这将是一个有理数值)。 - Peter