[Solved]: Calculating modulus of large non-factored numbers

Problem Detail: 

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.

Asked By : caesar

Answered By : Karolis Juodelė

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66187

 Ask a Question

 Download Related Notes/Documents