RSA Prime Number Calculator
Discover how prime numbers protect passwords and secret messages across the internet. Create sample key pairs, encrypt test messages, and see how the math works.
How RSA Turns Two Primes into a Digital Lock
How do two prime numbers work like a padlock anyone can snap shut, but only you can unlock? Follow these 5 simple steps:
p = 61 and q = 53. Real internet security picks huge random primes hundreds of digits long. n = 61 × 53 = 3,233. Everyone gets to see n. Multiplying takes a split second, but working backwards to split 3,233 into p and q is the hard puzzle. (61 − 1) × (53 − 1) = 60 × 52 = 3,120. This counts numbers below n that share no factors with it. Without knowing p and q, finding this count is practically impossible. e that shares no common factors with 3,120 (other than 1). Here, e = 17 works cleanly. d so that 17 × d divided by 3,120 leaves remainder 1. Reversing Euclid’s division steps gives d = 2,753 (because 17 × 2,753 = 46,801 = 15 × 3,120 + 1). The “Square-and-Multiply” Power Shortcut
How does your device find the remainder of huge powers like M^e ÷ n without freezing or running out of memory? Instead of multiplying one by one, computers use the square-and-multiply shortcut: they turn the exponent into binary (1s and 0s), repeatedly square the running answer, and keep only the remainder at every single step!
Cracking Close Primes: Why p and q Must Be Far Apart
If two secret primes are chosen too close to each other, an attacker can start right near the square root of n, check simple differences of two squares, and crack the secret key in seconds! Test a number below to watch:
Historic RSA Numbers & Factoring Milestones
From the original 1977 challenge to modern encryption standards protecting the web, see how factoring abilities grew over decades:
| Challenge | Key Size | Digits | Year Cracked | Method Used | Status | Try |
|---|---|---|---|---|---|---|
| RSA-100 | 330 bits | 100 | 1991 | Quadratic Sieve | Cracked (Early Challenge) | |
| RSA-110 | 364 bits | 110 | 1992 | Quadratic Sieve | Cracked | |
| RSA-120 | 397 bits | 120 | 1993 | Quadratic Sieve | Cracked | |
| RSA-129 | 426 bits | 129 | 1994 | Quadratic Sieve | Cracked (1977 Puzzle Solved) | |
| RSA-130 | 430 bits | 130 | 1996 | Number Field Sieve | Cracked (New Method Record) | |
| RSA-140 | 463 bits | 140 | 1999 | Number Field Sieve | Cracked (~2,000 CPU days) | |
| RSA-150 | 496 bits | 150 | 2004 | Number Field Sieve | Cracked | |
| RSA-155 | 512 bits | 155 | 1999 | Number Field Sieve | Cracked (Retired 512-bit Keys) | |
| RSA-160 | 530 bits | 160 | 2003 | Number Field Sieve | Cracked | |
| RSA-170 | 563 bits | 170 | 2009 | Number Field Sieve | Cracked | |
| RSA-180 | 596 bits | 180 | 2010 | Number Field Sieve | Cracked | |
| RSA-190 | 629 bits | 190 | 2010 | Number Field Sieve | Cracked | |
| RSA-200 | 663 bits | 200 | 2005 | Number Field Sieve | Cracked | |
| RSA-210 | 696 bits | 210 | 2013 | Number Field Sieve | Cracked | |
| RSA-220 | 729 bits | 220 | 2016 | Number Field Sieve | Cracked | |
| RSA-230 | 762 bits | 230 | 2020 | Number Field Sieve | Cracked | |
| RSA-240 | 795 bits | 240 | 2019 | Number Field Sieve | Cracked (900 core-years) | |
| RSA-250 | 829 bits | 250 | 2020 | Number Field Sieve | Cracked (2,700 core-years) | |
| RSA-768 | 768 bits | 232 | 2009 | Number Field Sieve | Cracked (Retired 768-bit Keys) | |
| RSA-2048 | 2048 bits | 617 | Current | Unbroken Target | Safe Today (~300T CPU Years) |
4 Step-by-Step Examples
Clear step-by-step examples showing how digital keys are built, used, and sometimes broken:
1. Multiply primes: n = 61 × 53 = 3,233.
2. Find partner count: (61 − 1) × (53 − 1) = 60 × 52 = 3,120.
3. Pick public lock power e = 17 (shares no factors with 3,120).
4. Find private unlock power d = 2,753.
5. Lock message 65 (‘A’): remainder of 65^17 ÷ 3233 = 2,790.
6. Unlock message: remainder of 2790^2753 ÷ 3233 = 65 (original letter returned!).
In 1977, writer Martin Gardner published an RSA puzzle with a $100 prize to break a 129-digit number. The inventors guessed it would take quadrillions of years to solve. But in 1994, 600 volunteers linked computers together over 8 months and split the number into a 64-digit prime and a 65-digit prime, revealing the secret sentence: “THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE”.
Suppose someone chooses two prime numbers right next to each other, like 10,007 and 10,009. Because they are so close together, testing numbers starting right at the square root (10,008) cracks the secret code on the very first try! To prevent this, safe systems always pick primes that are far apart.
To speed up decoding, programmers sometimes tried using a small private key. Mathematician Michael Wiener showed in 1990 that if the unlock key is too small, an attacker can quickly calculate the private key and break the lock in milliseconds. Safe systems always keep private keys full-sized.
How Fast Computers Build vs. Break Locks
Making keys and locking messages takes fractions of a second, while breaking large locks takes years or longer:
| Task / Method | Purpose | Speed | Memory Needed | What It Means |
|---|---|---|---|---|
| Creating Keys | Setup | Very fast | Tiny | Tests random primes in under a second |
| Locking Data (e = 65,537) | Security | Instant | Tiny | Takes just 17 quick remainder steps |
| Unlocking Data (Fast Shortcut) | Security | Very fast | Tiny | 4× faster using secret primes p and q |
| Checking Factors One by One | Cracking | Hopelessly slow | Tiny | Unusable once numbers pass 14 digits |
| Cycle Search (Pollard’s Method) | Cracking | Fast for small locks | Tiny | Finds smaller factors up to ~18 digits |
| Quadratic Sieve | Cracking | Moderate | Large | Fastest method for numbers under 100 digits |
| Number Field Sieve | Cracking | Best classical attack | Supercomputer | Top method on regular computers above 100 digits |
| Shor’s Quantum Method | Quantum | Fast (future) | Large quantum chip | Requires huge error-free quantum computers |
Real-World Security Mistakes & Future Locks
Even strong prime math can fail if a computer builds keys carelessly. Here are four famous lessons from internet security history:
In 2006, a developer cleaning up a minor warning in Debian Linux accidentally broke its random number generator. For two years, millions of servers could only produce 32,767 possible keys instead of trillions—so hackers could simply guess all 32,767 keys in seconds.
Millions of smartcards and security chips tried to create prime numbers faster by forcing primes into a repeating formula pattern. Researchers discovered that pattern leaked clues inside the public key, allowing strong 2048-bit locks to be cracked in ~17 days on rented cloud computers for under $100.
Older websites reused one permanent RSA key to lock secret session data—meaning anyone who recorded encrypted traffic could unlock it years later if that key leaked. Modern HTTPS creates brand-new temporary keys for every single visit, while using RSA mainly to confirm a website’s identity.
Because large future quantum computers could factor huge prime products quickly, global standards groups released next-generation locks in 2024 built on complex multi-dimensional grid puzzles instead of prime factoring—keeping future internet traffic safe.
Related Security & Factoring Tools
Frequently Asked Questions
How do prime numbers make RSA encryption work?
RSA security works because multiplying two prime numbers is fast and easy, but untangling their product back into the original primes without knowing them is nearly impossible for computers.
What is the difference between the public key and private key in RSA?
The public key is shared with everyone so anyone can lock (encrypt) a message sent to you. The private key is kept secret on your device so only you can unlock (decrypt) the message.
Why is 65,537 commonly chosen as the public lock power?
65,537 is a special prime number (2¹⁶ + 1). In binary, it is written as 10000000000000001 (only two 1s), which lets computers lock messages in just 17 fast squaring and multiply steps while staying secure.
Why must secret primes p and q be kept far apart?
If the two secret prime numbers are too close to each other, an attacker can quickly guess near their average and break the secret lock in seconds. Safe systems always make sure the two primes are far apart.
What is the difference between classroom RSA and real-world RSA?
Classroom RSA locks raw numbers directly. Real-world internet security adds random padding to every message before locking it, making sure identical messages always look completely different when sent.
Will quantum computers affect RSA prime encryption?
Yes, large future quantum computers could solve prime factoring much faster. Because of this, internet security standards are moving toward newer methods that do not rely on factoring prime numbers.