Prime numbers and encryption: why 36118 = 2 × 18,059 matters

Number science. 6-minute read. Updated 2026-10-10.

A prime number has exactly two divisors: 1 and itself. Every whole number above 1 can be written as a product of primes in exactly one way. That simple fact, called the fundamental theorem of arithmetic, sits underneath much of the internet's security.

A small example

36118 factors as 2 × 18,059, and 18,059 is prime. A number with exactly two prime factors is called a semiprime. Finding those factors is quick here because one of them is 2. Now imagine both factors were primes hundreds of digits long.

The asymmetry

Multiplying two large primes takes a computer a fraction of a second. Recovering them from the product, with no other information, is believed to take classical computers an impractically long time once the numbers are large enough. RSA encryption, introduced in 1977, is built on that gap: the public key contains the product, and only the holder of the private key knows the factors.

How big is big enough?

RSA keys of 2048 bits, numbers with about 617 decimal digits, are a common baseline today. Many systems now prefer elliptic-curve cryptography, which offers similar security with shorter keys. Researchers are also standardising post-quantum algorithms, because a large enough quantum computer could factor semiprimes efficiently.

Primes are everywhere else too

• Hash tables often use prime sizes to spread data evenly.
• Cicadas in parts of North America emerge in 13- and 17-year cycles.
• Primes thin out slowly: among numbers near 36,000, roughly one in ten is prime.

The video below shows a beautiful pattern that appears when primes are plotted in polar coordinates. To factor your own number, use the number decoder.

Keep reading

• Binary, hex and other bases: one number, many spellings6 min