# Trial division + Miller-Rabin complexity

I was reading a paper that shows time complexity of Trial division + Miller-rabin test for creating prime number.

T = N(T_rnd + T_td + T_mr)

T_rnd denotes time for making rnd number, T_td denotes time for trial division, and T_mr denotes time for Miller-rabin test.

N denotes the number of r(n-bit random number) that algorithm make until r is a prime number. Which is nln2/2.

I can't calculate how nln2/2 comes out.

Anyone can help me to understand this?

and sry for my bad English.

## 1 Answer

Well, the probability that a random number circa $$N$$ happens to be prime is approximately $$1 / \log_e N$$ (for $$e=2.718281828...$$), this is also known as $$1 / \ln N$$.

Now, if $$n$$ is the number of bits of the number we're searching for, that is, we are generating random numbers circa $$2^n$$, then this probability is approximately $$1 / \ln 2^n = 1 / (n \ln 2)$$. Hence, if we try random $$n$$ bit numbers, we would expect to need to try about the inverse of this number, namely $$n \ln 2$$, before we stumble onto a prime. Now, obviously, we might get lucky early, or we might happen to need to do several times this number before we find a prime - this is just an average.

Now, one thing that you don't mention that they do is, when they select a random number, they set the lsbit. This means that we'll never select an even number (which are hardly ever prime), effectively doubling the probability that a guess happens to give us a prime. This doubling of the probability halves the number of expected trials, hence giving us an expected $$n \ln 2 / 2$$ trials.

Now, one thing about the equation you listed; it includes the term $$N T_{mr}$$. This may be accurate if, independent of whether the trial division finds a factor or not, you perform the Miller-Rabin test anyways. However, it is more likely that, if the trial division shows that the number is composite, you don't perform the Miller-Rabin test, but instead try again with another random number. This implies that you perform fewer Miller-Rabin tests than the number of random numbers you picked (and how much fewer would depend on how thorough you are with your trial division; checking the factors 3, 5, 7 will be less effective (but cheaper) than checking all potential prime factors less than, say, a million).