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