🔍 Step 1: Sieve of Eratosthenes
Find Small Primes up to √n
Prime Numbers
Composite Numbers
Sieve Algorithm Steps
- Create list of consecutive integers 2 to n
- Start with smallest prime p = 2
- Mark multiples of p (except p itself)
- Repeat until p² > n
🧪 Step 2: Miller-Rabin Primality Test
Candidate
982451653
Bit Length: 30
Round 1
Base: 7
✓ PASS
Base 7 Testn-1 = 982451652
2^r × d = 2^2 × 245612913
x = 7^d mod n = 245612913
Result: Probable Prime
Round 2
Base: 11
✓ PASS
Base 11 Testx = 11^d mod n = 245612913
x² mod n = 245612913
Result: Probable Prime
Round 3
Base: 13
✓ PASS
Base 13 Testx = 13^d mod n = 245612913
x² mod n = 245612913
Result: Probable Prime
PROBABLE
PRIME ✓
Confidence: 99.998%
If composite found, repeat with new candidate
Miller-Rabin Test Details
1. Express n-1 as 2^r × d where d is odd
2. For each witness base a:
3. Compute x = a^d mod n
4. If x = 1 or x = n-1, continue to next witness
5. For j = 1 to r-1:
a. x = x² mod n
b. If x = n-1, continue to next witness
c. If x = 1, declare composite
6. Declare composite if no early exit
Miller-Rabin Algorithm
- Write n-1 = 2^r × d (where d is odd)
- Choose random base a: 2 ≤ a ≤ n-2
- Compute x = a^d mod n
- If x = 1 or x = n-1, n passes this round
- For j = 1 to r-1, compute x = x² mod n
- If x = n-1 at any point, n passes this round
- Otherwise, n is composite
- Error probability: 1/4^k = 1/64 for k=3
Test Visualization
Step 1: Find d, r
n-1 = 2^r × d
982451652 = 2^2 × 245612913
Step 2: Compute x
x = a^d mod n
7^245612913 mod 982451653
Step 3: Check x
x = 1 or x = n-1?
x = 245612913 (continue)
Step 4: Square x
x = x² mod n
x = 245612913² mod 982451653
🔑 Step 3: RSA Key Generation
Prime p
1024 bits
First large prime number
×
Prime q
1024 bits
Second large prime number
=
RSA Modulus n
2048 bits
Public key component
🔒 Factoring n into p×q must be computationally infeasible
Key Sizes & Security Levels
1024-bit: Deprecated
2048-bit: Current
3072-bit: Future
4096-bit: High