Editing Euclidean algorithm (section)

=== Multiplicative inverses and the RSA algorithm ===
A [[finite field]] is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as [[commutativity]], [[associativity]] and [[distributivity]]. An example of a finite field is the set of 13 numbers {{math|{{mset|0,&nbsp;1,&nbsp;2,&nbsp;...,&nbsp;12}}}} using [[modular arithmetic]]. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced [[modulo operation|modulo]] {{math|13}}; that is, multiples of {{math|13}} are added or subtracted until the result is brought within the range {{math|0}}–{{math|12}}. For example, the result of {{math|1=5 × 7 = 35 mod 13 = 9}}. Such finite fields can be defined for any prime {{math|''p''}}; using more sophisticated definitions, they can also be defined for any power {{math|''m''}} of a prime {{math|''p''<sup>''m''</sup>}}. Finite fields are often called [[Évariste Galois|Galois]] fields, and are abbreviated as {{math|GF(''p'')}} or {{math|GF(''p''<sup>''m''</sup>}}).

In such a field with {{math|''m''}} numbers, every nonzero element {{math|''a''}} has a unique [[modular multiplicative inverse]], {{math|''a''<sup>−1</sup>}} such that {{math|1=''aa''<sup>−1</sup> = ''a''<sup>−1</sup>''a'' ≡ 1 mod ''m''}}. This inverse can be found by solving the congruence equation {{math|''ax'' ≡ 1 mod ''m''}},<ref>{{Harvnb|Schroeder|2005|pp=107–109}}</ref> or the equivalent linear Diophantine equation<ref>{{Harvnb|Stillwell|1997|pp=186–187}}</ref>
: {{math|1=''ax'' + ''my'' = 1}}.

This equation can be solved by the Euclidean algorithm, as described [[#Linear Diophantine equations|above]]. Finding multiplicative inverses is an essential step in the [[RSA algorithm]], which is widely used in [[electronic commerce]]; specifically, the equation determines the integer used to decrypt the message.<ref>{{Harvnb|Schroeder|2005|p=134}}</ref> Although the RSA algorithm uses [[ring (mathematics)|rings]] rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in [[error-correcting code]]s; for example, it can be used as an alternative to the [[Berlekamp–Massey algorithm]] for decoding [[BCH code|BCH]] and [[Reed–Solomon code]]s, which are based on Galois fields.<ref>{{cite book|title=Error Correction Coding: Mathematical Methods and Algorithms|page=266|first=T. K.|last=Moon|publisher=John Wiley and Sons|year=2005|isbn=0-471-64800-0}}</ref>