Course contentsShow
← Mathematics
Lesson 2762 of 3,12154. Number TheoryFree lesson

The RSA Setup: Choosing Primes

Learn how to select two large distinct primes p and q, and compute their product n = pq as the modulus.

The RSA Setup: Choosing Primes

What you'll learn: How to select two large distinct primes p and q and compute their product n = pq as the modulus for RSA encryption.

Why This Matters

In public-key cryptography, RSA relies on the practical difficulty of factoring large numbers. The security of the entire system hinges on how we choose our building blocks: two prime numbers.

Choosing the Primes

The first step in RSA setup is selecting two large, distinct prime numbers, conventionally called p and q. Here's what "large" means in practice:

  • Each prime should be hundreds or thousands of digits long (in real-world applications, 1024-bit or 2048-bit primes are common)
  • The primes must be distinct: p ≠ q
  • They should be randomly chosen to prevent attackers from guessing them

Think of p and q as the secret ingredients in a recipe. Once mixed together, it's nearly impossible for anyone to reverse-engineer the original components from the final dish.

Computing the Modulus

Once you've chosen p and q, compute their product:

n = pq

This number n is called the RSA modulus. It will be public—everyone can see it—but factoring it back into p and q is computationally infeasible when the primes are large enough.

Why This Works

The modulus n becomes the foundation for all RSA operations. Its totient φ(n) = (p − 1)(q − 1) drives the relationship between encryption and decryption (thanks to Euler's Theorem, which you've already studied). However, computing φ(n) is easy only if you know p and q—the secret factors.

Key Takeaway: RSA setup begins by choosing two large distinct primes p and q, then computing n = pq as the public modulus; the security depends on keeping p and q secret while n is public.