[boost] Re: Re: Re: Re: Compile time prime numbers, powers and roots

From: Lucas Galfaso (lgalfaso_at_[hidden])
Date: 2003-09-22 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 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, 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
>