8
$\begingroup$

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?

$\endgroup$
4
  • 7
    $\begingroup$ Read up on the difference between polynomial and pseudo-polynomial time. $\endgroup$
    – Raphael
    Dec 15, 2015 at 14:12
  • 6
    $\begingroup$ I think the key point of confusion is that the time for integer factorization is expressed in terms of the number of digits in the number, not the number itself. Primality is testable in time polynomial in the number of digits; factorization is not known to be solvable in polynomial time in the number of digits. $\endgroup$ Dec 15, 2015 at 19:11
  • $\begingroup$ @PålGD How do you know that $exp(15)∼10^7$ means that the algorithm process a 15-digit number fast? And everyone seems to have calculated the running time differently, is there anyway less arbitrary to tackle that question? $\endgroup$ Dec 16, 2015 at 2:44
  • $\begingroup$ The example here en.wikipedia.org/wiki/Pseudo-polynomial_time is exactly what I was asking. Thanks, @Raphael $\endgroup$ Dec 16, 2015 at 12:49

5 Answers 5

31
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I checked if it grew exponentially with the input number plotting time-number and observing the trend. It seemed logarithmic and it surely wasn't exponential. Also, how can I input a 200-digit number in my computer? $\endgroup$ Dec 15, 2015 at 19:27
  • 2
    $\begingroup$ @Alberto Arbitrary precision integer libraries handle this, and then arithmetic operators are not O(1) but rather O(b) where b is the number of bits in the integer. A 200-digit number will have roughly 650 bits... $\endgroup$ Dec 15, 2015 at 20:27
  • 4
    $\begingroup$ @Alberto don't check how it grows compared to the input number, check how it grows compared to the length of the input number. In this problem, going from 15 digits to 30 digits counts only as twice as much, not as an increase of 1000000000000000 times. $\endgroup$
    – Peteris
    Dec 16, 2015 at 9:20
  • 2
    $\begingroup$ Seeing the comments below the question, I think you can improve this answer for reference purposes by mentioning the term "pseudo-polynomial". $\endgroup$
    – Raphael
    Dec 16, 2015 at 14:38
  • $\begingroup$ This leads me to ask, why do we even do this? I.e. why do we measure input size in bits and not with the numeric value? To me, intuitively, doubling the input to this problem means e.g. going from 128 to 256, not from 128 to $2^{14}$. If we use bits to measure input size, well, of course most algorithms are going to be exponential, since the numeric value increases exponentially with the number of digits (by definition)! It seems like artificially "pumping" how difficult the problem appears. So why do we do this? $\endgroup$
    – Anakhand
    Jan 23, 2021 at 12:42
12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So, why Tom van der Zanden says that it goes as $3.14^n$? And Pål GD, in their comment below my question, $exp(15)∼107$? $\endgroup$ Dec 15, 2015 at 19:33
  • 2
    $\begingroup$ 3.16, not 3.14. One is approximately the square root of ten, the other is approximately pi. There were some cultures that thought pi was equal to the square root of ten because of their proximity. $\endgroup$ Dec 15, 2015 at 21:56
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

When a know fast primality finds that its input is not a prime, it has a proof that there must be a non-trivial factor hidden somewhere, but it doesn't have the slightest clue what that factor would be (unless a primality tester first does a quick check if its input is even. or divisible by 3, 5 or 7).

So the best you can do if you try to find a non-trivial prime factor, is to make a guess "if there was a non-trivial prime factor then it is likely that I would have found it by now". And in that case, you do a primality check, and if the primality checker says "prime" then the number is factored.

(You do that in Pollard-rho. It finds a factor in about $c \cdot \sqrt p$ steps, where p is the smallest prime factor. That means for composite numbers it will find a factor in $c \cdot n^{1/4}$, but if n is prime it will proudly announce after $c \cdot \sqrt n$ steps that n has the factor n. So after more than say $10 \cdot \sqrt n$ steps you add a primality test. )

The worst case for all the easily understandable algorithms are composite numbers n with exactly two prime factors not for away from $\sqrt n$.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ All of what you wrote may be true (except that N-2 should be N-1) but I don't see how this answers the question that was asked. $\endgroup$
    – D.W.
    Dec 16, 2015 at 0:37
  • $\begingroup$ @D.W.: The title of the question notes that primality testing can be done efficiently; I thought it would be helpful to illustrate how a common method of primality testing involves testing whether a given value is a solution to an equation, while factoring would involve finding solutions to that equation. As for N-2 vs N-1, for a prime number N, (X^(N-2))%Y==1 and (X^(N-1))%Y=X, for X in the range 1..N-1 $\endgroup$
    – supercat
    Dec 16, 2015 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.