Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm more of a programmer than a Mathematician so please bear with me if my question is too trivial.

I am looking up RSA specifically the key generation bit. Using Trial division, I know that it would take roughly (2*(n^0.5))/ln n divisions to find the factors of n.

However I'd like to represent this in a generalized manner i.e. how many divisions would it take to factorize the product of two k-digit primes ?

Any help would be much appreciated

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

I will assume that both primes are approximately $5\times 10^k$. This is in fact the worst-case scenario for trial division. How long trial division will take depends on how exactly you implement it. If you have a table of all primes with up to $5\times 10^k$, then the number of trial divisions will be equal to the number of primes up to $5\times 10^k$, which is $$\pi(5\times 10^k)\approx\frac{5\times 10^k}{\ln 5\times 10^k}=\frac{5\times 10^k}{\ln 5 + k\ln 10}$$ with the approximation following from the prime number theorem. However, if you do not have such a table (which is likely the case if $k$ is large enough for the primes to be used for RSA) then you will need to perform $5\times 10^k$ trial divisions.

share|improve this answer
    
Thank you that helped :) –  Jonny Mar 25 '12 at 12:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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