Factorization

As explained in Hacking Cryptography

Integer factorization is the problem of decomposing an integer into a product of prime factors.

Integer factorization decomposes an integer into prime factors. Public-key cryptography uses the asymmetry that multiplying large primes is easy, while recovering those primes from their product is computationally expensive on classical computers. section 8.3 section 8.3.2

From a small product to RSA-sized integers

Factoring 764,512 can begin with trial division. If n = p × q uses two 512-bit primes, finding p and q requires trying many possibilities; this one-way behavior supplies RSA's trapdoor function. Classical methods such as Fermat's differences of squares and Pollard's methods improve on naive trial division but remain infeasible for examples involving 2,048-bit primes. section 8.3.2 section 8.3.2

RSA makes the factorization relationship operational: the public key contains n and e, while the private key contains d. Encryption computes c = m^e mod n, and decryption computes m = c^d mod n. Recovering the private relationship from public information is tied to factoring n. section 8.3.2 section 8.3.2

Security consequences follow from both the mathematical problem and its implementation:

• Use sufficiently large, independently generated primes; weak randomness or hardware faults caused 0.3%–0.5% of internet RSA keys to share primes, enabling rapid discovery with batch GCD. section 8.5
• Avoid textbook RSA because deterministic encryption gives identical plaintexts identical ciphertexts; probabilistic padding adds randomness. section 8.5
• Avoid small private exponents; fixed small public exponents commonly help guarantee sufficiently large private exponents. section 8.5
• Account for quantum risk: Shor's algorithm efficiently solves integer factorization in theory, although current demonstrations and scaling remain far below cryptographic key sizes. section 8.3 section 8.3.2

Figure 8.13 The penultimate page of Pietro Antonio Cataldo’s 1603 book Trattato de’ numeri perfetti, showing prime factors for numbers from 625 to 743 (a prime number)

A historical prime-factor table makes the basic decomposition task concrete before extending it to cryptographic-size integers. section 8.3.2

How Hacking Cryptography covers it

How deep it goes

Defines decomposition, illustrates trial division and classical methods, and stops short of detailed factoring algorithms or post-quantum replacements.

Examples

Uses 764,512, products of large primes, historical factor tables, RSA equations, batch GCD, and quantum factoring demonstrations.

What it assumes

Assumes basic prime-number and modular-arithmetic familiarity while introducing factorization's cryptographic role through concrete examples.

What you can do after

Evaluate RSA's factorization assumption and identify weak randomness, deterministic encryption, and short-private-exponent risks.

How it connects

Connects integer factorization to RSA, public-key cryptography, prime numbers, trapdoor functions, quantum computing, and Shor's algorithm.

liveBookmanning.com

Read Hacking Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Real-World CryptographyThe mathematical problem of decomposing an integer into its prime factors.
• 

  liveBookmanning.com
  Software Security for DevelopersInteger factoring is the decomposition of an integer into a product of prime numbers.

Compare how 3 books explain factorization →

Related concepts

• Shor's algorithmaddressed by · Shor's algorithm is a quantum algorithm that efficiently factors integers and solves discrete logarithms using quantum period finding.
• RSAused by · RSA is a public-key cryptosystem based on the computational difficulty of factoring large composite integers and supporting encryption and digital signatures.
• Markov propertyconfigured by · The Markov property is the condition that, given the current state, the distribution of future states is independent of the process’s earlier history.
• public key cryptographyused by · Public-key cryptography is asymmetric cryptography that uses mathematically related public and private keys for encryption, decryption, signing, and verification.
• conditional probabilityuses · Conditional probability is the probability of an event or variable value given that specified information, an event, or another variable’s value is known.

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.