Mathematics - (Prime Factorization Theorem | Factoring integers)

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}.

Articles Related

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}

Use

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

Computation

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

Using square roots

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

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