4 <title>Affine ciphers
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
46 <textarea id=
"source">
50 ## Explanation of extended Euclid's algorithm from [Programming with finite fields](http://jeremykun.com/
2014/
03/
13/programming-with-finite-fields/)
52 **Definition:** An element _d_ is called a greatest common divisor (gcd) of _a, b_ if it divides both _a_ and _b_, and for every other _z_ dividing both _a_ and _b_, _z_ divides _d_.
54 **Theorem:** For any two integers _a, b_ there exist unique integers _x, y_ such that _ax_ + _by_ = gcd(_a, b_).
56 We could beat around the bush and try to prove these things in various ways, but when it comes down to it there’s one algorithm of central importance that both computes the gcd and produces the needed linear combination _x, y_. The algorithm is called the Euclidean algorithm. Here is a simple version that just gives the gcd.
60 if abs(a)
< abs(b):
70 This works by the simple observation that gcd(_a_, _aq_ + _r_) = gcd(_a_, _r_) (this is an easy exercise to prove directly). So the Euclidean algorithm just keeps applying this rule over and over again: take the remainder when dividing the bigger argument by the smaller argument until the remainder becomes zero. Then gcd(_x_,
0) =
0 because everything divides zero.
72 Now the so-called ‘extended’ Euclidean algorithm just keeps track of some additional data as it goes (the partial quotients and remainders). Here’s the algorithm.
75 def extendedEuclideanAlgorithm(a, b):
77 (x,y,d) = extendedEuclideanAlgorithm(b, a)
83 x1, x2, y1, y2 =
0,
1,
1,
0
88 a, b, x2, x1, y2, y1 = b, r, x1, x, y1, y
93 Indeed, the reader who hasn’t seen this stuff before is encouraged to trace out a run for the numbers
4864,
3458. Their gcd is
38 and the two integers are
32 and -
45, respectively.
95 How does this help us compute inverses? Well, if we want to find the inverse of _a_ modulo _p_, we know that their gcd is
1. So compute the _x, y_ such that _ax_ + _py_ =
1, and then reduce both sides mod _p_. You get _ax_ +
0 =
1 _mod p_, which means that _x mod p_ is the inverse of _a_. So once we have the extended Euclidean algorithm our inverse function is trivial to write!
99 x,y,d = extendedEuclideanAlgorithm(self.n, self.p)
100 return IntegerModP(x)
103 And indeed it works as expected:
106 >>> mod23 = IntegersModP(
23)
107 >>> mod23(
7).inverse()
109 >>> mod23(
7).inverse() * mod23(
7)
115 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
118 <script type=
"text/javascript"
119 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
121 <script type=
"text/javascript">
122 var slideshow = remark.create({ ratio:
"16:9" });
127 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
130 MathJax.Hub.Queue(function() {
131 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
132 return(elem.SourceElement());
133 }).parent().addClass('has-jax');
135 MathJax.Hub.Configured();