Prime Factorization
Definition
For a natural number $N$, finding prime numbers $p_{1} , \cdots , p_{n}$ and natural numbers $r_{1} , \cdots , r_{n}$ satisfying $N = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}}$ is called prime factorization.
Explanation
Historically, prime numbers have always been an object of inquiry, and yet there is still much we do not know.
Elementary tools such as the Fermat test, the Korselt test, and the Miller-Rabin test, as well as analytic approaches including the prime number theorem, are great products of human intellect. Even if not perfect, there has been meaningful progress in relatively efficient methods for finding primes. However, a method for finding a general formula for primes is still unknown.
With a bit of exaggeration, humanity is still stuck at the sieve of Eratosthenes. There is no method that essentially surpasses the sieve of Eratosthenes in accuracy, and even though 2000 years have passed since its introduction, it remains the most reliable way to find primes.
Meanwhile, note that the sieve of Eratosthenes is in fact a method that uses prime factorization. Erasing all multiples of $2$ up to $n = 120$ amounts to nothing other than simultaneously testing $120$ numbers for divisibility by $2$. Watching the animation, this method may look quite efficient, but as $n$ grows it becomes an extremely laborious process. To put it bluntly, using prime factorization to test primality means doing ‘grunt work’. One computes directly and, if no divisor is found, declares the number prime—this is far too crude to call the level of mathematics we desire.
The reason the sieve of Eratosthenes looks useful is that every time it finds a prime it rapidly reduces the ‘candidates’, and while testing up to $n$ it also finds the smaller primes along the way. The output seems abundant relative to the effort put in, but in the end, for a single large natural number $n=N$ that we want to factorize, an honest amount of time is inevitably required.
With the development of computers, multiplication has become a very easy task, but even with that tremendous computing power, prime factorization remains a hard problem. However, this characteristic of the prime factorization problem is at the same time an essential property of cryptography, and by overcoming the weakness of the discrete logarithm problem, it has enriched our lives.
As a method for performing prime factorization quickly, there is the Shor algorithm based on quantum computers, but since the commercialization of quantum computers is a long way off, cryptosystems that exploit the difficulty of the prime factorization problem are expected to remain in active service for the time being.
Code
R
The following is an implementation of the sieve of Eratosthenes in R code. Given a natural number $n$, it determines whether $n$ is prime in the same manner as the sieve of Eratosthenes. If a number equal to $n$ is returned, $n$ is prime; if a number smaller than $n$ is returned, it means the smallest among the divisors of $n$.
eratosthenes<-function(n){
residue<-2:n
while(n %in% residue){
p<-residue[1]
residue<-residue[as.logical(residue%%p)]
}
return(p)
}
eratosthenes(101)
eratosthenes(1517)
For example, since $101$ is prime, $101$ is returned as is, and since $1517=37 \times 41$, $37$ is returned.
Julia
The following is a slightly more efficient implementation in Julia code.
function factorize(n)
factors = []
while n > 1
for k in 2:n
if n % k == 0
n ÷= k
push!(factors, k)
end
end
end
return factors
end
function eratosthenes(n::Integer)
if n == 1 return [[1]] end
if n == 2 return [[1], [2]] end
primes = [2]
factorized = [[1], [2]]
for k ∈ 3:n
m = k
for p ∈ primes
if m % p == 0
m ÷= p
temp = [p; factorized[m]]
push!(factorized, temp)
break
end
end
if length(factorized) != k
push!(primes, k)
push!(factorized, [k])
end
end
return factorized, primes
end
F, P = eratosthenes(20)
F
P