Prime Numbers, RSA and Post-Quantum Cryptography: What Changes in 2026?

RSA is not suddenly broken in 2026. Current quantum computers cannot factor the large RSA moduli used in real systems. The long-term problem is mathematical: a large, fault-tolerant quantum computer could use Shor’s algorithm to attack the factorization problem that protects RSA.

The practical change in 2026 is the move from preparation to deployment. Standardized post-quantum algorithms now exist for shared-key establishment and digital signatures. Software teams, certificate operators, hardware makers, and network designers can test and introduce them instead of waiting for an unfinished standard.

Why RSA begins with two prime numbers

An RSA key starts with two large, randomly chosen prime numbers, usually written as p and q. Their product becomes the RSA modulus:

The modulus n appears in the public key. The primes p and q remain secret. Anyone can multiply the primes when generating a key, but reversing the process is hard when n has thousands of bits and the primes were chosen correctly.

RSA therefore does not rely on prime numbers being rare or mysterious. It relies on an asymmetry between two tasks:

• Multiplying two known large primes is efficient.
• Recovering those primes from their large product is difficult for known classical methods.

A small example shows the structure

Take the primes 61 and 53:

The number 3233 can be public. The factors 61 and 53 provide the private mathematical structure used to derive the RSA private exponent. This tiny example offers no real security, but it shows what an attacker tries to recover.

The values 61 and 53 can be tested with the Prime Number Checker. The checker confirms primality; RSA key generation then adds much stricter requirements for randomness, size, independence, and safe implementation.

What Shor’s algorithm changes

Classical factoring algorithms become harder to run as the RSA modulus grows. This is why RSA key sizes rose over time. Shor’s algorithm changes the type of attack under consideration. On a sufficiently capable quantum computer, it can solve integer factorization in polynomial time.

That does not mean every quantum processor can break RSA. A practical attack on modern RSA would require a large, error-corrected machine that can run a long quantum computation reliably. Present systems do not have that capacity.

Why a larger RSA key is not a permanent quantum fix

Moving from RSA-2048 to RSA-3072 or RSA-4096 can raise the cost of classical attacks. It does not move the system away from factorization. A future quantum attack would still target the same mathematical family.

The quantum issue is therefore not a small key-size error. It is a change in which hard problems remain suitable for public-key cryptography.

RSA encryption and RSA signatures are both exposed

RSA has served two main jobs:

• Key establishment or encryption: protecting a secret that later supports symmetric encryption.
• Digital signatures: proving who signed data and detecting later changes.

A quantum attack on RSA factorization affects both uses because the private key can be reconstructed from the public modulus once its prime factors are recovered.

What changes in 2026

The post-quantum shift did not begin in 2026, and RSA did not receive a universal expiration date. The difference is that the first NIST post-quantum standards are final and available for implementation. Work now centers on protocol support, testing, validation, certificate formats, product upgrades, and migration planning.

2026 is about migration, not a mass RSA shutdown

Existing RSA systems will remain visible for years. Many products depend on certificate chains, hardware security modules, firmware formats, smart cards, document signatures, and long-lived devices that cannot change overnight.

New long-life systems face a different decision. Choosing a quantum-vulnerable public-key method today may create another migration before the system reaches retirement. This makes post-quantum support and algorithm replacement part of present engineering work.

The 2030 and 2035 dates need context

NIST’s transition draft proposes deprecating 112-bit quantum-vulnerable protection after 2030 and disallowing quantum-vulnerable public-key methods after 2035 in the standards covered by that transition plan. These dates are planning targets for affected standards, not proof that a quantum computer will break RSA in a named year. They are also not a single worldwide legal deadline.

Prime numbers do not disappear after RSA

It is easy to describe post-quantum cryptography as a move away from prime numbers. That description is too broad. The real move is away from prime factorization as the security assumption for widely used public-key systems.

Prime numbers still appear in the arithmetic of lattice-based standards. Their role has changed.

The public prime 3329 in ML-KEM

ML-KEM performs polynomial arithmetic with the prime modulus:

This number is public and fixed by the standard. No security benefit comes from hiding it. The prime helps define the finite arithmetic used for polynomial operations and the Number-Theoretic Transform. ML-KEM’s three parameter sets use the same modulus while changing other values that affect dimensions, noise, sizes, security category, and performance.

The public prime 8380417 in ML-DSA

ML-DSA uses another public prime modulus:

Again, the prime is not a secret factor. It supports efficient polynomial arithmetic in the signature scheme. The security claim comes from the difficulty of the lattice problems created by the full construction, not from the difficulty of deciding whether 8380417 is prime.

Both 3329 and 8380417 can be entered into the prime checker. That simple test confirms a mathematical property of the modulus. It does not evaluate the security of ML-KEM or ML-DSA as a whole.

RSA’s two jobs are replaced by different tools

There is no single post-quantum algorithm that replaces every use of RSA. Key establishment and digital signatures have different security goals, so the standardized replacements have different designs.

ML-KEM does not directly encrypt an entire file

A key-encapsulation mechanism produces a shared secret. The communicating parties feed that secret into an approved key-derivation process and use the result with symmetric encryption.

The flow is usually:

1. The receiver creates an ML-KEM encapsulation key and a matching decapsulation key.
2. The sender uses the public encapsulation key to produce a ciphertext and shared secret.
3. The receiver decapsulates the ciphertext to obtain the same shared secret.
4. Both sides derive symmetric keys for encryption and authentication.

FIPS 203 defines ML-KEM-512, ML-KEM-768, and ML-KEM-1024. The standard recommends ML-KEM-768 as the default because it offers a broad security margin at a reasonable performance cost. The names do not represent RSA-style modulus lengths.

ML-DSA and SLH-DSA handle signatures

ML-DSA is the primary lattice-based signature standard. It has three parameter sets: ML-DSA-44, ML-DSA-65, and ML-DSA-87. Their numbers describe matrix dimensions, not a direct bit-security count.

SLH-DSA uses hash-based mathematics. It gives system designers an option that does not rely on the same lattice assumptions as ML-DSA. Its signatures can be much larger, so the choice depends on message flow, storage, verification needs, and the expected number of signatures.

Why hybrid cryptography matters in 2026

Many deployments combine a traditional key exchange with a post-quantum KEM. A common design pairs X25519 with ML-KEM-768. Each component produces secret material, and the protocol combines the results before deriving session keys.

This arrangement reduces reliance on one new algorithm during the transition. If the classical component remains safe against present attackers and the post-quantum component remains safe against future quantum attackers, the combined exchange can preserve protection across both threat models.

Hybrid key exchange does not mean encrypting every message twice. It usually changes the handshake that establishes keys. The application can continue to protect bulk traffic with symmetric encryption.

TLS work became more concrete

RFC 9954, published in 2026, describes a general construction for hybrid key exchange in TLS 1.3. It treats a combined exchange as one negotiated TLS method and joins the component secrets using a defined concatenation approach. The document does not select one mandatory post-quantum algorithm; separate protocol work defines concrete combinations.

This distinction matters. Standardizing ML-KEM solves the algorithm question. Integrating it into TLS, certificate systems, secure email, software signing, hardware, and application libraries solves the deployment question.

Why stored data can make migration urgent

An attacker does not need a quantum computer today to create a future confidentiality problem. Encrypted traffic can be copied now and stored. If the protected information remains valuable when a capable quantum computer arrives, the attacker may try to decrypt the recording later.

This is often called harvest now, decrypt later. It affects medical records, state information, long-term research, identity data, trade secrets, and any archive with a long confidentiality period.

A short-lived web session and a secret that must remain protected for twenty years do not have the same schedule. The useful question is not only “When will a quantum computer exist?” It is also “How long must this data stay unreadable?”

Digital signatures have a different time problem

Recorded ciphertext may become readable later. A signature raises other questions:

• How long must the signature remain verifiable?
• Can firmware or software accept a new signature format?
• Can a device replace its trust anchors?
• Will archived documents need renewed timestamps or re-signing?
• Can certificate chains carry larger public keys and signatures?

These issues explain why a post-quantum transition covers far more than replacing one arithmetic function in a library.

RSA will remain visible during the transition

RSA support will continue in older certificate systems, enterprise software, embedded devices, smart cards, code-signing services, document workflows, and hardware security products. Compatibility requirements often keep an algorithm in use after a newer option becomes available.

That continued presence should not be mistaken for a claim of quantum resistance. A system can be acceptable for a short remaining life while being a poor choice for a new product expected to operate through the 2030s.

Crypto agility becomes part of cryptographic design

Crypto agility means that a system can replace algorithms, parameter sets, key formats, and protocol choices without rebuilding the whole product or interrupting essential operations. NIST updated its crypto-agility guidance in 2026 as post-quantum migration moved into product and infrastructure work.

A crypto-agile design does not choose algorithms automatically or accept any algorithm offered by a peer. It keeps cryptographic choices identifiable, testable, replaceable, and governed by clear policy.

For RSA migration, that can include:

• an inventory of certificates, keys, libraries, protocols, and devices that use RSA;
• versioned key and signature formats;
• room for larger post-quantum keys, ciphertexts, and signatures;
• negotiation rules that prevent unsafe downgrade;
• separate handling for key establishment and signatures;
• a way to update trust anchors and long-lived devices.

The durable design goal is not to predict the last cryptographic algorithm a product will ever need. It is to make the next replacement controlled and measurable.

Common questions about primes, RSA, and post-quantum cryptography

RSA made secret prime factors central to public-key security. The post-quantum standards used in 2026 shift that trust to lattice and hash problems while keeping prime-number arithmetic in supporting roles. The primes remain. What changes is the problem an attacker must solve.