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

71–80 of 89 posts

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

#71

Post by samatman »

jcalvinowens wrote: post #41

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4... If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply! This is…

> If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication.

Zig makes this relatively easy: it has a @mulWithOverflow intrinsic, which returns an overflow bit with the result, and it has integers up to (u|i)65535. So depending on what you're doing, you can either detect overflow and then upcast, or upcast first and then optionally truncate.

It also has saturating multiply as a separate operator *|, or wrapping with *%, for when those are the semantics you want. Otherwise overflow is safety-checked undefined behavior, which will panic in Debug and ReleaseSafe build modes.

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

#72

Post by pclmulqdq »

Jerrrry wrote: post #56
pclmulqdq wrote: post #39

One quick thing to add to this: /dev/urandom does not generate "true" random numbers. TRNGs generate 1 bit out per bit of entropy they collect from the environment, while /dev/urandom will not stop generating random bits when it runs out of entropy. That makes it a CSPRNG that is seeded by a TRNG. For all practical purposes, a CSPRNG seeded by a TRNG is almost as good as a TRNG, but it isn't quite the same. Linux use…

[flagged]

I'm glad you know it, but elsewhere on this site I was just talking to someone who proudly knows very little about programming.

The distinction here is actually very important to a few people (eg the people who run LavaRand at CloudFlare), although it doesn't matter to many.

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

#73

Post by SAI_Peregrinus »

aaplok wrote: post #34

Nice article, and nicely written. > My code from attempt #3 was effectively using base-255, with each byte acting as a single "digit". I think the author means base-256, not base-255.

There are famously 3 hard problems in computer science.

    1) Naming things 
    2) Cach3) Concurr invalidation
    ency 
    4) Off-by-one errors

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

#74

Post by SAI_Peregrinus »

pclmulqdq wrote: post #39

One quick thing to add to this: /dev/urandom does not generate "true" random numbers. TRNGs generate 1 bit out per bit of entropy they collect from the environment, while /dev/urandom will not stop generating random bits when it runs out of entropy. That makes it a CSPRNG that is seeded by a TRNG. For all practical purposes, a CSPRNG seeded by a TRNG is almost as good as a TRNG, but it isn't quite the same. Linux use…

A HWRNG is not necessarily a TRNG. As you say, a TRNG has one bit of entropy per bit of output. There's no way to prove this property is even possible in this physical universe, since it requires perfect unpredictability. Urandom is a CSPRNG seeded by a HWRNG.

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

#75

Post by LegionMammal978 »

samatman wrote: post #71
jcalvinowens wrote: post #41

One line of inline assembler makes the bignum school multiplication trivial: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4... If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. It's a shame Rust doesn't have it either. Hardware support is everywhere: hell, the Cortex M0 doesn't do division, but it has an expanding multiply! This is…

> If I could go back in time and change one thing about the C language, I would add some notion of expanding multiplication. Zig makes this relatively easy: it has a @mulWithOverflow intrinsic, which returns an overflow bit with the result, and it has integers up to (u|i)65535. So depending on what you're doing, you can either detect overflow and then upcast, or upcast first and then optionally truncate. It also has…

At least on x86, there's no real point in detecting truncation before upcasting, since expanding multiplication yields both the high and low halves in a single instruction. At best, you'd be adding branches that the processor can insert just as well itself. (Unless we're talking about things like 128x128-bit multiplication, which would be a different story; it would likely depend on your expected input distribution.)

As for returning an overflow bit, Rust has had this since forever with its overflowing_OP() methods, and C23 has recently added an header with a bunch of ckd_OP() macros that return an overflow bit.

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

#76

Post by djao »

lifthrasiir wrote: post #47
tzs wrote: post #31

Earlier quoted context omitted.

Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases. I've got a Miller-Rabin implementation in Python 3. Testing 2^1024 + 643, which is the first prime greater than 2^1024 with 65 random bases takes about 0.25 seconds on my Mac Studio. This is with no attempts at optimization or at using multiple cores. At that rate tes…

> Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases. Unfortunately this limit depends on the currently unproven conjecture (a subset of the generalized Riemann hypothesis). You have to check all n bases to be unconditionally correct.

Going up to n is surely excessive. You need a version of the Riemann hypothesis to get any sort of logarithmic bound, but a sqrt(n) bound can be achieved using unconditional Polya-Vinogradov type inequalities. (A successful Miller-Rabin test corresponds to a nontrivial value of a Dirichlet character, and Polya-Vinogradov ensures that the least such value cannot exceed sqrt(n) * ln(n), unconditionally without the need for any Riemann hypothesis.)

A reference for this material is "Explicit bounds for primality testing and related problems" by Eric Bach, Math. Comp. 55 (191), July 1990, pp. 355-380.

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

#79

Post by pbsd »

djao wrote: post #76
lifthrasiir wrote: post #47

Earlier quoted context omitted.

> Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases. Unfortunately this limit depends on the currently unproven conjecture (a subset of the generalized Riemann hypothesis). You have to check all n bases to be unconditionally correct.

Going up to n is surely excessive. You need a version of the Riemann hypothesis to get any sort of logarithmic bound, but a sqrt(n) bound can be achieved using unconditional Polya-Vinogradov type inequalities. (A successful Miller-Rabin test corresponds to a nontrivial value of a Dirichlet character, and Polya-Vinogradov ensures that the least such value cannot exceed sqrt(n) * ln(n), unconditionally without the need…

The best asymptotic bound is somewhere between n^(1/8sqrt(e) + eps) and n^(1/6.568sqrt(e) + eps), per [1].

[1] https://doi.org/10.1007/BFb0030409

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

#80

Post by archgoon »

Perepiska wrote: post #70
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…

pow(x,e,mod) was the reason I switched from Perl to Python :)

Even better, they implement negative exponents as well, so you don't have to find a library or cobble together an extended gcd function, since you get in inverses for free.
Post reply on HN