模运算中使用分数

Question

模运算中使用分数

8

我很困扰这个使用整数和分数模10乘法的密码学问题。

以下是方程式：

7 * (4/11) mod 10 =?

我知道应该将它转换为整数，因为模运算符不能用于分数，但我无法解决这个问题。显然，

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

但是我无法得到分数的模10。老师想要精确答案，而不是小数。任何帮助都将不胜感激！

- ComputerScientist123

1

你需要做的第一件事是定义当x不是整数时，x mod 10的含义。如果x和y是整数，则一个定义可以是x/y mod 10等于[x mod (10*y)]/y（这将是一个有理数值）。 - Peter

6个回答

4

8

确实，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

- Cabbie407

1

我可以猜测这个符号是错误的，整个表达式应该在每个中间阶段都以mod 10进行评估。由于(11 mod 1)为1，所以答案是(7 * 4) mod 10 = 8。

想象一个只支持个位数的计算器。

我不是说这是正确的答案，我同意28/11是正确的答案，但我试图进入教授的思维模式。这在密码学中很常见，其中每个计算都是在mod 2 ^ 256或类似的模数下执行的。

- Mark Lakata

谢谢大家，我很感激你们的帮助。我会回复并提供讲师想要的确切答案。 - ComputerScientist123

1

这是原问题可能应该写成的方式，因为它有不同的含义。当在末尾写上(mod 10)时，意味着每个项都使用隐含的mod 10运算进行评估。

$\sqrt{foo}$

问题有点奇怪，因为模数10不是通用的，因为它不是质数。例如，以下内容无法计算，因为1/2 mod 10未定义，因为2和10不互质。

$\sqrt{foo}$

- Mark Lakata

1

所以，这是讲师给出的正确答案。我不知道他是怎么想出来的：

    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

- ComputerScientist123

0

使用Python：

from fractions import Fraction
from math import fmod

print (fmod(Fraction(28, 11), 10))

结果将是2.545454545454。所以我猜8是错误的。

- Milbrae

2

你能解释一下你做了什么以及你是如何得出解决方案的吗？ - MZaragoza

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Wai Ha Lee · Accepted Answer

请看这里: "有没有可能对分数进行模运算" 在 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.....给出。

一个分数是一个精确的答案而不是一个小数。