chap33.htm

介绍算法的书籍

<pre><I>d</I> = gcd(<I>a</I>,<I>b</I>) = <I>ax</I> + <I>by </I>.</sub></sup></pre><P>
<h4><a name="09aa_1b55">(33.18)<a name="09aa_1b55"></sub></sup></h4><P>
Note that<I> x</I> and <I>y</I> may be zero or negative. We shall find these coefficients useful later for the computation of modular multiplicative inverses. The<P>
<pre><I>a   b  </I><img src="../images/hfbrdl12.gif"><B><I>a</I></B>/<B><I>b</I><img src="../images/hfbrdr12.gif">  </B><I>d   x     y</I></sub></sup></pre><P>
<pre><I>-------------------------</I></sub></sup></pre><P>
<pre>99  78   1    3  -11   14</sub></sup></pre><P>
<pre>78  21   3    3   3   -11</sub></sup></pre><P>
<pre>21  15   1    3   -2   3</sub></sup></pre><P>
<pre>15   6   2    3   1    -2</sub></sup></pre><P>
<pre> 6   3   2    3   0    1</sub></sup></pre><P>
<pre> 3   0   --    3   1    0</sub></sup></pre><P>
<h4><a name="09aa_1b56">Figure 33.1 An example of the operation of <FONT FACE="Courier New" SIZE=2>EXTENDED-EUCLID</FONT> on the inputs 99 and 78. Each line shows for one level of the recursion: the values of the inputs a and b, the computed value <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><FONT FACE="Times New Roman" SIZE=2>a/b<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT></FONT></FONT>, and the values d, x, and y returned. The triple (d,x,y) returned becomes the triple (d',x',y') used in the computation at the next higher level of recursion. The call <FONT FACE="Courier New" SIZE=2>EXTENDED-EUCLID</FONT>(99, 78) returns (3, -11, 14), so gcd(99, 78) = 3 and gcd(99, 78) = 3 = 99 <SUP>.</SUP> (-11) + 78 <img src="../images/dot10.gif"> 14.<a name="09aa_1b56"></sub></sup></h4><P>
procedure <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT> takes as input an arbitrary pair of integers and returns a triple of the form (<I>d</I>, <I>x</I>, y) that satisfies equation (33.18).<P>
<pre><a name="09aa_1b54">EXTENDED-EUCLID(<I>a</I>,<I> b</I>)</sub></sup></pre><P>
<pre>1  <B>f</B> <I>b </I>= 0</sub></sup></pre><P>
<pre>2     <B>then return</B> (<I>a</I>, 1, 0)</sub></sup></pre><P>
<pre>3  (<I>d</I>'<I>,</I>x<I>'</I>,<I>y</I>'<I>)</I> <I><img src="../images/arrlt12.gif"></I> EXTENDED-EUCLID(<I>b</I>, <I>a</I> mod <I>b</I>)</sub></sup></pre><P>
<pre>4  (<I>d</I>,<I>x</I>,<I>y</I>) <img src="../images/arrlt12.gif"> (<I>d</I>'<I>,</I>y<I>'</I>,<I>x</I>'<I> - <img src="../images/hfbrdl12.gif"></I>a<I>/</I>b<I><img src="../images/hfbrdr12.gif"> </I>y<I>')</I></sub></sup></pre><P>
<pre>5  <B>return</B> (<I>d</I>,<I>x</I>,<I>y</I>)</sub></sup></pre><P>
Figure 33.1 illustrates the execution of <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT> with the computation of gcd(99,78).<P>
The <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-E<FONT FACE="Courier New" SIZE=2>UCLID </FONT>procedure is a variation of the <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> procedure. Line 1 is equivalent to the test &quot;<I>b</I> = 0&quot; in line 1 of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT>. If <I>b</I> = 0, then <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT> returns not only <I>d </I>= <I>a </I>in line 2, but also the coefficients<I> x </I>= 1 and <I>y</I> = 0, so that <I>a</I> = <I>ax</I> + <I>by.</I> If <I>b </I><img src="../images/noteq.gif"> 0, <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT> first computes (<I>d</I>'<I>, </I>x<I>'</I>, <I>y</I>') such that <I>d</I>' = gcd(<I>b</I>, <I>a</I> mod <I>b</I>) and<P>
<pre><I>d</I>' = <I>bx</I>' + (<I>a</I> mod <I>b</I>)<I>y</I>' .</sub></sup></pre><P>
<h4><a name="09aa_1b57">(33.19)<a name="09aa_1b57"></sub></sup></h4><P>
As for <FONT FACE="Courier New" SIZE=2>EUCLID</FONT>, we have in this case <I>d</I> = <I>gcd(</I>a<I>, </I>b<I>) = </I><I>d</I>'<I> = gcd(</I>b<I>, </I>a<I> mod </I>b<I>)</I>. To obtain <I>x</I> and <I>y</I> such that <I>d</I> = <I>ax</I> + <I>by</I>, we start by rewriting equation (33.19) using the equation <I>d</I> = <I>d</I><I>'</I> and equation (33.2):<P>
<pre><I>d  </I>=  <I>bx</I>'<I> + (</I>a<I> - <img src="../images/hfbrdl12.gif"></I>a<I>/</I>b<I><img src="../images/hfbrdr12.gif"> </I>b<I>)</I>y<I>'</I></sub></sup></pre><P>
<pre>= <I>ay</I>' + <I>b</I>(<I>x</I>' - <img src="../images/hfbrdl12.gif"><I>a</I>/<I>b</I><img src="../images/hfbrdr12.gif"> <I>y</I>') .</sub></sup></pre><P>
Thus, choosing <I>x</I> = <I>y</I>'<I> and y = </I>x<I>'</I> - <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>a</I></FONT>/<I>b</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> <I>y</I><I>'</I> satisfies the equation <I>d</I> = <I>ax</I> + <I>by</I>, proving the correctness of <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT>.<P>
Since the number of recursive calls made in <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> is equal to the number of recursive calls made in <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT>, the running times of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> and <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT> are the same, to within a constant factor. That is, for <I>a</I> &gt; <I>b</I> &gt; 0, the number of recursive calls is <I>O</I>(lg <I>b</I>).<P>
<P>







<h2><a name="09ab_1b58">Exercises<a name="09ab_1b58"></h2><P>
<a name="09ab_1b59">33.2-1<a name="09ab_1b59"><P>
Prove that equations (33.13)--(33.14) imply equation (33.15).<P>
<a name="09ab_1b5a">33.2-2<a name="09ab_1b5a"><P>
Compute the values (<I>d, x, y</I>) that are output by the invocation E<FONT FACE="Courier New" SIZE=2>XTENDED-</FONT><FONT FACE="Courier New" SIZE=2>EUCLID</FONT>(899, 493).<P>
<a name="09ab_1b5b">33.2-3<a name="09ab_1b5b"><P>
Prove that for all integers <I>a, k</I>, and <I>n</I>,<P>
<pre>gcd(<I>a, n</I>) = gcd(<I>a</I> + <I>kn, n</I>).</sub></sup></pre><P>
<a name="09ab_1b5c">33.2-4<a name="09ab_1b5c"><P>
Rewrite <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> in an iterative form that uses only a constant amount of memory (that is, stores only a constant number of integer values).<P>
<a name="09ab_1b5d">33.2-5<a name="09ab_1b5d"><P>
If <I>a</I> &gt; <I>b</I> <img src="../images/gteq.gif"> 0, show that the invocation <FONT FACE="Courier New" SIZE=2>EUCLID</FONT>(<I>a, b</I>) makes at most 1 + log<img src="../images/phicap12.gif"><SUB><I>b</I> recursive calls. Improve this bound to 1 +log</SUB><FONT FACE="Courier New" SIZE=2><SUB><img src="../images/phicap12.gif"></FONT></SUB>(<I>b</I>/gcd(<I>a, b</I>)).<P>
<a name="09ab_1b5e">33.2-6<a name="09ab_1b5e"><P>
What does <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT>(<I>F<SUB>k </I>+ 1</SUB>, <I>F<SUB>k</I></SUB>) return? Prove your answer correct.<P>
<a name="09ab_1b5f">33.2-7<a name="09ab_1b5f"><P>
Verify the output (<I>d, x, y</I>) of <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT>(<I>a, b</I>) by showing that if d <FONT FACE="Times New Roman" SIZE=2>|</FONT> <I>a, d</I> <FONT FACE="Times New Roman" SIZE=2>|</FONT> <I>b</I>, and <I>d</I> = <I>ax </I>+ <I>by</I>, then <I>d</I> = gcd(<I>a, b</I>).<P>
<a name="09ab_1b60">33.2-8<a name="09ab_1b60"><P>
<a name="09ab_1b55">Define the gcd function for more than two arguments by the recursive equation gcd(<I>a</I><SUB>0</SUB>, <I>a</I><SUB>l</SUB>, . . . , <I><SUB>n</I></SUB>) = gcd(<I>a</I><SUB>0</SUB>, gcd(<I>a</I><SUB>1</SUB>, . . . , <I>a</I><SUB>n</SUB>)). Show that gcd  returns the same answer independent of the order in which its arguments are specified. Show how to find <I>x</I><SUB>0</SUB>,<SUB> </SUB><I>x</I><SUB>1</SUB>, . . . . , <I>x<SUB>n</I></SUB> such that gcd(<I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . . , <I>a</I><SUB>n</SUB>) = <I>a</I><SUB>0</SUB><I>x</I><SUB>0 </SUB>+ <I>a</I><SUB>1</SUB><I>x</I><SUB>1</SUB> + <SUP>. . .</SUP><FONT FACE="Times New Roman" SIZE=1> </FONT> + <I>a<SUB>n</SUB>x<SUB>n</I></SUB>. Show that the number of divisions performed by your algorithm is <I>O</I>(<I>n</I> + 1g(max<I><SUB>i</I></SUB>, <I>a<SUB>i</I></SUB>)).<P>
<a name="09ab_1b61">33.2-9<a name="09ab_1b61"><P>
<a name="09ab_1b56"><a name="09ab_1b57">Define lcm(<I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>) to be the <I><B>least common multiple </I></B>of the integers <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>, that is, the least nonnegative integer that is a multiple of each <I>a<SUB>i</I></SUB>. Show how to compute lcm(<I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>) efficiently using the (two-argument) gcd operation as a subroutine.<P>
<a name="09ab_1b62">33.2-10<a name="09ab_1b62"><P>
Prove that <I>n</I><SUB>1</SUB>, <I>n</I><SUB>2</SUB>, <I>n</I><SUB>3</SUB>, and <I>n</I><SUB>4</SUB> are pairwise relatively prime if and only if gcd(<I>n</I><SUB>1</SUB><I>n</I><SUB>2</SUB>, <I>n</I><SUB>3</SUB><I>n</I><SUB>4</SUB>) = gcd(<I>n</I><SUB>1</SUB><I>n</I><SUB>3</SUB>, <I>n</I><SUB>2</SUB><I>n</I><SUB>4</SUB>) = 1. Show more generally that <I>n</I><SUB>1</SUB>, <I>n</I><SUB>2</SUB>, . . . , <I>n<SUB>k</I></SUB> are pairwise relatively prime if and only if a set of <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg <I>k<FONT FACE="Times New Roman" SIZE=2></I><img src="../images/hfbrur14.gif"></FONT><I> </I>pairs of numbers derived from the <I>n<SUB>i</I></SUB> are relatively prime.<P>
<P>


<P>







<h1><a name="09ac_1b5a">33.3 Modular arithmetic<a name="09ac_1b5a"></h1><P>
<a name="09ac_1b58"><a name="09ac_1b59">Informally, we can think of modular arithmetic as arithmetic as usual over the integers, except that if we are working modulo <I>n</I>, then every result <I>x</I> is replaced by the element of {0, 1, . . . , <I>n</I> - 1} that is equivalent to <I>x</I>, modulo <I>n</I> (that is, <I>x</I> is replaced by <I>x</I> mod <I>n</I>). This informal model is sufficient if we stick to the operations of addition, subtraction, and multiplication. A more formal model for modular arithmetic, which we now give, is best described within the framework of group theory.<P>





<h2>Finite groups</h2><P>
<a name="09ad_1b5a"><a name="09ad_1b5b">A <I><B>group</I></B> (<I>S</I>, <img src="../images/xor14.gif">) is a set <I>S</I> together with a binary operation <img src="../images/xor14.gif"> defined on <I>S </I>for which the following properties hold.<P>
<a name="09ad_1b5c">1.     <B>Closure:</B> For all <I>a, b </I><img src="../images/memof12.gif"> <I>S</I>, we have <I>a</I> <img src="../images/xor14.gif"> <I>b</I> <img src="../images/memof12.gif"> <I>S</I>.<P>
<a name="09ad_1b5d">2.     <B>Identity:</B> There is an element <I>e </I><img src="../images/memof12.gif"> S<I> such that </I>e<I> <img src="../images/xor14.gif"> </I>a<I> = </I>a<I> <img src="../images/xor14.gif"> </I>e<I> = </I>a<I> for all </I>a<I> <img src="../images/memof12.gif"> </I>S<I>.</I><P>
<a name="09ad_1b5e">3.     <B>Associativity:</B> For all <I>a, b, c </I><img src="../images/memof12.gif"><I> S</I>, we have (<I>a</I> <img src="../images/xor14.gif"> <I>b</I>) <img src="../images/xor14.gif"> <I>c</I> = <I>a</I> <img src="../images/xor14.gif"> (<I>b</I> <img src="../images/xor14.gif"> c).<P>
<a name="09ad_1b5f">4.     <B>Inverses:</B> For each <I>a</I> <img src="../images/memof12.gif"> <I>S</I>, there exists a unique element <I>b</I> <img src="../images/memof12.gif"> <I>S</I> such that <I>a</I> <img src="../images/xor14.gif"> <I>b</I> = <I>b</I> <img src="../images/xor14.gif"> <I>a</I> = <I>e</I>.<P>
<a name="09ad_1b60"><a name="09ad_1b61"><a name="09ad_1b62">As an example, consider the familiar group (<B>Z</B>, +) of the integers <B>Z</B> under the operation of addition: 0 is the identity, and the inverse of <I>a</I> is -<I>a</I>. If a group (<I>S</I>, <img src="../images/xor14.gif">) satisfies the <I><B>commutative law</I></B> <I>a</I> <img src="../images/xor14.gif"> <I>b</I> = <I>b</I> <img src="../images/xor14.gif"> <I>a</I> for all <I>a, b</I> <img src="../images/memof12.gif"> <I>S</I>, then it is an <I><B>abelian group.</I></B> If a group (<I>S</I>, <img src="../images/xor14.gif">) satisfies <I>|S| &lt; <img src="../images/infin.gif">, then it is a </I><B>finite group.<I></B></I><P>
<P>







<h2>The groups defined by modular addition and multiplication</h2><P>
We can form two finite abelian groups by using addition and multiplication modulo <I>n</I>, where <I>n</I> is a positive integer. These groups are based on the equivalence classes of the integers modulo <I>n</I>, defined in Section 33.1.<P>
To define a group on <B>Z</B><I><SUB>n</I></SUB>, we need to have suitable binary operations, which we obtain by redefining the ordinary operations of addition and multiplication. It is easy to define addition and multiplication operations for <B>Z</B><I><SUB>n</I></SUB>, because the equivalence class of two integers uniquely determines the equivalence class of their sum or product. That is, if <I>a</I> <img src="../images/equiv10.gif"> <I>a</I>' (mod <I>n</I>) and <I>b</I> <img src="../images/equiv10.gif"> <I>b</I>'<SUB> (mod <I>n</I>), then<P>
<pre><I>a</I> + <I>b  </I><img src="../images/equiv10.gif">  <I>a</I>'<SUB> + <I>b</I>'</SUB>  (mod <I>n</I>) ,</sub></sup></pre><P>
<pre><I>ab  </I><img src="../images/equiv10.gif">  <I>a</I>'<SUB><I>b</I>'</SUB>    (mod <I>n</I>) .</sub></sup></pre><P>
<pre>+<B><SUB>6 </SUB></B>0  1  2  3  4  5    <B><img src="../images/dot10.gif"></B><SUB>15   </SUB><B>1   2   4   7   8   11   13   14</B></sub></sup></pre><P>