0Pricing
Cryptology Academy · Lesson

Prime Numbers & Factorization

Learn why prime numbers are the backbone of public-key crypto.

Prime Numbers & Factorization is a free Cryptology Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Cryptology Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

Welcome

Prime numbers are divisible only by 1 and themselves. They are the atoms of multiplication — and the bedrock of RSA, Diffie-Hellman, and many other crypto systems.

Definition & Examples

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... A number is prime if its only positive divisors are 1 and itself. 1 is NOT prime by convention.

Fundamental Theorem of Arithmetic

Every integer > 1 can be factored into primes in exactly one way (up to ordering). 60 = 2² × 3 × 5. This uniqueness is what makes factoring-based crypto work.

Trial Division

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Only need to check up to √n — if no factor found below √n, n is prime.

Sieve of Eratosthenes

To find all primes up to N: start with a list of numbers 2..N. Cross out multiples of 2, then 3, then 5, etc. Remaining numbers are prime. Runs in O(N log log N).

Primality Testing: Miller-Rabin

For large numbers (2048 bits) trial division is too slow. Miller-Rabin is a probabilistic test: run it 40 times and the probability of error is < 4^(-40).

Integer Factorization

Given n = p × q, finding p and q is the integer factorization problem. If n is 2048 bits, the best known algorithms take 2^112 operations — currently infeasible.

Why RSA Uses Two Large Primes

RSA modulus n = p × q. Knowing n but not p,q makes it hard to compute the private key. The security relies entirely on the hardness of factoring n.

Generating Large Primes

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oracle: generate random odd number, test with Miller-Rabin, repeat until prime.

Safe Primes & Strong Primes

A safe prime p = 2q+1 where q is also prime. Safe primes resist certain attacks on DH. RSA sometimes uses strong primes to prevent Pollard's p-1 attack.

Prime Gaps & Infinity

Euclid proved there are infinitely many primes in 300 BCE. The twin prime conjecture (primes p, p+2 exist infinitely) is still unproven. We never run out of primes for crypto.

Quick Check

Why does RSA use large prime numbers?

Recap

You understand prime numbers and factorization. Next we apply Euler's totient function and GCD — the final math tools needed before RSA.

Frequently asked questions

Is the “Prime Numbers & Factorization” lesson free?

Yes — the full text of “Prime Numbers & Factorization” is free to read here on the web, and the Cryptology Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Cryptology Academy course, upgrade to CoddyKit PRO.

What will I learn in “Prime Numbers & Factorization”?

Learn why prime numbers are the backbone of public-key crypto. You practise Cryptology Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Cryptology Academy?

No prior experience is required. Cryptology Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Prime Numbers & Factorization” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Cryptology Academy lesson?

Yes. Every Cryptology Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Binary & Hexadecimal Fundamentals
  2. Modular Arithmetic Basics
  3. Prime Numbers & Factorization
  4. GCD, Euler's Totient & Number Theory Intro
← Back to Cryptology Academy