From: Lucas Galfaso (lgalfaso_at_[hidden])
Date: 2003-09-22 04:10:40
"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 a^m=a
> 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.
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, 3,
5, 7, 11, 13 and 17 then N is prime.
The first number which is a strong pseudoprime to these seven bases, but not
a prime, is larger than 34 * 10^13.
> 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