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.

Improve this question
$\endgroup$
3
  • 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
    Commented Nov 18, 2016 at 11:28
  • $\begingroup$ @gnasher729 Could you provide more details, how can you perform this operation in O(k)? $\endgroup$
    – caesar
    Commented Nov 18, 2016 at 11:33
  • $\begingroup$ Write down a 100 digit decimal number. Divide it by 9. What's the remainder? $\endgroup$
    – gnasher729
    Commented Nov 18, 2016 at 19:56

2 Answers 2

Reset to default
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) + ...).

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 18, 2016 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ė
    Commented Nov 18, 2016 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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Nov 18, 2016 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
    Commented Nov 18, 2016 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ė
    Commented Nov 18, 2016 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
    Commented Nov 18, 2016 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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