Cómo calcular eficazmente a*b mod N

Question

Estoy tratando de resolver algunos problemas en interviewstreet. Para algunos problemas mencionan As the answers can be very big, output them modulo 1000000007 . ¿Cómo puedo calcular a*b mod N donde N es un número grande como 1000000007.

Pensé en usar

(a mod N) * (b mod N) = (a*b mod N)

pero creo que realizar esto no funcionaría. Ejemplo :

a=4, b=5 and N=10
(4 mod 10) * (5 mod 10) = 20
whereas (4*5 mod 10) = 2

¿Puede alguien orientarme en la dirección correcta?

Answer 1

Puedes hacer el mod cuando quieras, antes de la multiplicación o después.

Por otra parte $4*5\equiv 0\pmod{10}$ no 2.

Por ejemplo $16*12\equiv 192\equiv 2\pmod{10}$ y también

$16*12\equiv (10+6)*(10+2)\equiv 6*2\equiv 12\equiv 2\pmod{10}$

Siempre es aconsejable modificar antes de multiplicar, ya que así los números serán lo más pequeños posible.