使用分数的模运算

Question

我被这个使用整数和分数相乘的密码学问题困住了 mod 10.

公式如下：

7 * (4/11) mod 10 =?

我知道我应该将其转换为整数，因为 mod 运算符不适用于分数，但我无法弄清楚这个。显然，

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

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

Answer 1

看看这里：“Is it possible to do modulo of a fraction" on math.stackexchange.com.

One natural way to define the modular function is

a (mod b) = a − b ⌊a / b⌋

where ⌊⋅⌋ denotes the floor function. This is the approach used in the influential book Concrete Mathematics by Graham, Knuth, Patashnik.

This will give you 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 agrees with me and gives 28/11 as the exact result. Google 也同意，但以小数形式给出，2.54545454.....

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

Answer 2

我可以推测符号是错误的，整个表达式应该在每个中间阶段在 mod 10 中计算。由于 ( 11 mod 1 ) 为 1，则答案为 (7 * 4) mod 10 = 8。

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

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

Answer 3

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 4

原来的问题可能应该这样写，因为这有不同的含义。 When the (mod 10) is written at the end，这意味着每个术语都使用隐含的 mod 10 操作进行评估。

$\sqrt{foo}$

这个问题有点奇怪，因为 10 的模值不是通用的，因为它不是质数。比如下面的不能求值，因为1/2 mod 10没有定义，因为2和10不是互质的。

$\sqrt{foo}$

Answer 5

所以，这是老师的正确答案。我不知道他是怎么想到这个的：

    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

Answer 6

使用Python：

from fractions import Fraction
from math import fmod

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

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

使用分数的模运算

Modular arithmetic using fractions

modulo

8