Re:All Mersenne prime exponents below 100m tested at least once
by schoen on Friday December 04, 2020 @07:20PM
(#25310210)
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!
Re:All Mersenne prime exponents below 100m tested at least once
by mlyle on Friday December 04, 2020 @05:39PM
(#25309252)
> 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).
Re:All Mersenne prime exponents below 100m tested at least once
by linknoid on Friday December 04, 2020 @06:01PM
(#25309480)
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.
Re:All Mersenne prime exponents below 100m tested at least once
by SamReidHughes on Friday December 04, 2020 @06:23PM
(#25309657)
You can also combine those shift/adds by multiplying by a 1001001001 pattern or perhaps some 1000001000001 patterns.
Re:All Mersenne prime exponents below 100m tested at least once
by mlyle on Friday December 04, 2020 @07:54PM
(#25310481)
Sure. That's why I said it was the same as the mod 9 tricks in base 10.
Re:All Mersenne prime exponents below 100m tested at least once
by blintz on Friday December 04, 2020 @09:46PM
(#25311203)
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).
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.