# Calculating modulus of large non-factored numbers

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.

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

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) + ...).

• 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? – caesar Nov 18 '16 at 11:42
• @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. – Karolis Juodelė Nov 18 '16 at 11:52

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.

• I don't think that this is an efficient approach to calculate it. @karolis solution seems more efficient in terms of running time. – caesar Nov 18 '16 at 11:42
• 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. – Yuval Filmus Nov 18 '16 at 11:46
• @caesar, I'd suspect that the mod implementation in GMP is better than what I came up with off the top of my head. – Karolis Juodelė Nov 18 '16 at 11:58
• @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. – gnasher729 Nov 18 '16 at 19:57