My purpose is just for "small" primes up to 128 bits. There are much
faster ways to find larger primes, such as GNFS and ECPP. I have other
programs to find random primes of >1000 digits for cryptographic
purposes using Miller Witness probabilistic tests. Those are never
100% certain, but getting 1 in 10^40 probability in 0.1% of the time
to be 100% certain is good enough for the purpose. I haven't dabbled
in the really huge Mersenne searches because I don't have an
application for those, but they are interesting.
Don
On Dec 18, 11:15 am, Travis Scheponik <tschepo...@gmail.com> wrote:
> Ah thanks for the clarification. As a follow up is this for small primes
> only? If it is for large (> 100 decimal digits), you might want to compare
> this against the general number field sieve (GNFS)
>
>
>
>
>
>
>
> On Tue, Dec 18, 2012 at 11:13 AM, Don <dondod...@gmail.com> wrote:
> > That word is overloaded. I mean they are parallel mathematically, not
> > running on different processors.
> > Don
>
> > On Dec 18, 11:08 am, Travis Scheponik <tschepo...@gmail.com> wrote:
> > > This is where I got the parallel piece from, perhaps I am quoting the
> > wrong
> > > person:
>
> > > "I used 48 parallel sieves, one for each value in the range 0..210
> > > which is not divisible by 2,3,5, or 7"
>
> > > On Tue, Dec 18, 2012 at 10:57 AM, Don <dondod...@gmail.com> wrote:
> > > > No, it does make it faster.
>
> > > > There are 48 sieves each doing 1/210th of the work which one sieve
> > > > would do. Thus it is doing about a quarter as much work.
> > > > It means that I don't have to mark values which are multiples of 2,3,5
> > > > or 7. Those values do not appear in the sieve. A simple sieve spends a
> > > > large portion of its time on those values because they occur with the
> > > > greatest frequency.
> > > > I'm not sure what you mean by N workers. I'm not running it in
> > > > parallel. It would parallelize very nicely, though.
>
> > > > Don
>
> > > > On Dec 18, 10:01 am, Travis Scheponik <tschepo...@gmail.com> wrote:
> > > > > That actually doesn't make it "faster" as you claim. You are just
> > > > > splitting the work out to N workers, which ignores big O notation
> > > > > boundaries. A more appropriate sieve, could be the Euler sieve.
> > > > However,
> > > > > I am not sure what you mean by create a sieve that ignores the first
> > few
> > > > > prime numbers, could you expound on that?
>
> > > > > On Tue, Dec 18, 2012 at 9:55 AM, Don <dondod...@gmail.com> wrote:
> > > > > > He is how I did it:
>
> > > > > > I used 48 parallel sieves, one for each value in the range 0..210
> > > > > > which is not divisible by 2,3,5, or 7. If those numbers are store
> > in
> > > > > > A[48]={1,11,13.17,19,23,...}, then the Nth bit in sieve S
> > represents
> > > > > > the value N*210+A[S]. When a new prime P is encountered, you need
> > to
> > > > > > find the first place in each of the 48 sieves where it will be
> > > > > > encountered. That will be the smallest value V > P^2 where
> > V%210=A[S].
> > > > > > Then to process a sieve you take steps of size 210*P. This is about
> > > > > > four times faster than using a single sieve. It could be extended
> > to
> > > > > > include multiples of 11, but I didn't do that.
>
> > > > > > Don
>
> > > > > > On Dec 7, 4:14 pm, Don <dondod...@gmail.com> wrote:
> > > > > > > I know that the Sieve of Eratosthenes is a fast way to find all
> > prime
> > > > > > > numbers in a given range.
> > > > > > > I noticed that one implementation of a sieve spends a lot of time
> > > > > > > marking multiples of small primes as composite. For example, it
> > takes
> > > > > > > 1000 times as long to mark off all of the multiples of five as it
> > > > > > > takes to mark off the multiples of 5003. In addition, when it is
> > > > > > > marking off the multiples of larger primes, most of them are
> > > > multiples
> > > > > > > of small primes. In fact, if it could skip over multiples of
> > 2,3,5,7,
> > > > > > > and 11, the sieve would be about 5 times faster.
>
> > > > > > > Can someone describe a way to make a sieve faster by not having
> > to
> > > > > > > deal with multiples of the first few prime numbers?
>
> > > > > > > Don
>
> > > > > > --
>
> > > > --
>
> > --
--
