Editing Modular arithmetic (section)

== Computational complexity ==
Since modular arithmetic has such a wide range of applications, 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]], for details see [[linear congruence theorem]]. Algorithms, such as [[Montgomery reduction]], also exist to allow simple arithmetic operations, such as multiplication and [[Modular exponentiation|exponentiation modulo&nbsp;{{math|''m''}}]], to be performed efficiently on large numbers.

Some operations, like finding a [[discrete logarithm]] or a [[Quadratic congruences|quadratic congruence]] appear to be as hard as [[integer factorization]] and thus are a starting point for [[Cryptography|cryptographic algorithms]] and [[encryption]]. These problems might be [[NP-intermediate]].

Solving a system of non-linear modular arithmetic equations is [[NP-complete]].<ref>{{cite book |first1=M. R. |last1=Garey |first2=D. S. |last2=Johnson |title=Computers and Intractability, a Guide to the Theory of NP-Completeness |url=https://archive.org/details/computersintract0000gare |url-access=registration |publisher=W. H. Freeman |year=1979 |isbn=0716710447 }}</ref>