|
|
Boost : |
From: Daniel Frey (daniel.frey_at_[hidden])
Date: 2003-09-20 06:07:56
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: +49 (0)241 936737-42, fax: +49 (0)241 936737-99 eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk