Comment by blintz | Hacker News Reader

Comment by blintz | Hacker News Reader

Parent Full thread

> too big to do almost any kind of practical computation with

There are definitely possible (though perhaps not immediate) applications for primes of this size. For example, in 2009, researchers were awarded $100k for the discovery of the Mersenne prime 2^43112609-1.

This number, while too large for RSA or ECC, could very well be useful for (R)LWE schemes (used to make post-quantum secure public-key cryptography and partial/fully homomorphic encryption schemes). In particular, it is free to modularly reduce by this prime (take the bottom 43112609 bits), so schemes that rely on doing large matrix multiplication on a modular elements (or even elements in a polynomial ring) would benefit greatly.

Since 43112609 bits is only 5.3MB, this is not at all a ridiculous size - multiplying numbers of 2^26 bits is feasible in well under 1 second in modern hardware, and so making accumulation and modular reduction free is actually valuable.

I gave out the $100k prize you mention (well, I handed the discoverers a non-negotiable giant check for it), but I didn't know about these possibilities. That will be great if they materialize as useful applications!

> In particular, it is free to modularly reduce by this prime (take the bottom 43112609 bits)

Am I missing something? 2^3 - 1 is a Mersenne prime; but taking a number mod 7 is not taking the 3 low bits (there's a relatively low cost trick to take numbers modulo b-1, the same "divide by 9" tricks we can do in base 10... but it's not as easy as looking at the last digit).

The simple trick with modulo 7 is take all the 3 bit sequences: (x & 111), (x & 111000) >> 3, (x & 111000000) >> 6, etc. and add them all together. It means you just have to do bitshift + add instead of all the complexity of division. Same applies to higher powers of 2^n-1 as well.

You can also combine those shift/adds by multiplying by a 1001001001 pattern or perhaps some 1000001000001 patterns.

Sure. That's why I said it was the same as the mod 9 tricks in base 10.

Yeah, sorry, there are extra steps here. If n= 43112609 and you have some 2n-bit number to reduce, you can split it into two n-bit words and simply add the words together, since 1 = 2^n (mod 2^n - 1). You can do this very quickly (ie you can add an arbitrary number of 2n -bit values together with only a small number of adds and shifts as overhead).

Yah-- as mentioned-- just like we can find the residue mod 9 by adding digits up in base 10.

There's notably also the all 1's case to deal with as an exception.

Reply on news.ycombinator.com