Generating (Random) Primes¶
links: AC2 TOC - Number-Theoretic Algorithms and Hardness Assumptions - Index
Generating Random k-Bit Primes¶
- First number can't be 0 because it has to be at least
and last bit is 1 to avoid even numbers
Testing Primality (Naive Approach)¶
Testing Primality (Probabilistic Approach)¶
Instead of completely testing all possibilities and making sure that a number is prime, a function
Fermat¶
This check is not enough because Carmichael Numbers would return false even though they aren't prime (should return true). Miller-Rabin algorithm solves this.
Miller-Rabin¶
- the Miller-Rabin primality test is most widely used in practice
- the failure probability of a single test is
Example
Suppose we have an odd integer
- Write
as , where is an odd number ( must be as large as possible). - Compute
using fast exponentiation. - If
equals or , then n passes the test for base . - Otherwise, square
repeatedly mod up to times. If, in any of these squarings, we get , then passes the test for base . - If we haven't found
or by this point, then is composite, and we say that is a witness to the compositeness of .
Let's consider an example. Suppose we want to check whether
- We can write
as , so and . - Compute
, which equals . - Since
is not or , we square to get . - At this point, we've found
(which is ), so passes the test for base . Either is prime or is a strong liar for
We do the same for
- Compute
, which equals . - Since
is not or , we square to get . - We squared
once ( ) and have not reached or hence is a witness that is not prime
links: AC2 TOC - Number-Theoretic Algorithms and Hardness Assumptions - Index