Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

Question

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and references to study it well.

As I have understood it, whether integer factorization can be done in polynomial time is still an open question and, as this article in wikipedia (https://en.wikipedia.org/wiki/Integer_factorization) puts it,

When the numbers are very large, no efficient, non-quantum integer factorization algorithm is known; an effort by several researchers concluded in 2009, factoring a 232-digit number (RSA-768), utilizing hundreds of machines took two years and the researchers estimated that a 1024-bit RSA modulus would take about a thousand times as long.

So, trying to see that for myself, I have written a very naive code in MATLAB checking it with prime numbers up to 15 digits; the reasoning being that if I can check if a number is prime fast, I can easily modify the code to give me the factorization fast.

The time it takes the code to check if a number is prime doesn't grow exponentially with the input.

function[]=prime(n)
tic
f=floor(sqrt(n));
for i=2:f
    if rem(n,i)~=0
        b=0;
    else
        b=1;
        disp(i)
        break
    end
end
if b==0
    disp('prime')
else
    disp('not prime')
end
toc
end

And so I go back to the question in the title. What is wrong with my reasoning?

Answer 1

Since your algorithm is "fast", why did you only try it with a 15-digit number and not with a 232-digit one? There's serious money to be made if you indeed have a "fast" algorithm.

Your algorithm takes time (if we count "div" as taking constant time) proportional to $\sqrt{n}$. A $d$-digit number can be as large as $10^d$, so your algorithm takes time proportional to $\sqrt{10^d} \approx 3.16^d$, i.e. exponential in $d$, the number of digits. That is by no means "fast" and grows very quickly as the numbers get larger.

It is polynomial with respect to the value of $n$, but not with respect to the size of $n$. This behavior is called pseudopolynomiality.

The "fast" prime testing algorithms use much more sophisticated approaches which can not be modified (easily) to also give a factorization. They just report yes/no whether the number is prime. The AKS primality test uses time proportional to $d^6$.

Answer 2

The point is that the complexity of an algorithms is measured in the size of the input. For a number $n$ its size, the length of its representation, is $\log n$ bits.

Answer 3

There can be different algorithms to solve a problem and there is no reason that all of them should follow some particular structure. It is a common mistake to assume that to check if a number is not a prime an algorithm needs to find a non-trivial factor of the number. This is not true. The AKS algorithm does not find any factors when it reports a number is not prime.

AKS is rather complicated so let's look at the simpler Miller–Rabin algorithm (ignoring the fact that it is a probabilistic algorithm). Let $n$ be the number we want to check if it is prime or not. The case of even numbers is easy so we consider the case of odd $n$. Let $n-1 = d2^s$ where $d$ is an odd number.

The idea is:

$n$ is not prime iff for all $0 < a < n$ and $0 \leq r < s$, $$a^d \not\equiv 1 \ (\text{mod } n)$$ and $$a^{2^rd} \not\equiv -1 \ (\text{mod } n)$$

Assume that we checked these conditions, then we know $n$ is not a prime without finding a nontrivial factor of $n$.

Answer 4

If one uses N%D to denote the remainder after dividing N by D, and B^E to denote B raised to the power E, then for any integer N and X with no common factors greater than 1, there will exist some integer Y less than N-1 such that (X^Y)%N equals 1. If N is prime, the smallest such integer will be Y=N-2. For most non-prime values of N, however, most values of X will cause (X^(N-2))%N to yield something else.

If one could identify the Y values for which (X^Y)%N equals 1, that information could be used to factor N fairly easily (and likewise knowing the factors one could compute Y values), but there's no known generally-useful way to find such values without knowing or guessing at the factorization of N.