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

From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-20 13:22:49

To be honest I'm still trying to get my head around Fermat's theorem and how
do implement it.  If you care to take a look into it would be very helpful.
I agree it would be easy to specialise the pseudoprimes, though I'm not sure
how many of them there are in the 32 and 64 bit integer spaces.

Stephen

----- Original Message ----- 
From: "Daniel Frey" <daniel.frey_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, September 20, 2003 7:07 AM
Subject: [boost] Re: Compile time prime numbers, powers and roots

> Stephen Nutt wrote:
> > Since there are around 200 hundred millions prime numbers in the 32 bit
> > unsigned integer domain space, and 4e17 primes in the 64 bit integer
space,
> > I'm trying to find a way to avoid specialisations.  My solution now
works
> > for all 32 bit unsigned numbers, and may even manage number in the teens
of
> > billions, thought I cannot test this with my compiler.
>
> Just an idea, but "s^(p-1)=s mod p" might still be a solution. We can
> use the fact that we have a limited range of numbers to test (32 or 64
> bit currently), so we can choose a set of tests that don't create
> pseudo-primes (or so few of them that we can specialize them away).
>
> Regards, Daniel
>
> -- 
> Daniel Frey
>
> aixigo AG - financial training, research and technology
> Schloß-Rahe-Straße 15, 52072 Aachen, Germany
> fon: [phone], fax: [phone]
> eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost