Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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