Cryptology Academy · Lesson

Prime Numbers & Factorization

Q: Is the “Prime Numbers & Factorization” lesson free?

Yes — the full text of “Prime Numbers & Factorization” is free to read here on the web. 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. The Cryptology Academy course includes 4 lessons in total.

Q: 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, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.

Q: 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.

Q: 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.

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

Lesson 3 of 413 steps

Prime Numbers & Factorization is a free Cryptology Academy lesson on CoddyKit. This is 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, and your progress syncs across the web and the CoddyKit app. The Cryptology Academy course includes 4 lessons in total.

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?

Answer it in the interactive lesson

Recap

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

Free to start

Learn Cryptology Academy with an AI tutor — free

Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.

Courses: 67
Lessons: 261

Start learning free View the full course

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. 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. The Cryptology Academy course includes 4 lessons in total.

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, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.

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

Binary & Hexadecimal Fundamentals
Modular Arithmetic Basics
Prime Numbers & Factorization
GCD, Euler's Totient & Number Theory Intro

← Back to Cryptology Academy