Hacker News Reader

Comment by adgjlsfhk1 | Hacker News Reader

note that your last optimization of increasing the number by 2 if it fails rather than generating a new random number actually breaks the security slightly. Primes aren't evenly distributed, so doing this biases you towards primes that are directly after large prime gaps.

View on HN

Yeah i read about this in my research. It is a tradeoff between execution speed vs randomness of primes, i choose to go with speed assuming that 16 threads all starting from a random number and competing to find the prime would add enough randomness. If someone preferred more randomness in place of speed it's an easy change to replace the +=2 with a rng() call.

I don’t think the parallelism really helps with this; you’ll still never find the second of two twin primes for instance.

Are there any easy ways to mitigate this though? What about say adding 2^64 at each step instead of 2?

That's an interesting idea. I don't know enough to say if using a large offset would be enough to mitigate the downsides of +=2, i would have to read more about it. In actual use you can go directly to using random candidates for each test as a few extra seconds to generate 2 primes would be worth the benefits. In hindsight my simplistic rng() can also probably be better optimized (batch load random bits and cache) to make it faster as the slowdown primarily comes from repeated filesystem access.

I guess so long as your increment is constant there are primes you’re never going to find. If a prime happens to be 2^64 from another prime you’ll still never see it with my approach.

Probably the most reasonable thing to do would be to use a Mersenne twister or other PRNG to generate a stream of random bytes. Would be plenty fast and should hopefully have no relevant pattern. No reason you should need real randomness from the OS after the initial seed.

IMO you really shouldn't be bottle-necked by random number generation speed. If the kernel calls are what's slowing you down, you could use a strong user space PRNG (e.g. aes based) that is seeded with urandom. The other approach that would be not perfect but a lot better would be to re-randomize the lower 64 or 128 bits each time. That would cut down your rng requirements by a factor of ~10 while keeping much better uniformity since your jumps would be random and much bigger than the gap between primes.

Another option is to do N sequential candidate tests for each fresh random candidate. Where N is something that gets you most of the speed advantage of doing all sequential tests. Maybe like N=16.

Nice write-up!

Reply on news.ycombinator.com