In today’s Programming Praxis we have to implement the Affine-Shift Cipher. Let’s get going, shall we?

A quick import:

import Data.Char

Since both encoding an decoding have roughly the same structure, we’re going to abstract that out into a function.

convert :: (Int -> Int) -> String -> String
convert f = map (chr . (\i -> f (i - 65) `mod` 26 + 65) . ord . toUpper)

For decoding, we need to calculate the modular inverse of a number.

inverse :: Int -> Int -> Int
inverse x n = f (mod x n) 1 where
f 0 _ = error "Numbers not coprime"
f 1 a = a
f y a = let q = - div n y in f (n + q * y) (mod (q * a) n)

Encoding and decoding is then simply a case of calling the convert function with the correct argument.

encode :: Int -> Int -> String -> String
encode a b = convert (\i -> a*i + b)
decode :: Int -> Int -> String -> String
decode a b = convert (\i -> inverse a 26 * (i-b))

All that’s left to do is test if everything works correctly.

main :: IO ()
main = do print $ encode 5 8 "BONSAICODE" == "NAVUIWSAXC"
print $ decode 5 8 "NAVUIWSAXC" == "BONSAICODE"

All clear.

### Like this:

Like Loading...

*Related*

Tags: affine, bonsai, cipher, code, Haskell, kata, praxis, programming, shift

This entry was posted on December 15, 2009 at 12:47 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

December 17, 2009 at 2:23 am |

I’m afraid your code doesn’t work as exected.

Your inverse function is wrong… (see comment@programmingpraxis)

Try with a=7 and see…

Cheers.

December 17, 2009 at 9:51 am |

Whoops. Fixed it, thanks.