modular arithmetic

• a+b mod n

running time: O(|n|)

 

• a*b mod n

running time: O(|n|2)

 

• (+,*) field mod p

associative - commutative - distributive - inverses