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)ticf=floor(sqrt(n));for i=2:f    if rem(n,i)~=0        b=0;    else        b=1;        disp(i)        break    endendif b==0    disp('prime')else    disp('not prime')endtocendAnd so I go back to the question in the title. What is wrong with my reasoning?
Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?
algorithms;complexity theory;time complexity;factoring
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$.