Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.
Related to modular arithmetic, it is important to know how hard it is to solve a system of congruences. A linear system of congruences can be solved in polynomial time with a form of Gaussian elimination (linear congruence theorem). Algorithms (like the Montgomery reduction) also exist to allow simple arithmetic operations, such as multiplication and exponentiation modulo $n$ (also known as "modular exponentiation"), to be performed efficiently on large numbers. Solving a system of non-linear modular arithmetic equations is NP-complete (see "Computers and Intractability: A Guide to the Theory of NP-completeness" by Michael R. Garey and David S. Johnson, April 1979, W.H.Freeman & Co Ltd).
