9

これはちょっとした質問ですが、次のコードでは、「シーザー暗号」とマークされたセクションに多くの重複があります。これに対処するための「ハスケル」の方法は何ですか？高階関数を作成する必要がありますか？私はそれについて考えましたが、何が理にかなっているのかわかりません。暗号を作成するために定義できる「暗号」タイプはありますか？

また、2つの場所で同じエラーチェックを行っているという意味で、少し過剰に設計されているように見えるかもしれませんが、各機能の「意味」の観点からは理にかなっていると思います。提案？

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その逆行列の計算であるようです。操作（例）を2つのステップに分割することは理にかなっていencipherます。最初にチェックし、次に実際に暗号化します。このようにして、チェック部分を1回だけ書き込むことができます。

これを実現する1つの方法は、有効なキーのみ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キーで定義

ここで、ダニエルの観察を利用することができます。これはdecipher、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

そして今では、decipherとdecipherString関数は不要なので破棄できます（つまり、invert代わりに使用することをお勧めします）。

allKeys関数を作成する

bruteForceCaesarDecipher概念的には、 2つのタスクに分割できます。最初に、可能なすべてのキーを生成します。次に、各キーでテキストをデコードします。これをコードで実装しましょう：

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

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

（私の意見では）理解しやすいコードを提供することに加えて、この方法でコードを分割すると、デコードするすべての文字列のキーを再構築する必要がなく、キーのリストを1回だけ作成するという利点があります。

他のいくつかの小さな変更にも注意してください。

  • 私は鍵catMaybes :: [Maybe a] -> [a]を捨てていましたNothing

  • 私はダニエルの提案に従って、bruteForceCaesarより効率的にする方法を学びました。

完全なコードはここにあります。

于 2012-04-02T02:41:14.207 に答える
9

暗号化と解読はまったく同じアルゴリズムを使用するため、1つの関数でそれを実行する必要があることに注意してください。

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

可能なすべてのキーによる暗号化は解読と同じであるため、順序が異なり、作業が少なくなります。そして、偶数が互いに素ではないことはあまりにも明白です。

于 2012-04-02T01:37:25.803 に答える