使用分数的模算法

Question

我被这个密码学问题困住了，用整数和分数mod 10的乘法。

下面是方程式：

7 * (4/11) mod 10 =?

我知道我应该把它转换成一个整数，因为mod运算符不适用于分数，但我无法计算出这个。显然，

7 * (4/11) = 28/11,

但我不能得到10的分数。老师想要的是确切的答案，而不是十进制。任何帮助都将不胜感激！

Answer 1

8

8确实是正确的答案。

7*4/11 mod 10意味着我们要看的是7*4*x mod 10，其中x是11模10的模逆，这意味着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

Answer 2

看看这里："https://math.stackexchange.com/questions/864568/is-it-possible-to-do-modulo-of-a-fraction“在math.stackexchange.com上。

定义模块函数的一种自然方法是 A (mod b) =a−b⌊a / b⌋ 其中，地板功能表示⌊⋅⌋。这是格雷厄姆，克努斯，帕塔什尼克在有影响力的书“具体数学”中使用的方法。 这将给出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 同意我的意见并给出了28/11的确切结果。谷歌也同意，但作为小数，2.54545454.

分数是，是一个精确的答案，而不是十进制。

Answer 3

我可以推测这个表示法是错误的，整个表达式应该在每个中间阶段用mod 10进行评估。既然( 11 mod 1)是1，那么答案是(7 * 4) mod 10 = 8。

想象一下，一个计算器只支持那些数字。

我不是说这是正确的答案，我同意28/11是正确的答案，但我试图进入教授的领导。这在密码学中很常见，每一次计算都执行mod 2^ 256左右。