9

这是一个软问题，但在下面的代码中，标有“凯撒密码”的部分有很多重复。处理这个问题的“Haskell”方法是什么？我应该做一个更高阶的函数吗？我想过这个，但我不知道什么是有意义的。是否有我可以定义用于制作密码的“密码”类型？

此外，我知道它可能看起来有点过度设计，因为我在两个地方进行相同的错误检查，但我认为从每个功能“意味着”的角度来看这是有道理的。建议？

import Data.Char
import Control.Applicative
import Control.Monad
import Math.NumberTheory.Powers

--Helpers

extendedGcd::Integer->Integer->(Integer, Integer)
extendedGcd a b | r == 0 = (0, 1)
                | otherwise = (y, x - (y * d))
                where
                    (d, r) = a `divMod` b
                    (x, y) = extendedGcd b r

modularInverse::Integer->Integer->Maybe Integer
modularInverse n b | relativelyPrime n b = Just . fst $ extGcd n b
                   | otherwise = Nothing
                   where
                        extGcd = extendedGcd

relativelyPrime::Integer->Integer->Bool
relativelyPrime m n = gcd m n == 1 

textToDigits::String->[Integer]
textToDigits = map (\x->toInteger (ord x - 97)) 

digitsToText::[Integer]->String
digitsToText = map (\x->chr (fromIntegral x + 97)) 

--Caesar Ciphers

caesarEncipher::Integer->Integer->Integer->Maybe Integer
caesarEncipher r s p | relativelyPrime r 26 = Just $ mod (r * p + s) 26
                     | otherwise = Nothing

caesarDecipher::Integer->Integer->Integer->Maybe Integer
caesarDecipher r s c | relativelyPrime r 26 = mod <$> ((*) <$> q <*> pure (c - s)) <*> pure 26
                     | otherwise = Nothing
    where
        q = modularInverse r 26

caesarEncipherString::Integer->Integer->String->Maybe String
caesarEncipherString r s p | relativelyPrime r 26 = fmap digitsToText $ mapM (caesarEncipher r s) plaintext
                           | otherwise = Nothing
    where
        plaintext = textToDigits p

caesarDecipherString::Integer->Integer->String->Maybe String
caesarDecipherString r s c | relativelyPrime r 26 = fmap digitsToText $ mapM (caesarDecipher r s) ciphertext
                           | otherwise = Nothing
    where
        ciphertext = textToDigits c

bruteForceCaesarDecipher::String->[Maybe String]
bruteForceCaesarDecipher c = caesarDecipherString <$> [0..25] <*> [0..25] <*> pure c
4

2 回答 2

15

创建一个Key类型，并使用智能构造函数

样板的主要来源似乎r是可逆的重复检查，以及其逆的计算。encipher将您的操作（例如）分为两个步骤是有意义的：首先检查，然后实际加密。这样，您只需编写一次检查部分。

实现这一点的一种方法是定义一个保证只CaesarKey包含有效键的新类型。我们可以使用智能构造函数来保证这个不变量，如下所示：

{-# LANGUAGE RecordWildCards #-} -- for the Key{..} syntax below

-- invariant: r and q are inverses mod 26. 
-- To ensure this invariant, we only export the 'caesarKey' smart constructor,
-- and not the underlying 'Key' constructor
data CaesarKey = Key { r :: Integer, s :: Integer, q :: Integer }

caesarKey :: Integer -> Integer -> Maybe CaesarKey
caesarKey r s = Key r s <$> invertMod r 26

-- ciphers
encipher :: CaesarKey -> Integer -> Integer
encipher Key{..} p = mod (r * p + s) 26

decipher :: CaesarKey -> Integer -> Integer
decipher Key{..} c = mod (q * (c - s)) 26

encipherString :: CaesarKey -> String -> String
encipherString key = digitsToText . map (encipher key) . textToDigits

decipherString :: CaesarKey -> String -> String
decipherString key = digitsToText . map (decipher key) . textToDigits

invert在键上定义

现在我们可以利用 Daniel 的观察，decipher即 just encipher，但定义在不同的键（即“逆键”）上。所以让我们定义一个反转键的操作：

-- turns a key suitable for encoding into one suitable for decoding, and vice versa.
--   @invert (invert key) = key@
invert :: CaesarKey -> CaesarKey
invert (Key r s q) = Key q ((26-q)*s) r

现在我们可以抛弃decipheranddecipherString函数，因为它们是不必要的（即最好使用它们invert）。

做一个allKeys函数

从概念上讲，我们可以分为bruteForceCaesarDecipher两个任务：首先，生成所有可能的密钥；其次，用每个键解码文本。让我们在代码中实现它：

allKeys :: [CaesarKey]
allKeys = catMaybes $ caesarKey <$> [1,3..25] <*> [1,3..25]

bruteForceCaesar :: String -> [String]
bruteForceCaesar str = [encipherString key str | key <- allKeys]

除了提供更易于理解的代码（在我看来）之外，以这种方式拆分代码的优点是我们只构建一次键列表，而不必为我们要解码的每个字符串重新构建键。

还要注意其他一些小的变化：

完整的代码在这里。

于 2012-04-02T02:41:14.207 回答
9

请注意，加密和解密使用完全相同的算法，因此您应该有一个函数来执行该算法。

transform :: Integer -> Integer -> Integer -> Integer
transform mult trans n = (mult * n + trans) `mod` 26

然后检查互质性并计算每个字符的模逆是浪费的，因此我建议

caesarEncipherString r s p
    | gcd r 26 == 1 = Just $ digitsToText $ map (transform r s) $ textToDigits p
    | otherwise     = Nothing

caesarDecipherString r s c = do
    mi <- modularInverse r 26
    caesarEncipherString mi (mi*(26-s)) c

对于蛮力，

bruteForceCaesarDecipher c = caesarEncipherString <$> [1, 3 .. 25] <*> [0 .. 25] <*> pure c

因为使用所有可能的密钥进行加密与解密相同，只是顺序不同，工作量更少；很明显，偶数不能与 26 互质。

于 2012-04-02T01:37:25.803 回答