Affine Cipher
Encode and decode text with the affine cipher, which maps letter number i to (a * i + b) mod 26.
Adapted from Exercism’s problem specification (MIT). Listed under Encoding & Ciphers.
// FILE: affine_cipher.nomi
//# The affine cipher: letter number `i` becomes letter `(a * i + b) mod 26`.
//# Digits pass through unchanged, and everything else is dropped.
once alphabet = Iter.to_vector('a'..='z')
once letter_count = PositiveInt.try_from(Vector.length(alphabet))!
/// Each lowercase letter's number, from 0 for `a`.
once letter_numbers =
Iter.zip(alphabet, 0..letter_count)
|> Iter.to_map()
/// An encryption key. `a` must be coprime with 26, or no key decrypts it.
pub struct Key
a: Int
b: Int
end
/// Why a phrase cannot be encrypted or decrypted.
pub enum Error
NotCoprime
end
/// The ciphertext of `phrase` under `key`, in lowercase groups of five.
pub fn encode(phrase: String, key: Key) -> Result<String, Error>
_ = inverse(key.a)?
phrase
|> translate(fn i -> key.a * i + key.b)
|> Iter.chunks(5)
|> Iter.map(String.join)
|> String.join(" ")
|> Ok()
end
/// The plaintext of `phrase` under `key`, with no spaces.
pub fn decode(phrase: String, key: Key) -> Result<String, Error>
a_inverse = inverse(key.a)?
phrase
|> translate(fn y -> a_inverse * (y - key.b))
|> String.join()
|> Ok()
end
/// The `x` with `a * x` one more than a multiple of 26, which exists only
/// when `a` and 26 are coprime.
fn inverse(a: Int) -> Result<Int, Error>
0..letter_count
|> Iter.find(fn x -> Int.modulo(a * x, letter_count) == 1)
|> Maybe.to_result(.NotCoprime)
end
/// Each letter and digit of `text`, a letter moved to the letter `step`
/// gives for its number, and a digit kept.
fn translate(text: String, step: (Int) -> Int) -> List<String>
text
|> String.lowercase()
|> String.to_codepoints()
|> Iter.flat_map(&shift(&1, step))
|> Iter.map(Codepoint.to_string)
|> Iter.to_list()
end
fn shift(cp: Codepoint, step: (Int) -> Int) -> Maybe<Codepoint>
if Codepoint.is_digit(cp) then return Some(cp)
Map.get(letter_numbers, cp)
|> Maybe.map(fn i -> Vector.get(alphabet, Int.modulo(step(i), letter_count))!)
end
// FILE: affine_cipher_test.nomi
import
affine_cipher
affine_cipher.Key
end
group "encode"
test "encodes"
[
("encode yes", "yes", Key{a: 5, b: 7}, "xbt"),
("encode no", "no", {a: 15, b: 18}, "fu"),
("encode OMG", "OMG", {a: 21, b: 3}, "lvz"),
("encode O M G", "O M G", {a: 25, b: 47}, "hjp"),
("encode mindblowingly", "mindblowingly", {a: 11, b: 15}, "rzcwa gnxzc dgt"),
("encode numbers", "Testing,1 2 3, testing.", {a: 3, b: 4}, "jqgjc rw123 jqgjc rw"),
("encode deep thought", "Truth is fiction.", {a: 5, b: 17}, "iynia fdqfb ifje"),
(
"encode all the letters",
"The quick brown fox jumps over the lazy dog.",
{a: 17, b: 33},
"swxtj npvyk lruol iejdc blaxk swxmh qzglf",
),
]
|> subtests (description, phrase, key, expected), description
assert affine_cipher.encode(phrase, key) == Ok(expected)
end
end
test "encode with a not coprime to m"
assert affine_cipher.encode("This is a test.", {a: 6, b: 17}) == Err(.NotCoprime)
end
end
group "decode"
test "decodes"
[
("decode exercism", "tytgn fjr", Key{a: 3, b: 7}, "exercism"),
(
"decode a sentence",
"qdwju nqcro muwhn odqun oppmd aunwd o",
{a: 19, b: 16},
"anobstacleisoftenasteppingstone",
),
("decode numbers", "odpoz ub123 odpoz ub", {a: 25, b: 7}, "testing123testing"),
(
"decode all the letters",
"swxtj npvyk lruol iejdc blaxk swxmh qzglf",
{a: 17, b: 33},
"thequickbrownfoxjumpsoverthelazydog",
),
(
"decode with no spaces in input",
"swxtjnpvyklruoliejdcblaxkswxmhqzglf",
{a: 17, b: 33},
"thequickbrownfoxjumpsoverthelazydog",
),
(
"decode with too many spaces",
"vszzm cly yd cg qdp",
{a: 15, b: 16},
"jollygreengiant",
),
]
|> subtests (description, phrase, key, expected), description
assert affine_cipher.decode(phrase, key) == Ok(expected)
end
end
test "decode with a not coprime to m"
assert affine_cipher.decode("Test", {a: 13, b: 5}) == Err(.NotCoprime)
end
endok encode / encodes (8 cases)
ok encode / encode with a not coprime to m
ok decode / decodes (6 cases)
ok decode / decode with a not coprime to m
test result: ok. 16 passed, 0 failed
How it’s written
Section titled “How it’s written”- The key is a
pub struct Key { a, b }, and the one error, anathat shares a factor with 26, isError.NotCoprime. - The modular inverse is found by search,
Iter.findover0..26for thexwitha * x mod 26 == 1. The search fails exactly whenais not coprime with 26, so one function both checks the key and gives the inverse; the extended Euclidean algorithm is not worth it for 26 candidates. encodechecks the key with_ = inverse(key.a)?before it starts, since it does not need the inverse.translatetakes the step as a function,fn i -> key.a * i + key.borfn y -> a_inverse * (y - key.b), so encoding and decoding share it.Int.modulobrings a negative result back into0..26, where%would leave it negative.- Letters go to numbers through a map, a
oncethat pipesIter.zip(alphabet, 0..letter_count)intoIter.to_map(), written stacked to start from the pairs, and back withVector.get(...)!, which cannot miss because the index is reduced mod 26. - Each table names
Keyin its first row only (Key{a: 5, b: 7}); the rows after it write{a: 15, b: 18}, which the first row makes aKey, so the table needs no annotation.