4
$\begingroup$

The internet is full of algorithms to calculate the modulo operation of large numbers that have the form $a^e \bmod p$. How about numbers with unknown factorization. More precisely, let's say I have a 4-byte sized modulus prime $p$, and a large number $a$ stored in memory as an array of bytes, that is, $a = [a_{k-1}, a_{k-2},\dots, a_0]$, where $ k \gg 4$.

How to calculate the modulo operation $a \bmod p$ efficiently? Please, cite a reference for your algorithm if it is possible.

$\endgroup$
  • 1
    $\begingroup$ It's the same as multi-precision division, except you don't care about the result of the division, only the remainder. Easily done in O (k). $\endgroup$ – gnasher729 Nov 18 '16 at 11:28
  • $\begingroup$ @gnasher729 Could you provide more details, how can you perform this operation in O(k)? $\endgroup$ – caesar Nov 18 '16 at 11:33
  • $\begingroup$ Write down a 100 digit decimal number. Divide it by 9. What's the remainder? $\endgroup$ – gnasher729 Nov 18 '16 at 19:56
5
$\begingroup$

The map from natural numbers to the ring of remainders is a homomorphism, which is a way to say that it has all sorts of nice properties with respect to operations + and *. In particular, a+b has the same remainder as mod_p(a) + mod_p(b) and a*b, the same as mod_p(a)*mod_p(b).

So, mod_p(a_0 + a_1*2^8 + a_2*2^16 + ...) = mod_p(mod_p(a_0) + mod_p(a_1)*mod_p(2^8) + mod_p(a_2)*mod_p(2^16) + ...).

$\endgroup$
  • $\begingroup$ If I use this approach, then I would need to calculate the modulus of $(2^8)^i$, where $i = 0, 1, ..., k-1$ using exponentiation by squaring. Are you sure there is no other more efficient algorithm for this particular case? $\endgroup$ – caesar Nov 18 '16 at 11:42
  • 4
    $\begingroup$ @caesar, for powers you could use mod_p(2^(8*(i+1)) = mod_p(2^8 * mod_p(2^(8*i)), since you're going to have to compute all k of them anyway. $\endgroup$ – Karolis Juodelė Nov 18 '16 at 11:52
2
$\begingroup$

The modulo operation is one of the basic arithmetic operations. As such, you can use the division algorithm you learned in school (if they still teach it) to calculate $a \bmod p$, which is the remainder in the division of $a$ by $p$. Efficient implementations are also available in libraries like GMP.

$\endgroup$
  • $\begingroup$ I don't think that this is an efficient approach to calculate it. @karolis solution seems more efficient in terms of running time. $\endgroup$ – caesar Nov 18 '16 at 11:42
  • 1
    $\begingroup$ It's definitely an efficient approach, in the sense that it runs in polynomial time. I agree that Karolis' solution might be faster if you're only interested in the remainder. $\endgroup$ – Yuval Filmus Nov 18 '16 at 11:46
  • $\begingroup$ @caesar, I'd suspect that the mod implementation in GMP is better than what I came up with off the top of my head. $\endgroup$ – Karolis Juodelė Nov 18 '16 at 11:58
  • 1
    $\begingroup$ @caesar: A bit of common sense should tell you that every single byte of those k bytes will affect the outcome, so anything faster than O (k) is flat out impossible. $\endgroup$ – gnasher729 Nov 18 '16 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.