# CSCE 314: Programming Languages

# Assignment 3

## Objective

In this assignment you'll practice tackling more complex problems; a critical skill to acquire is splitting large problems into a set of Haskell functions.

## Instructions

- This assignment asks you to implement a set of Haskell functions. Each of those functions can be defined with just a few lines of code. If your implementations start to get much longer, it may be a sign that there are less complicated solutions that you may be missing. Nevertheless, you may need to implement several functions (maybe as many as five) that you can put together to give a solution.

## Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a theorem with many uses, including as part of most RSA encryption implementations. The basic idea is as follows:

Given a number **x**, and a set of numbers **n _{i}**, we can compute a set of remainders

**a**modulo the

_{i}**n**. That is:

_{i}**a**=_{0}**x**mod**n**_{0}**a**=_{1}**x**mod**n**_{1}*etc.*

The Chinese Remainder Theorem states that for a given set of **a _{i}** and

**n**(assuming the

_{i}**n**are pairwise coprime), there is a unique number

_{i}**x**less than the product of the

**n**, which satisfies

_{i}**a**=

_{i}**x**mod

**n**for all

_{i}**i**. For example, if

**2**=**x**mod**7****1**=**x**mod**5****0**=**x**mod**3**

Then there is exactly one number less than 7×5×3=105 that meets all these criteria. There are a variety of algorithms for finding this number, but we only focus on the brute force algorithm in this question.

The brute force algorithm notes that for each (**a _{i}**,

**n**) pair, there is an infinite sequence of numbers that satisfy that value. If you form a sequence of these numbers for each pair in ascending order, the smallest number that appears in all sequences is your answer. For example, given the pairs (2,7), (1, 5), and (0, 3):

_{i}**2**=**x**mod**7**means**x**is one of: {2, 9, 16, 23, 30, 37, 44, 51, 58, 65, 72, 79, 86, 93, 100, …}**1**=**x**mod**5**means**x**is one of: {1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, …}**0**=**x**mod**3**means**x**is one of: {3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, …}

Examining those lists will show that **51** is the smallest number and also the only number
less than **105** that is so. (Note that for **x** greater than 105, we would
still be able to say that **51** = **x** mod **105**).

An alternate way is that you could take those lists in pairs: by combining the first two lists, you
would find that **16** = **x** mod **35**. Then, that would form a sequence {16,
51, 86, 121, …}, which, when combined with the sequence corresponding to
**0** = **x** mod **3**, would yield that **51** = **x** mod **105**.

Write a function, `crt`

, that takes as input a list of tuples, (**a _{i}**,

**n**), each with a remainder

_{i}**a**and a number

_{i}**n**. You can assume all the

_{i}**n**are pairwise coprime. From them, you should produce a new tuple, (

_{i}**a**,

**n**), where

**n**is the product of the

**n**, and

_{i}**a**is

**x**mod

**n**, or the smallest number that meets the criteria.

crt :: [(Integer, Integer)] -> (Integer, Integer)

As an example:

> crt [(2, 7), (0, 3), (1, 5)]

(51, 105)

**Note:** numbers are coprime if they do not have any common prime factors. So 10 = 2×5 and 21 =3×7 are coprime. The Chinese Remainder Theorem also has a less
restrictive formulation in which the numbers are not required to be coprime, but you can assume these will all be coprime in this question.

#### CRT Application: Secret Sharing System

In the film "Once Upon a Time in America", part of the plot hangs around a scenario in which the hero, Noodles, and his friends have a third party, Mo, keep a key. Noodles tells Mo that he is only to release the key when all of them appear.

A generalization of this, and perhaps one that is more useful in daily life, might
have **m** people sharing a secret **S** that can only be unlocked when
at least **k** are together. The CRT can be used to design this sort of
secret sharing system. The basic idea is: 1) choose **m** coprime
integers **n _{1} < n_{2} < … < n_{m}**, such that

**n**×…×

_{m-k+2}**n**×

_{m}< S < n_{1}**n**×…×

_{2}**n**, i.e.,

_{k}**S**is smaller than the product of any

**k**of these integers, but at the same time is greater than any

**k-1**of them. Then each person keeps a part,

**a**, where

_{1}, a_{2}, …, a_{n}**a**is computed as

_{i}**a**=

_{i}**S**mod

**n**. Using this one may determine

_{i}**S**, uniquely, from any set of

**k**or more shares, but not from fewer than

**k**. For more details, please see here.

## k-composite Numbers and Anagram Codes

Suppose a natural number **n** has the set of factors **{1, f _{1},
f_{2},…, f_{k}, n}** where its factors have been
written in increasing order so that the trivial factors,

**1**and

**n**, sandwich the rest. Since we have

**k**non-trivial factors, we say that

**n**is

*k*-composite. And, thus, prime numbers are the special case of 0-composite numbers.

### k-composites

Write a function using list comprehension that, given *k* produces the ordered (infinite) list of
positive *k*-composite numbers.

kcomposite :: Int -> [Int]

Here is an example of the function being called:

*Main> take 5 $ kcomposite 2 [6,8,10,14,15]

### A simple anagram code

The following describes a simple code that children sometimes use to exchange secret messages based on shuffling letters. The anagrams of a word are made by rearranging the letters
that make up the word. Here you'll be shuffling whole sentences including the spaces between the words. Given a piece of text, called *plaintext*, the encoding procedure involves
the following steps:

- If the number of letters in the plaintext sentence is 2-composite — fine.
- If not, take it up to the next 2-composite length by adding
*X*'s to the end. This is called padding.- For example:
*"LEND ME FIVE BUCKS"*has 18 characters, and 18 isn't 2-composite. The next 2-composite number is 21, so we add three*X*'s:*LEND ME FIVE BUCKSXXX*

- For example:
- The next step is to arrange the letters in a block. Since there are 21 letters, and 21 = 3 × 7, we write the letters in 3 rows, with 7 letters in each row. (The people communicating agree beforehand to have the larger number across.)
*L**E**N**D**M**E**F**I**V**E**B**U**C**K**S**X**X**X* - The message you send comes from reading down the columns:
*L UEFCNIKDVS EXM XEBX*

Implement a function to encrypt messages in the anagram code:

anagramEncode :: [Char] -> [Char]

Here's an example:

> anagramEncode "Chig-gar-roo-gar-rem/Chig-gar-roo-gar-rem/Rough Tough! Real Stuff!"

"Cihhg i-Tggo-augrga-hrr!-o roRo-eoga-algr a-Srrt-eurmfe/fmR!/oXCuXhgX"

Now, implement a function to decrypt messages in the anagram code. (You can assume that the pre-padded plaintext does not end with any X's, so you should strip the trailing padding off the text.)

anagramDecode :: [Char] -> [Char]

Here's one to test on:

"Tt hroeovrneegr tithshr aontwo n i ctba ysc tamlnoenn oestyo X bXseX"

### Acknowledgement

Chinese reminder theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Secret sharing: https://en.wikipedia.org/wiki Secret_sharing_using_the_Chinese_remainder_theorem

The idea for anagram codes comes from a pamphlet entitled "codes" written by Ray Hemmings.

### Check your answers

The test cases for this assignment are here. Of course, you can
test your `anagramEncode`

and `anagramDecode`

to ensure they are inverses of one another.