20201002, 20:22  #1 
Mar 2016
437_{8} Posts 
calculation of modulo Mp
A peaceful and pleasant day for you,
I do not understand how the calculation modulo a Mersenne prime is made: https://en.wikipedia.org/wiki/Mersenne_prime: "Arithmetic modulo a Mersenne number is particularly efficient on a binary computer" Perhaps this is an interesting question also for others. Greetings from the modulo operator Bernhard 
20201002, 21:43  #2  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,831 Posts 
Read https://www.mersenne.org/various/math.php first ?
Quote:
Fact 1. When doing mod operations, (a * b) (mod Mp) = a (mod Mp) * b (mod Mp). Consequence: you never need to keep "the real value"; always keep only the value (mod Mp). This means that it will never be more than p bits long. Fact 2. if we multiply one value by another and both are less than p bits long, you will get a result that is < 2p bits long. Fact 3 (assuming mult or square is already done; there was no question about that part). Mod operation becomes this: cut the bits above pth bit. Slide them down, align with lower part. Add. Only if 1 bit carry sticks out above p bits, cut it again and add 1 to lower part. Done! The DWT actually doesn't need this operation literally. But even if it did, this is how cheap computationally it would have been. Essentially  there is no division. Division by 2^{p}1 is luckily this elegant and easy. 

20201003, 07:18  #3 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·23·97 Posts 
Probably easier for him, you have a number a which you want to reduce (mod m), so you are looking for a number b such as a=b (mod m). From the definition of the modulus, if a=b (mod m), this means that there is a number k, such as a=k*m+b. Now, if m=2^p1, then you have a=k*(2^p1)+b, or other way written, a=k*(2^p)k+b. When you represent this is binary, on 2p bits, the first mostsignificant p bits (MSB) of the representation contain the k value (because multiplying with 2^p just moves k, p bits to the left), and the last p LSB bits (least significant bits) contain the value bk. If you add the two halves together, you get b. That's all**.
 (**Edit: except, sometimes you may get it all 1, by addition, and then the result is zero, or you may need to repeat the procedure once, but those "trifles" won't be discussed here.) Edit 2, as I have some more time, and there is no reply yet, say you want to reduce 107 (mod 31), now 107 is 3*32+11, i.e. 3*2^5+11, therefore when you represent it in binary on 10 bits (5+5) you have 00011 01011. The MSB contains 3, and the LSB contain 11 (decimal, sorry for the confusion, I will "go advanced" now to change the font for the binary numbers here, and color all of them nicely). This is 3*32+11=3*(31+1)+11=3*31+3+11. The 3*31 part won't matter for the modulus. So, all you have to do, is to add the two halves to get 11+3=14. Which is the right result of 107 (mod 31). Last fiddled with by LaurV on 20201005 at 07:56 
20201003, 08:49  #4 
Sep 2002
Database er0rr
11×317 Posts 
2^p  1 == 0 mod Mp
2^p == 1 mod Mp k*2^p == k mod Mp That is k shifted to the left pbits is equivalent to k. If a and b each have no more than p bits then a*b is at most 2*p1 bits, you can just add the number composed of the top most bits (above p1 counting from 0) to the number composed of the bottom p bits, to get the result mod Mp. Last fiddled with by paulunderwood on 20201003 at 09:35 
20201003, 17:03  #5 
Mar 2016
7·41 Posts 
Most people know the 9rule in the decimalsystem
which based on the fact that 10 = 1 mod 9 For Mersenne numbers it is the same reflection that 2^p = 1 mod 2^p 1 Thanks for all replies, now we know one advantage from the Mersenne numbers. Last fiddled with by bhelmes on 20201003 at 17:04 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorial modulo a prime  axn  Computer Science & Computational Number Theory  66  20110901 21:55 
modulo operation for polynomials?  smslca  Math  3  20110418 17:18 
Order of 3 modulo a Mersenne prime  T.Rex  Math  7  20090313 10:46 
N! modulo for large N  Cyclamen Persicum  Math  2  20031210 10:52 
The modulo operation, how is it computed?  eepiccolo  Math  7  20030108 03:07 