
Boost : 
From: Lucas Galfaso (lgalfaso_at_[hidden])
Date: 20030922 04:10:40
"Lucas Galfaso" <lgalfaso_at_[hidden]> wrote in message
news:bkmcta$590$1_at_sea.gmane.org...
> 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
property
> (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 RabinMiller, 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 rabinmiller 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.
Lucas/
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk