Problem Detail: 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?
Asked By : kdow
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50767
Related
