Mathematics - (Prime Factorization Theorem | Factoring integers)

> Mathematics

1 - About

For every integer N >= 1, there is a unique bag of prime numbers whose product is N.

All the elements in a bag must be prime. If N is itself prime, the bag for N is just {N}.

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.
Carl Friedrich Gauss, Disquisitiones Arithmeticae, 1801
Because both the system’s privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.
Bill Gates, The Road Ahead, 1995

3 - Example

  • 75 is the product of the elements in the bag {3, 5, 5}
  • 126 is the product of the elements in the bag {2, 3, 3, 7}
  • 23 is the product of the elements in the bag {23}
Advertising

4 - Use

4.1 - Secure Sockets Layer

Secure communication with websites uses HTTPS (Secure HTTP)

  • which is based on SSL (Secure Sockets Layer)
  • which is based on the RSA (Rivest-Shamir-Adelman) cryptosystem
  • which depends on the computational difficulty of factoring integers

5 - Computation

5.1 - Naive way

# Python
def factor(N):
    for d in range(2, N-1):
        if N % d == 0: return d

As:

  • If d is a divisor of N then N/d is also a divisor of N.
  • <math>min(d,N/d) <= \sqrt{N}</math>

it suffices to search form 2 to <math>\sqrt{N}</math>

# Python
def factor(N):
    for d in range(2, intsqrt(N):
        if N % d == 0: return d
Advertising

5.2 - Using square roots

5.2.1 - Definition

Find integers a and b such that: <MATH>a^2 − b^2 = N</MATH> Then: <MATH>(a − b)(a + b) = N</MATH> so a − b and a + b are divisors ideally non-trivial

5.2.2 - Computation

Naive approach to find such integers:

  • Choose integer a slightly more than <math>\sqrt{N}</math>
  • Check if <math>\sqrt{a^2 − N}</math> is an integer.
  • If so, let <math>b = \sqrt{a^2 − N}</math>, a − b is now a divisor of N
  • If not, repeat with another value for a

For large N, it takes too long to find a good integer a

mathematics/prime_factorization.txt · Last modified: 2018/02/07 16:47 by gerardnico