From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-22 19:08:14
Great info. Thanks Lucas. I'll read Knuth and see what he says about the
Rabin-Miller probabilistic primality test. 34 * 10^13 gives us all 32 bit
numbers, and perhaps we could add a few more bases for 64 bit compilers.
----- Original Message -----
From: "Lucas Galfaso" <lgalfaso_at_[hidden]>
Sent: Monday, September 22, 2003 5:10 AM
Subject: [boost] Re: Re: Re: Re: Compile time prime numbers, powers and
> "Lucas Galfaso" <lgalfaso_at_[hidden]> wrote in message
> > Ok, under some very special circumstances, it might be useful to do a
> > compile time prime verification.
> > Trying to join to another branch of this same thread, verifying that
> > mod m is not a verification test at all. Composite number with this
> > (with the additional hypothesis that a and m are coprime) are called
> > Carmichael number, viz. 3.11.17, 5.13.17, 5.17.29, 5.29.73, 7.13.19.
> > If you really want a fast algorithm, try implement Rabin-Miller, but a
> > compile time of this algorithm could be really tricky to implement.
> > Lucas/
> Some info that might be useful.
> Given: N < 34 * 10^13.
> If N is a strong pseudoprime (pass the rabin-miller test) to the bases 2,
> 5, 7, 11, 13 and 17 then N is prime.
> The first number which is a strong pseudoprime to these seven bases, but
> a prime, is larger than 34 * 10^13.
> > _______________________________________________
> > Unsubscribe & other changes:
> Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk