Mod 哈斯克尔家庭作业

Question

我的作业是提供一个计算 'x^y mod n' 的函数 - 对于任何 n < （sqrt maxint32）

所以我开始这样做：

modPow :: Int -> Int -> Int -> Int 
modPow x y n = (x `mod` n) ^ (y `mod` n) `mod` n

对于任意数量的n，这似乎都可以正常工作，尽管我的下一个家庭作业问题涉及使用x^n mod n = x（Camichael数字）并且我永远无法让modPow工作。

因此，我使用伪代码进行模幂运算，制作了另一个 modPow，-来自维基百科：

modPow2 :: Int -> Int -> Int -> Int 
modPow2 x y n 
 = loopmod 1 1
  where
   loopmod count total = if count > y
                          then total
                           else loopmod (count+1) ((total*x) `mod` n)

现在可以正确地为我的下一个问题生成正确的答案，(x^n mod n = x) -用于检查 Camichael 数字。

尽管如此，modPow2 不适用于大量“y”（堆栈溢出！！）

我如何调整 modPow2，以便在 y > 的情况下不再出现堆栈溢出？ 10,000（但仍小于 maxint 32 的 sqrt - 约为 46,000）

或者是否对我的原始 modPow 进行了修复，以便它可以与 x^n mod n = x 一起使用？ （我总是做 560 561 561 作为输入，它给我返回 1 而不是 560 （561 是一个卡迈克尔数字，所以应该给我返回 560）

非常感谢。

Answer 1

您的 modPow 公式是错误的，您不能只使用 y mod n 作为指数，这会导致错误的结果。例如：

Prelude> 2^10
1024
Prelude> 2^10 `mod` 10
4
Prelude> 2^(10 `mod` 10) `mod` 10
1

要获得更好的 modPow 函数，您可以使用 x2n+1 = x2n ⋅ x 和x2n = xn ⋅ xn 而对于乘法你实际上< em>可以简单地使用因子的mod。

Answer 2

您从哪里获得 modPow 的公式？

(x ^ y) `mod` n = ((x `mod` n) ^ (y `mod` φ n)) `mod` n 其中 φ 是欧拉 totient 函数。

Answer 3

这可能是因为参数 total 是延迟计算的。

如果您使用 GHC，您可以通过放置 ! 来使 loopmod 在 total 中严格。在参数前面，即

loopmod count !total = ...

另一种方法是强制计算总计，如下所示： 将最后一行替换为

else if total == 0 then 0 else loopmod (count+1) ((total*x) `mod` n)

这不会改变语义（因为 0*x 无论如何都是 0，因此提醒必须为 0也）并且它强制拥抱在每次递归中评估总数。

Answer 4

如果您正在寻找实现（ a^d mod n ）那么

powM::Integer->Integer->Integer->Integer
powM a d n
   | d == 0 = 1
   | d == 1 = mod a n
   | otherwise = mod q n  where
       p = powM  ( mod ( a^2 ) n ) ( shiftR d 1 ) n
       q = if (.&.) d 1 == 1 then mod ( a * p ) n else p