Skip to content

Generating (Random) Primes

links: AC2 TOC - Number-Theoretic Algorithms and Hardness Assumptions - Index


Generating Random k-Bit Primes

Generating-Random-k-Bit-Primes.png

  • First number can't be 0 because it has to be at least 2k1 and last bit is 1 to avoid even numbers

Testing Primality (Naive Approach)

Testing-Primality-Naive-Approach.png

Testing Primality (Probabilistic Approach)

Testing-Primality-Probabilistic-Approach.png

Pseudocode-isPrime.png

Instead of completely testing all possibilities and making sure that a number is prime, a function isComposite() is used to decide that n is likely prime. Users can decide themselves how sure they want to be if n is prime by running the algorithm multiple times.

Fermat

Testing-Primality-Fermat.png

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

Testing-Primality-Miller-Rabin.png

  • the Miller-Rabin primality test is most widely used in practice
  • the failure probability of a single test is α0.25

Example

Suppose we have an odd integer n>3 that we want to test for primality, and we've chosen a random integer a in the range [2,n2].

  1. Write n1 as 2rd, where d is an odd number (r must be as large as possible).
  2. Compute x=admodn using fast exponentiation.
  3. If x equals 1 or n1, then n passes the test for base a.
  4. Otherwise, square x repeatedly mod n up to r1 times. If, in any of these squarings, we get n1, then n passes the test for base a.
  5. If we haven't found 1 or n1 by this point, then n is composite, and we say that a is a witness to the compositeness of n.

Let's consider an example. Suppose we want to check whether n=221 is prime, and we choose a=174.

  1. We can write 220 as 2255, so r=2 and d=55.
  2. Compute x=17455mod221, which equals 47.
  3. Since x is not 1 or 220, we square x to get 472mod221=220.
  4. At this point, we've found 220 (which is n1), so 221 passes the test for base 174. Either 221 is prime or 174 is a strong liar for 221

We do the same for a=137

  1. Compute x=13755mod221, which equals 188.
  2. Since x is not 1 or 220, we square x to get 1882mod221=205.
  3. We squared x once (r1) and have not reached x=1 or x=220 hence 137 is a witness that 221 is not prime

links: AC2 TOC - Number-Theoretic Algorithms and Hardness Assumptions - Index