# Miller primality test bound

Good morning!

I'm on my way to implement a deterministic (though unproven due to GRH) Miller primality test. On Wikipedia, it is said that it suffices to test all numbers in $[2, \lfloor\times2\ln^2n\rfloor]$

However, there is a problem that I only have bigint arithmetics and can afford neither a true natural logarithm function nor fractional numbers at all.

Ultimately, I only know the amount of bits in the tested number, which is actually $\lfloor\log_2n\rfloor+1$ (am I correct?).

Can anyone advise me what to do with this value to get as close as possible to the upper bound of Miller test, which is $\lfloor2\times\ln^2n\rfloor$, without getting away from the ring of integers?

## 1 Answer

Frankly, the calculation of one logarithm takes so little time compared to doing so many tests that I'm not sure why you'd bother. Probably the best approach in your case is to use a lookup table that tells you how many tests you need -- that way you can use A006945 which allows you to use 10 tests below 3825123056546413051 rather than the 3661 you'd need otherwise.

But if you'd really like to do this directly, $\ln x=\log_2x/\log_2e$ and you can use bignum multiplication with something like $$\lceil2^n\ln2\rceil$$ for sufficiently large n, then shift back by n, then add 1.

• +1 for don't bother. If you do bother, in most applications $\log_2 n$ is one of few possible values, so you can compute the bound "offline" and use a lookup table. – Yuval Filmus May 16 '11 at 21:33