2009/4/22 Robert Gerbicz <robert.gerb...@gmail.com>:
>
>>
>> Do you have a canonical reference on the Strong Lehmer test. As a
>> number theorist, I should have heard of it, but to my embarrassment, I
>> have not! {blush}
>>
> Look: http://mersennewiki.org/index.php/Pocklington%27s_Theorem
> in our case f=p.Ah, so this is just a primality test. I have certainly heard of the Pocklington-Lehmer test, as a student of mine implemented it in another project I work on. > It doesn't mention, but in my number theory book it's > called strong Lehmer test. OK. Is that Pomerance's book Primes: A computational perspective? > What I've forgotten that to take a final gcd in > the code, however up to p=10000 and for all r<p there is no counterexample, > but I don't like unproven items, so modified the code at google group. Great. We always require a proof in MPIR. > For the weaker Lehmer test, see > http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_test That's interesting. I've never seen it called the Lucas-Lehmer test. I always think of that as an algorithm for testing primality of Mersenne numbers. > > In fact, what I've used from old gmp versions is also in mpir-1.1.0, so that > should be no problem. Great. > The newer version of gmp is using a fast checking if a number is a power of > two or not for negative inputs. But I'm just shifting in this case the > exponent to get an odd number. OK. > > The gcd function for unsigned int type numbers is not critical, but I > replaced my own gcd, because that's faster than Lehmer's binary gcd. > OK. I won't bother too much with this then, as yours works. If it is not critical it is not worth optimising for this application. I'll try to read your code through thoroughly in the next few days. Things are incredibly busy for me all the time at the moment, but it looks like Jason has already given your code a once over. It sounds like a really impressive improvement, so I'm looking forward to getting it into the code base. I've opened a ticket on our trac server for this: http://trac.mpir.org/mpir_trac/ It is now ticket number 13^2. Bill. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
