haskell - 被 0 返回困扰

Question

好的，稍作编辑，例如 encode 99 18 108 45 = Nothing 实际上是正确的，显然我无法正确阅读问题，因为 99 和 18 不是素数，所以我添加了一个将函数 checkin 代码中:

coprime :: Int -> Int -> Bool
coprime a b = gcd a b == 1

check :: Int -> Int -> Bool
check p q = (isPrime p) && (isPrime q)

phi :: Int -> Int -> Int
phi p q = (p - 1) * (q - 1)

encrypt :: Int -> Int -> Int -> Int -> Int
encrypt p q m e = powmod m e (p * q)

encode :: Int -> Int -> Int -> Int -> Maybe Int
encode p q m e |check p q && coprime (phi p q) e = Just (encrypt p q m e)
           |otherwise = Nothing

这次我的问题似乎是encode 53 73 151 90 = Just 133但该示例表示它应该返回 Just 3869 而不是 Just 133。

所以我想问你们的是:我是不是个白痴，没有看到眼前的错误，或者我的工作还好吗？

如果你愿意的话，我也会放上isPrime代码，但它只是检查是否为“否”。通过返回 true 或 false 来判断是否为素数。

Answer 1

您的问题是您将数字提高到大次幂，这会导致非常大数字，而Int通常最多包含64 - 位数字。结果，我们出现溢出，CPU 将执行回绕。

通过直接计算公式来计算 a^b mod c 通常不是一个好主意。我们可以在这里使用更聪明的方法:since (a×b) mod c == ((a mod c) × (b mod c)) mod c，我们可以通过计算功率来利用这个属性，从而需要最少的内存:

powmod :: Int -> Int -> Int -> Int
powmod _ 0 _ = 1
powmod a b c | even b = ab2
             | otherwise = mod (a * ab2) c
    where ab2 = powmod (mod (a * a) c) (div b 2) c

因此，我们在这里计算O(log b)(其中b为值幂)a^b mod c，其中 a^b 本身可以通过在所有递归级别执行模运算而变得非常大。我们这里假设c小于Int最大值的平方根。由于 Int 的最小上限至少为 2²⁹-1，这意味着只要 c ≤ 23'170，它就有效。如果您需要一个适用于更高值的函数，那么您最好使用 Int64(c 的最大值为 3'037'000'499)或 Integer (任意最大值)。

现在我们可以将此函数用于加密函数:

encrypt :: Int -> Int -> Int -> Int
encrypt p q m e = powmod m e (p * q)

但是，您的 encode 函数还可以改进。您使用 == True，这是不必要的，因为 True == True 是 True，而 False == True > 是False。

encode :: Int -> Int -> Int -> Int -> Maybe Int
encode p q m e | coPrime (phi p q) e = Just (encrypt p q m e)
               |otherwise = Nothing

现在我们得到:

Prelude> encode 99 18 108 45
Just 1134
Prelude> encode 37 17 23 48
Nothing