Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How hard can generating 1024-bit primes be?

glitchcomet.com

Post reply on HN
Print view View original

21–30 of 89 posts

Re: How hard can generating 1024-bit primes be?

#21

Post by kadoban »

glitchcomet wrote: post #17
GaggiX wrote: post #14

Earlier quoted context omitted.

>For a given maximum number range, it's trivial to make Miller-Rabin actually deterministic. You just choose bases that have been proven to together exclude all pseudoprimes in the given range. What are the bases for the range of 1024-bit numbers? I couldn't find an answer online.

You can find the bases for N [0]: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...

Oh, woops. I thought the list went way higher, my bad.

I did read that I think if you do up to 2*ln(n)^2 you're always good, but that's not _that_ short of a list. Probably better off just keeping it probabalistic, negating my original post :(

Re: How hard can generating 1024-bit primes be?

#22

Post by dullcrisp »

glitchcomet wrote: post #19
adgjlsfhk1 wrote: post #9

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.

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?

Re: How hard can generating 1024-bit primes be?

#23

Post by mxwsn »

dgacmu wrote: post #18

Related, there are a few cryptocurrencies that used things related to finding large primes as part of their proof of work functions. It turns out that ~8 years ago, a really fast primality test implementation could make you a lot of money. (For some period of time I was the author and maintainer of mining software for riecoin. Why, I have no idea, except that I like prime numbers.) This article omits the number one o…

I'd love to read that story. Please do write it up!

Re: How hard can generating 1024-bit primes be?

#25

Post by glitchcomet »

dullcrisp wrote: post #22
glitchcomet wrote: post #19

Earlier quoted context omitted.

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.

Re: How hard can generating 1024-bit primes be?

#27

Post by Ditiris »

How long did this take you? Curious as I did an undergrad research project on multiplying large integers that basically took two semesters. I implemented Karatsuba, Toom-Cook, the complex FFT, a few NTTs, and Schonhage-Strassen. Primes are basically math magic. A Friendly Introduction to Number Theory by Silverman is an amazing math book for those interested.

FYI the link on your page reads 4025051 instead of 40250519.

Re: How hard can generating 1024-bit primes be?

#28

Post by LegionMammal978 »

Nice article! I've also rolled some of my own bigint code recently (for earlier versions of [0]), and I can recall how frustrating it was to translate high-level descriptions in math papers into actual operations.

I do have a small quibble, though:

> At this point, the BigInt is using base-(2^64-1) or base-18446744073709551615 and it only needs 16 "digits" to represent a number that uses 309 digits in base-10!

If you use the full range of a u64, then your number will be in base 2^64, with each word ranging from 0 to 2^64-1, in the same way that base-10 digits range from 0 to 9.

[0] https://github.com/LegionMammal978/bigfoot-sim

Re: How hard can generating 1024-bit primes be?

#30

Post by dullcrisp »

glitchcomet wrote: post #25
dullcrisp wrote: post #22

Earlier quoted context omitted.

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) t…

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.

Post reply on HN