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