Thread: modular arithmetic View Single Post
2010-12-07, 22:42   #8
CRGreathouse

Aug 2006

172516 Posts

Quote:
 Originally Posted by science_man_88 I know (a*b) mod x = (a mod x * b mod x)mod x, I've thought about addition and a few others as well looks like it holds for other operations.
Quote:
 Originally Posted by 3.14159 Operations using modular arithmetic; (a mod x + b mod x) mod x = (a + b) mod x. (a mod x * b mod x) mod x = (a * b) mod x.
Yes. But it's sometimes useful to reduce only partially: (a - Ax)(b - Bx) mod x = a * b mod x. This is used in some efficient algorithms where fully reducing at each step would be more costly.