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.
----- Original Message -----
From: "Daniel Frey" <daniel.frey_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
> > I'm trying to find a way to avoid specialisations. My solution now
> > for all 32 bit unsigned numbers, and may even manage number in the teens
> > 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: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
> eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de
> 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