Algorithms
The time complexity describes the amount of computer time it takes to run an algorithm. It is estimated by counting the number of elementary operations performed by the algorithm. Since an algorithm’s running time may vary among different inputs of the same size, one commonly considers the worst-case time. Algorithmic complexities are classified according to the type of function appearing in the big O notation. Here are some examples:
| Name | Time complexity |
|---|---|
| Constant time | $\mathcal{O}(1) $ |
| Logarithmic time | $\mathcal{O}(\log n) $ |
| Linear time | $\mathcal{O}(n) $ |
| Linearithmic time | $\mathcal{O}(n \log n)$ |
| Quadratic time | $\mathcal{O}(n^2) $ |
| Polynomial time | $2^{\mathcal{O}(\log n)} = poly(n)$ |
| Exponential time | $2^{poly(n)}$ |
Multiplication algorithms
Schoolbook multiplication
Consider this example $102 \times 257$:
Scalar multiplication
Let $\mathbb{G}$ be a commutative group under the addition law ($+$) and let $G \in \mathbb{G}$ be its generator. The group has an order $p$. We define a scalar multiplication $k \cdot G$ as $\underbrace{G+…+G}_\text{$k$~times}$.
- Consider $105 \cdot G$. How many additions does it involve?
- Now consider the binary decomposition of $105 = 2^6 + 2^5 + 2^3 + 2^0$. It can be written as
$105 = ((((((((((1 · 2 + 1) · 2) + 0) · 2) + 1) · 2) + 0) · 2) + 0) · 2) + 1$. Given that a doubling (multiplication by 2) has the same cost as an addition, how many additions $105 \cdot G$ involves?
Primes are of great theoretical and practical value in cryptography. A primality test is an algorithm for determining whether an input number is prime or not.
Naive but deterministic
The simplest primality test is trial division: given an input number, $n$, check whether it is divisible by any prime number between 2 and $\sqrt{n}$. If so, then $n$ is composite. Otherwise, it is prime.
The prime number theorem: the distribution of primes is $π(n) \sim n/\log(n)$ where $π(n)$ is the prime-counting function (the number of primes less than or equal to $n$) and $\log(n)$ is the natural logarithm of $n$.
Polynomials are functions of the form: $$ f(x) = a_0 + a_1 x + \dots + a_n x_n $$ where $n$ is any non-negative integer and $a_0,\dots,a_n$ any fixed numbers with $a_n \ne 0$. We call:
- $n$ the polynomial degree,
- $a_0,\dots,a_n$ the polynomial coefficients and
- $a_0$ the polynomial constant term.
Polynomial Interpolation
- Suppose that $f(x)$ is a polynomial of degree 2, i.e. of the form $f(x) = a_0 + a_1 x + a_2 x^2$. Let $f(1)=2$, $f(2)=5$, and $f(4)=2$. Find $f(x)$.
- Can you quickly write down a non-zero polynomial that vanishes at 1, 3 and 100?
- Same problem as before, but now with the two extra conditions: $f$ must have degree $\leq 3$ and also $f(50)=1$.
- Same problem as before, but now with the following conditions: $f$ must have degree $\leq 4$, $f(50)=1$ and $f(4)=3$.
- Now suppose that we have $n+1$ points $(x_0,y_0), (x_1,y_1), \dots, (x_n,y_n)$ such that $f(x_i)=y_i$ for $0 \leq i \leq n$. Can you generalize the above approach to find $f(x)$?
Secret Sharing
Raibi Jamila, often referred to simply as “Raibi,” is a beloved yogurt-based drink that has become a staple in Moroccan culture. Many have tried to replicate the drink, but none have succeeded in capturing its unique flavor. The secret recipe for Raibi is known only to a few select individuals, who have sworn to keep it a secret. To prevent these individuals from sharing the secret and to ensure it is never lost, we are going to construct a scheme that allows the secret to be shared among a group of people in such a way that the secret cannot be revealed unless a minimum number of the group’s members act together to pool their knowledge.