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