Miller–Rabin primality test

The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known. Gary L. Miller discovered the test in 1976; Miller's version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980. Similarly to the Fermat and Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing. The property is the following. For a given odd integer n > 2, let’s write n − 1 as 2sd where s is a positive integer and d is an odd positive integer. Let’s consider an integer a, called a base, which is coprime to n. Then, n is said to be a strong probable prime to base a if one of these congruence relations holds: for some 0 ≤ r < s. The idea beneath this test is that when n is an odd prime, it passes the test because of two facts: by Fermat's little theorem, (this property alone defines the weaker notion of probable prime to base a, on which the Fermat test is based); the only square roots of 1 modulo n are 1 and −1. Hence, by contraposition, if n is not a strong probable prime to base a, then n is definitely composite, and a is called a witness for the compositeness of n. However, this property is not an exact characterization of prime numbers. If n is composite, it may nonetheless be a strong probable prime to base a, in which case it is called a strong pseudoprime, and a is a strong liar. Thankfully, no composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the Carmichael numbers).

Measurement and characterization of room impulse responses

Thomas Batschelet

Room acoustics refers to the audio capture of an enclosed room. It can be seen as its color and fully describes the characteristics of the room, including the shape, size or the population. The goal of the project is to set up a database of Room impulse responses which will be useful in many fields in order to test algorithms. This document covers the way to set up equipment and successfully capture one of those room impulse responses.

2016

Primality Testing

Kamal Tahiri Jouti

Since the discovery of the utility of the numbers, the human being tried to differentiate them. We decide between them according to whether they are even or odd. Or, according to the fact that they are prime or composite. A natural number n >1 is called a prime number if it has no positive divisors other than 1 and n. Therefore, other numbers that are not prime have other divisors. That is why we call them composite numbers because we can write them : n = p*q with {p,q} ≠ {1,n}. The problem has always been to decide whether a number is prime or not. To answer this problem, many algorithms have been created like the Trial Division. It uses the property which says that the biggest divisor of n is smaller or equal to the square root of n. But for numbers that exceed 30 digits, it will take more than 10^13 years to know the answer. So, the interest would be to create an algorithm using mathematical bases which would answer to this question as fast as possible. This is what we will see in this project. The study of prime numbers became really important to code texts. Cryptography is one of the most important application of prime numbers theory. At the beginning, it was only used to code texts during the wars and more recently it was used for other applications, like the security of an account. Fist of all, I will focus on randomized algorithms for primality testing. Then, I will focus on a deterministic algorithm that I have implemented.

2006

Measurement and characterization of room impulse responses

Randomized and Deterministic Primality Testing

Primality Testing

Randomized and Deterministic Primality Testing

Primality Testing

Measurement and characterization of room impulse responses