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

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.

Stephen

----- Original Message ----- 
From: "Lucas Galfaso" <lgalfaso_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, September 22, 2003 5:10 AM
Subject: [boost] Re: Re: Re: Re: Compile time prime numbers, powers and
roots

>
> "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
> >
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost