Factorization

As explained in Real-World Cryptography

The mathematical problem of decomposing an integer into its prime factors.

Factorization decomposes an integer into prime factors. In RSA, the public modulus N is built as p × q, while p and q remain secret. Knowing them makes it possible to calculate ϕ(N) and derive the private exponent; without them, this calculation is considered hard. section 6.3.1

RSA uses hidden factorization through a short key-generation chain:

• Generate two large prime numbers, p and q. section 6.3.1
• Publish the modulus N = p × q and public exponent e. section 6.3.1
• Use the secret factors to calculate ϕ(N) and derive private exponent d. section 6.3.1

Why the factors matter

RSA encrypts a message by computing message^e modulo N and decrypts it with message^d modulo N. The public key reveals N, but recovering the private exponent depends on knowing its hidden prime factors. section 6.3.1

Figure 6.12 RSA encryption works by exponentiating a number (our message) with the public exponent e modulo the public modulus N = p × q. RSA decryption works by exponentiating the encrypted number with the private exponent d modulo the public modulus N.

Trace RSA's exponentiation steps while relating the public modulus to the secret factorization behind the private exponent. section 6.3.1

How Real-World Cryptography covers it

How deep it goes

Traces factorization through RSA's modulus, group order, and private-exponent derivation.

Examples

Uses RSA's N = p × q modulus and its public-exponent encryption and private-exponent decryption flow.

What you can do after

Evaluate/understand why keeping RSA's prime factors secret protects private-key derivation.

How it connects

Links factorization to RSA, modular arithmetic, multiplicative groups, and the discrete logarithm problem.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Hacking CryptographyInteger factorization is the problem of decomposing an integer into a product of 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 Real-World Cryptography. The section links point to the parts of the book it draws on.