mersenneforum.org > Math calculation of modulo Mp
 Register FAQ Search Today's Posts Mark Forums Read

 2020-10-02, 20:22 #1 bhelmes     Mar 2016 1011101112 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
2020-10-02, 21:43   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×37×131 Posts

Quote:
 Originally Posted by https://www.mersenne.org/various/math.php#lucas-lehmer ...and it performs the mod 2P-1 step for free.
In very simple terms:
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 p-th 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 2p-1 is luckily this elegant and easy.

 2020-10-03, 07:18 #3 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2×3×5×7×47 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^p-1, then you have a=k*(2^p-1)+b, or other way written, a=k*(2^p)-k+b. When you represent this is binary, on 2p bits, the first most-significant 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 b-k. 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 2020-10-05 at 07:56
 2020-10-03, 08:49 #4 paulunderwood     Sep 2002 Database er0rr 24·3·83 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 p-bits is equivalent to k. If a and b each have no more than p bits then a*b is at most 2*p-1 bits, you can just add the number composed of the top most bits (above p-1 counting from 0) to the number composed of the bottom p bits, to get the result mod Mp. Last fiddled with by paulunderwood on 2020-10-03 at 09:35
 2020-10-03, 17:03 #5 bhelmes     Mar 2016 3×53 Posts Most people know the 9-rule 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 2020-10-03 at 17:04
 2021-02-07, 18:15 #6 bhelmes     Mar 2016 17716 Posts Does someone has a function in gmp for calculating mpz_mod_mp ? Would be nice for me and perhaps also for others. Greetings Bernhard
2021-02-07, 19:45   #7
paulunderwood

Sep 2002
Database er0rr

24·3·83 Posts

Quote:
 Originally Posted by bhelmes Does someone has a function in gmp for calculating mpz_mod_mp ? Would be nice for me and perhaps also for others.
Something along the lines of:

Code:
void mpz_mod_mp(mpz_t r, mpz_t a, mp_bitcnt_t p){
mpz_t x,y;
mpz_init(x);
mpz_init(y);
mpz_fdiv_q_2exp(x, a, p);
mpz_fdiv_r_2exp(y, a, p);
mpz_clear(x);
mpz_clear(y);
}
I have not ran it nor debugged it.

Last fiddled with by paulunderwood on 2021-02-07 at 20:06

 2021-02-07, 21:13 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×37×131 Posts You also need to loop do { your routine } while (mpz_sizeinbase(r,2)>p); If mpz_fdiv_qr_2exp() exists, could be even neater, but optimizing complier will take care of optimizing the two-function call, most surely. So, you can do: Code: void mpz_mod_mp(mpz_t r, mpz_t a, mp_bitcnt_t p) { // assumed that r is initialized and a is expendable do { mpz_fdiv_r_2exp(r, a, p); mpz_fdiv_q_2exp(a, a, p); mpz_add(r, r, a); } while (mpz_sizeinbase(r,2)>p); } The repeat might be needed even if a is fairly small. Example: a = 2p+1-1. After pass #1, we will get exactly r = 2p, pass #2 will turn it into r = 1. Return.
 2021-02-08, 15:27 #9 paulunderwood     Sep 2002 Database er0rr 24×3×83 Posts Nice one Serge. I would also write a function (called mpz_mod_mp_partial) that works at the word boundary instead of being bit-accurate, calling a full reduction at the end of a loop. If p+r == 0 mod 32 and what has to be reduced is k*2^(p+r)+c = k*2^r+c where c < 2^(p+r). But on reflection this extra function does not really help for mod reduction for Mp in particular. See this thread for more details of what I mean. Last fiddled with by paulunderwood on 2021-02-08 at 16:19
 2021-02-09, 01:16 #10 bhelmes     Mar 2016 3×53 Posts Thanks for the function. Last fiddled with by bhelmes on 2021-02-09 at 01:47
 2021-11-03, 17:24 #11 bhelmes     Mar 2016 3×53 Posts I had some problems to use the function, described before, mpz_mod_Mp void mpz_mod_mp (mpz_t r, mpz_t a, mp_bitcnt_t p) { mpz_t res; mpz_init (res); // assumed that r is initialized and a is expendable do { mpz_fdiv_r_2exp (res, a, p); mpz_fdiv_q_2exp (a, a, p); mpz_add (res, res, a); } while (mpz_sizeinbase (res,2) > p); mpz_set (r, res); mpz_clear (res); } calling function is mpz_mod_mp (m_A, m_A, Mp); The result is not the same (I replaced it with a mpz_mod) Where is the logical error ?

 Similar Threads Thread Thread Starter Forum Replies Last Post axn Computer Science & Computational Number Theory 66 2011-09-01 21:55 smslca Math 3 2011-04-18 17:18 T.Rex Math 7 2009-03-13 10:46 Cyclamen Persicum Math 2 2003-12-10 10:52 eepiccolo Math 7 2003-01-08 03:07

All times are UTC. The time now is 22:48.

Mon Jan 24 22:48:27 UTC 2022 up 185 days, 17:17, 1 user, load averages: 0.94, 1.17, 1.38

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔