哈斯克尔 – 在0回归时难倒

好的,轻微编辑,如示例编码99 18 108 45 =没有什么是实际上正确的,显然我无法正确阅读问题,因为99和18不是素数,所以我在代码中添加了检查功能：

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

这次我的问题似乎是编码53 73 151 90 =只是133
但是这个例子说它应该返回Just 3869而不是Just 133.

所以我向你们提出的问题是：我只是一个白痴而没有在我面前看到错误或者我的工作正常吗？

如果你想要的话,我会把isPrime代码放上去,但是它只检查是否为no.通过返回true或false来表示是否为素数.

你的问题是你将数字提升到一个大的功率,这导致非常大的数字,而Int通常包含多达64位的数字.结果,我们得到溢出,CPU将执行环绕.

通过直接计算公式来计算ab mod c通常不是一个好主意.我们可以在这里使用更聪明的方法：因为(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表示幂)ab mod c来计算,其中ab本身可以通过在所有递归级别执行模运算来非常大.我们在这里假设c小于Int的最大值的平方根.由于Int至少具有229-1的最小上限,这意味着它的工作时间长度为c≤23’170.如果你需要一个使用更高值的函数,那么你最好使用Int64(c的最大值是3’037’000’499)或整数(任意最大值).

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

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

但是,您的编码功能可以得到改进.你使用== 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