0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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