# Specifications

You’ll find in the subsquent sections all the specifications for the functions you’re expected to code down.

Stages

## Builtin

### builtin.ml

The OCaml built-in `mod`

and `/`

binary operators on `int`

correspond to what is called the *symmetric* Euclidean division. You
can test for yourself the fact `mod`

of a negative integer by a
positive one is not positive. If `x`

is a negative integer and `y`

a positive one then `x mod y`

is the opposite of ```
(abs x) mod
y
```

. The latter corresponding to the Euclidean division in the
mathematical sense. The `builtin.ml`

is there to tweak the `Ocaml`

Euclidean operators to fit our working definition.

Sign function

`val sign : int -> int`

returns 1 if non-negative and -1 otherwise.

Quotient of an integer by a non-zero integer number

`val quot : int -> int -> int`

This is the quotient in Euclidian division sense.

Modulo of an integer by a non-zero integer number

`val modulo : int -> int -> int`

Remainder of an integer by a non-zero integer in the Euclidean division sense. NOT OCAML DEFAULT! Positive integer between 0 (included) and absolute value of modulo (excluded) resulting from euclidian division of entry by modulo.

Division of an integer by a non-zero integer number

`val div : int -> int -> (int * int)`

Division of an integer by a non-zero integer \(b\) is the unique couple of integers \((q, r)\) such that \(a = bq + r\) and \(r\) is in interval \([0, |b|[\).

### basic_arithmetics.ml

Greater common divisor of two integers

`val gcd : int -> int -> int`

The greater common divisor is the biggest (thus positive) number dividing two non-zero integers.

Bézout relation of two integers

`val bezout : int -> int -> (int * int * int)`

Extended Euclidean division of two integers. Given non-zero entries \(a\), \(b\) computes triple \((u, v, d)\) such that \(au + bv = d\) and \(d\) is GCD of \(a\) and \(b\).

### power.ml

Computing power of integers efficiently.

Linear complexity power function

`val pow : int -> int -> int`

Fast exponentiation function

`val power : int -> int -> int`

Fast modular exponentiation function

`val mod_power : int -> int -> int -> int`

Computes power of a functions using the fast exponentiation strategy modulo a fixed integer base.

Fast modular exponentiation function modulo prime

`val prime_mod_power : int -> int -> int -> int`

Think : Little Fermat Theorem.

### test_primes.ml

Focus here is on testing whether a number is prime. The two first
options are the one given by screening *all* possibile divisors, the
second to use Fermat Little Theorem to test for primality ; if it is
not satisfied then argument is not prime otherwise we get a milder
chance of it being so.

Deterministic primality test

`val is_prime : int -> bool`

Tests if argument is prime screening through possible divisors.

Pseudo-primality test

`val is_pseudo_prime : int -> (int list) -> bool`

Tests if first argument is prime using Fermat Little Theorem againt a list of integers given as second argument.

### generate_primes.ml

To build up cryptosystem we’ll need to generate big enough prime numbers for latter use. That also involves us saving and loading them.

Init Eratosthenes sieve

`val init_eratosthenes : int -> (int list)`

Returns list composed of 2 and then odd integers starting at 3 till given argument.

Eratosthene sieve

`val eratosthenes : int -> (int list)`

Write list of prime numbers into file

`val write_list_primes : int -> string -> unit`

Write a list of prime numbers up to argument into a txt file at path given by string.

Load list of primes into OCaml environment

`val read_list_primes : string -> (int list)`

Argument is the file path you wish to load list of prime numbers from.

Double primes

`val double_primes : int -> (int -> bool) -> (int * int) list`

Finding couples of primes where second entry is twice the first plus 1. First argument is an upper bound on searched for primes. Second is a function testing for (pseudo)-primality.

Finding twin primes

`val twin_primes : int -> (int -> bool) -> (int * int) list`

Finding couples of primes where second entry is the first plus 2. First argument is a positive integer bounding searched for primes. Second is a function testing for (pseudo)-primality.

### ciphers.ml

This file contains main function for basic cryptosystems. There are three cphering algorithms we’ll be looking into : Cesar cipher, RSA and El Gamal.

Cesar’s cipher encryption

`val encrypt_cesar : int -> (int list) -> int -> (int list)`

First argument is (private) key, second is a list of integers (word) to cipher and last is the number of letters in the alphabet we’re using for writing down message (for extended ASCII table should be set to 255).

Cesar’s cipher decryption

`val decrypt_cesar : int -> (int list) -> int -> (int list)`

First argument is (private) key, second is a list of integers (word) to decipher and last is the number of letters in the alphabet we’re using for writing down message (for extended ASCII table should be set to 255).

Generate an RSA public and private keys

`val generate_keys_rsa : int -> int -> ((int * int) * (int * int))`

Both arguments are prime numbers that need to be distinct. Output is a couple of public key \((n,e)\), private key \((n,d)\).

Encryption using RSA cryptosystem

`val encrypt_rsa : int -> (int * int) -> int`

First argument is integer to encrypt, second is a couple \((n,e)\) corresponding to public key.

Decryption using RSA cryptosystem

`val decrypt_rsa : int -> (int * int) -> int`

First argument is integer to encrypt, second is a couple \((n,d)\) corresponding to private key.

Generate El Gamal public data

`val public_data_g : int -> (int * int)`

Generates a pair \((g, p)\) where \(p\) is prime and \(g\) is an element of \(\mathbb{Z}/p\mathbb{Z}\) having high enough order. The prime \(p\) is supposed to be of the form \(2q + 1\) where \(q\) is prime.

Generate El Gamal public and private keys

`val generate_keys_g : (int * int) -> (int * int)`

Generates a pair \((kA,a)\) of keys where \(kA\) is congruent to \(g^a\) modulo \(p\). \(kA\) is the public key and \(a\) is the private key.

El Gamal encryption process

`val encrypt_g : int -> (int * int) -> int -> (int * int)`

First argument is an integer to be ciphered, the second is the El Gamal public data \((g, p)\) and last is public key.

El Gamal decryption process

`val decrypt_g : (int * int) -> int -> (int * int) -> int`

First argument is an El Gamal encrypted message, the second is the private key and last is El Gamal cryptosystem public data \((g, p)\).

### break_ciphers.ml

We’re only concerned by breaking the RSA cryptosystem for the time being.

Brute forcing RSA cryptosystem

`val break : int * 'a -> (int * int)`

It is only about factoring a product of two primes.

### encoding_msg.ml

The file `encoding_msg.ml`

to implement naive string encodings using
an indexed alphabet. The fun is still to send one another an encrypt
intelligible message.

Encode a string having alphanumeric ASCII characters

`val encode : string -> int -> int`

First argument is the message to encode, second is the number of
bits on which to encode a character. Restricted ASCII table leaves 7
bits per character. A character is encoded on 7 bits (ASCII code
ranging from \(0\) to \(127\)), use `Char.code c`

to encode
character `c`

. A string can hence be encoded
by *concatenating* each character encoding.

Decode a string containing alphanumeric ASCII characters

`val decode : int -> int -> string`

First argument is integer representing encoded message to decode,
second is number of bits on which to encode a character. Restricted
ASCII leaves 7 bits per character, use `Char.chr n`

to convert number
`n`

to a character.

### chinese_remaindert.ml

This file contains a first implementation of the Chinese Remainder map
and its inverse. It uses built-in type `int`

.

Chinese Remainder map

`val crt_image : int -> (int list) -> (int list)`

First argument is a positive integer we’re willing to map using the Chinese Remainder map. The second is a list of pairwise coprimes positive integers.

Inverse to Chinese Remainder map

`val crt_solver : int -> (int list) -> (int list) -> int`

First argument is a positive integer, second a list of pairwise coprime factors of first argument, last argument is a list of remainders modulo previous coprime factors.

## Scalable

The `scalable`

module is here to extend previous functions to a set
of integers not having bounded number of digits. In computer
programming, there are efficient and unified ways to treat both
previous and upcoming data types. Most of you still do not have the
means to go through these techniques; start simple grow
ambition. Note that using higher order functions here would
fully make sense.

We’ll represent unbounded integers simply using `OCaml`

built-in `int lists`

. To represent a given integer `x`

we will
write it using a list of zeroes and ones corresponding to its binary
decomposition. The first bit of the list will be the sign bit :
`0`

for a positive integer and `1`

for a negative number. The
remaining bits (the tail) correspond to the absolute value `|x|`

. To
simplify the code we’re expecting from you, the binary decomposition of
`|x|`

is read with respect to the list order, starting with the bit corresponding to \(2⁰\),
then the bit corresponding to \(2¹\) etc.
For instance the bitarray corresponding to `+11`

is the list `[0; 1; 1; 0; 1]`

.
Thus the binary decomposition of `11`

corresponds to the tail `[1; 1; 0; 1]`

instead of `1011`

as usually expected.

In the `scalable`

specifications below, the previous data type will be called **bitarray**.
A **bitarray** represents an integer number, positive or negative. Furthermore,
we will call **natural** a **bitarray** with no sign bit. It is assumed to represent
the binary decomposition of a non-negative integer. For both **bitarrays** and **naturals**,
`0`

is represented by the empty list.

Only `scalable.ml`

is documented subsequently. All other files have
same specifications as in the `builtin.ml`

case up to integer
types. You are invited to look through the available `.mli`

files
for more details.

### scalable.ml

Convert built-in `int`

into bitarray

`val from_int : int -> int list`

Convert bitarray of built-in size to built-in `int`

`val to_int : int list -> int`

Prints bitarray as binary number on standard output

`val print_b : int list -> unit`

Comparing naturals

`val compare_n : int list -> int list -> int`

Output is \(1\) if first argument is bigger than second \(-1\) if its smaller and \(0\) in case of equality.

Bigger inorder comparison operator on naturals

`val (>>!) : int list -> int list -> bool`

Returns true if first argument is bigger than second and false otherwise.

Smaller inorder comparison operator on naturals

`val (<<!) : int list -> int list -> bool`

Returns true if first argument is smaller than second and false otherwise.

Bigger or equal inorder comparison operator on naturals

`val (>=!) : int list -> int list -> bool`

Returns true if first argument is bigger or equal to second and false otherwise.

Smaller or equal inorder comparison operator on naturals

`val (<=!) : int list -> int list -> bool`

Returns true if first argument is smaller or equal to second and false otherwise.

Comparing two bitarrays

`val compare_b : int list -> int list -> int`

Output is \(1\) if first argument is bigger than second \(-1\) if it is smaller and 0 in case of equality.

Bigger inorder comparison operator on bitarrays

`val (>>) : int list -> int list -> bool`

Returns true if first argument is bigger than second and false otherwise.

Smaller inorder comparison operator on bitarrays

`val (<<) : int list -> int list -> bool`

Returns true if first argument is smaller than second and false otherwise.

Bigger or equal inorder comparison operator on bitarrays

`val (>>=) : int list -> int list -> bool`

Returns true if first argument is bigger or equal to second and false otherwise.

Smaller or equal inorder comparison operator on bitarrays

`val (<<=) : int list -> int list -> bool`

Returns true if first argument is smaller or equal to second and false otherwise.

Sign of a bitarray

`val sign_b : int list -> int`

Absolute value of bitarray

`val abs_b : int list -> int list`

Addition of two naturals, output is a natural

`val add_n : int list -> int list -> int list`

Difference of two naturals

`val diff_n : int list -> int list -> int list`

Output is a natural. Assume first argument bigger than second.

Addition of two bitarrays

`val add_b : int list -> int list -> int list`

Difference of two bitarrays

`val diff_b : int list -> int list -> int list`

Shifts bitarray to the left by a given natural number

`val shift : int list -> int -> int list`

Multiplication of two bitarrays

`val mult_b : int list -> int list -> int list`

Quotient of two bitarrays

`val quot_b : int list -> int list -> int list`

Modulo of a bitarray against a positive one

`val mod_b : int list -> int list -> int list`

Euclidean division of two bitarrays

`val div_b : int list -> int list -> (int list * int list)`

## Zarithing

You’ll find nothing here : read your given files and roam the internet.