Specifications

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

Stages

Builtin
Scalable
- scalable.ml
Zarithing

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.