How can number theory help you optimize algorithms?

2 Prime numbers

Prime numbers are integers that have exactly two positive divisors: 1 and themselves. They are the building blocks of all other integers, since any integer can be written as a product of prime numbers in a unique way. Prime numbers are important for algorithms because they can be used to test for divisibility, generate random numbers, and encrypt data. For example, one of the most popular encryption algorithms, RSA, relies on the fact that it is easy to multiply two large prime numbers, but hard to factorize their product.

4 Euler's totient function

Euler's totient function, denoted by phi(n), is a function that counts how many positive integers less than or equal to n are relatively prime to n. Two integers are relatively prime if they have no common divisors other than 1. For example, phi(12) is 4, because there are 4 numbers less than or equal to 12 that are relatively prime to 12: 1, 5, 7, and 11. Euler's totient function has many applications in cryptography, number theory, and combinatorics. For instance, one of the properties of Euler's totient function is that a^phi(n) mod n = 1 for any integer a that is relatively prime to n. This is known as Euler's theorem, and it is used to prove Fermat's little theorem and to compute modular inverses.

5 Chinese remainder theorem

The Chinese remainder theorem is a theorem that states that if n_1, n_2, ..., n_k are pairwise coprime integers (meaning they have no common divisors other than 1), and a_1, a_2, ..., a_k are any integers, then there exists a unique integer x, modulo the product of n_1, n_2, ..., n_k, such that x mod n_i = a_i for all i. For example, if n_1 = 3, n_2 = 5, and n_3 = 7, and a_1 = 2, a_2 = 3, and a_3 = 4, then x = 23 is the unique solution, modulo 105, to the system of equations x mod 3 = 2, x mod 5 = 3, and x mod 7 = 4. The Chinese remainder theorem can be used to solve simultaneous congruences, speed up calculations, and implement parallel algorithms.

6 Fast exponentiation

Fast exponentiation is a technique that allows you to compute a^n mod m for large values of a, n, and m in a more efficient way than using the naive method of multiplying a by itself n times and then taking the modulus. The idea is to use binary representation of n and exploit the properties of modular arithmetic. For example, to compute 7^13 mod 11, you can write 13 as 1101 in binary, and then use the following steps:

7^13 mod 11 = (7^8 * 7^4 * 7^1) mod 11

7^8 mod 11 = ((7^4)^2) mod 11 = (5^2) mod 11 = 3

7^4 mod 11 = ((7^2)^2) mod 11 = (5^2) mod 11 = 3

7^1 mod 11 = 7

(7^8 * 7^4 * 7^1) mod 11 = (3 * 3 * 7) mod 11 = 9

This way, you only need to perform 5 multiplications and 5 moduli, instead of 13 multiplications and 13 moduli. Fast exponentiation is useful for algorithms that involve modular exponentiation, such as encryption, decryption, and primality testing.