chap33.htm

介绍算法的书籍

<pre>--------------------   -------------------------------------</sub></sup></pre><P>
<pre>0  0  1  2  3  4  5     1   1   2   4   7   8   11   13   14</sub></sup></pre><P>
<pre>1  0  2  3  4  5  0     2   2   4   8  14   1    7   11   13</sub></sup></pre><P>
<pre>2  0  3  4  5  0  1     4   4   8   1  13   2   14    7   11</sub></sup></pre><P>
<pre>3  0  4  5  0  1  2     7   7  14  13   4  11    2    1    8</sub></sup></pre><P>
<pre>4  0  5  0  1  2  3     8   8   1   2  11   4   13   14    7</sub></sup></pre><P>
<pre>5  5  0  1  2  3  4    11  11   7  14   2  13    1    8    4</sub></sup></pre><P>
<pre>                       13  13  11   7   1  14    8    4    2</sub></sup></pre><P>
<pre>                       14  14  13  11   8   7    4    2    1</sub></sup></pre><P>
<pre>        (a)                            (b)</sub></sup></pre><P>
<h4><a name="09ae_1b6c">Figure 33.2 Two finite groups. Equivalence classes are denoted by their representative elements. (a) The group (Z<SUB>6</SUB><FONT FACE="Times New Roman" SIZE=2>, +<SUB>6</SUB><FONT FACE="Times New Roman" SIZE=2>). (b) The group </FONT><img src="815_a.gif"><a name="09ae_1b6c"></FONT></sub></sup></h4><P>
<a name="09ae_1b63"><a name="09ae_1b64"><a name="09ae_1b65">Thus, we define addition and multiplication modulo <I>n</I>, denoted +<I><SUB>n</I></SUB> and <SUP>.</SUP><I><SUB>n</I></SUB>, as follows:<P>
<pre>[<I>a</I>]<I><SUB>n</I></SUB> + <I><SUB>n</I></SUB> [<I>b</I>]<I><SUB>n  </I></SUB>=  [<I>a</I> + <I>b</I>]<I><SUB>n </I></SUB>,</sub></sup></pre><P>
<pre>[<I>a</I>]<I>n</I> <img src="../images/dot10.gif"> <I>n</I>[<I>b</I>]<I>n  </I>=  [<I>ab</I>]<I><SUB>n</SUB> .</I></sub></sup></pre><P>
(Subtraction can be similarly defined on <B>Z</B><I><SUB>n</I></SUB> by [<I>a</I>]<I><SUB>n</I> - <I>n</I></SUB> [<I>b</I>]<I><SUB>n</I></SUB> = [<I>a - b</I>]<I><SUB>n</I></SUB>, but division is more complicated, as we shall see.) These facts justify the common and convenient practice of using the least nonnegative element of each equivalence class as its representative when performing computations in <B>Z</B><I><SUB>n</I></SUB>. Addition, subtraction, and multiplication are performed as usual on the representatives, but each result <I>x</I> is replaced by the representative of its class (that is, by <I>x</I> mod <I>n</I>).<P>
<a name="09ae_1b66"><a name="09ae_1b67"><a name="09ae_1b68">Using this definition of addition modulo <I>n</I>, we define the <I><B>additive group modulo n</I></B> as (<B>Z</B><I><SUB>n</I></SUB>, + <I><SUB>n</I></SUB>). This size of the additive group modulo <I>n </I>is <I>|<B>Z</B></I><SUB>n</SUB>| = <I>n</I>. Figure 33.2(a) gives the operation table for the group (<B>Z</B><SUB>6</SUB>, + <SUB>6</SUB>).<P>
<a name="09ae_1b6d">Theorem 33.12<a name="09ae_1b6d"><P>
The system (<B>Z</B><I><SUB>n,</I></SUB> + <I><SUB>n</I></SUB>) is a finite abelian group.<P>
<I><B>Proof     </I></B>Associativity and commutativity of +<I><SUB>n</I></SUB> follow from the associativity and commutativity of +:<P>
<pre>([<I>a</I>]<I><SUB>n</I></SUB> + <I><SUB>n</I></SUB>[<I>b</I>]<I><SUB>n</I></SUB>) +<I><SUB>n</I></SUB>[<I>c</I>]<I><SUB>n  </I></SUB>=  [(<I>a</I> + <I>b</I>) + <I>c</I>]<I><SUB>n</I></sub></sup></pre><P>
<pre>=  [<I>a </I>+ (<I>b </I>+ <I>c</I>)]<I><SUB>n</I></sub></sup></pre><P>
<pre>=  [<I>a</I>]<I><SUB>n</I> </SUB> + <I><SUB>n</I></SUB>([<I>b</I>]<I><SUB>n</I></SUB> + <I><SUB>n</I></SUB>[<I>c</I>]<I><SUB>n</I></SUB>),</sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre>[<I>a</I>]<I><SUB>n</I></SUB> + <I><SUB>n</I></SUB>[<I>b</I>]<I><SUB>n  </I></SUB>=  [<I>a</I> + <I>b</I>]<I><SUB>n</I></sub></sup></pre><P>
<pre>=  [<I>b</I> + <I>a</I>]<I><SUB>n</I></sub></sup></pre><P>
<pre>=  [<I>b</I>]<I><SUB>n</I></SUB> + <I><SUB>n</I></SUB>[<I>a</I>]<I><SUB>n </SUB>.</I></sub></sup></pre><P>
The identity element of (<B>Z</B><I><SUB>n</I></SUB>,+<I><SUB>n</I></SUB>) is 0 (that is, [0]<I><SUB>n</I></SUB>). The (additive) inverse of an element <I>a</I> (that is, [<I>a</I>]<I><SUB>n</I></SUB>) is the element -<I>a</I> (that is, [-<I>a</I>]<I><SUB>n</I></SUB> or [<I>n - a</I>]<I><SUB>n</I></SUB>), since [<I>a</I>]<I><SUB>n</I></SUB> +<I>n</I> [-<I>a</I>]<I><SUB>n</I></SUB>=[<I>a </I>- <I>a</I>]<I><SUB>n</I></SUB>=[0]<I><SUB>n</I></SUB>.      <P>
<a name="09ae_1b69">Using the definition of multiplication modulo <I>n</I>, we define the<I><B> multiplicative group modulo n</I></B> as <img src="816_a.gif">. The elements of this group are the set <img src="816_b.gif"> of elements in <B>Z</B><I><SUB>n</I></SUB> that are relatively prime to <I>n</I>:<P>
<img src="816_c.gif"><P>
To see that <img src="816_d.gif"> is well defined, note that for 0 <img src="../images/lteq12.gif"> <I>a</I> &lt; <I>n</I>, we have <I>a</I> <img src="../images/equiv10.gif"> (<I>a</I>+<I>kn</I>) (mod <I>n</I>) for all integers <I>k</I>. By Exercise 33.2-3, therefore, gcd(<I>a, n</I>) = 1 implies gcd(<I>a</I>+<I>kn, n</I>) = 1 for all integers <I>k</I>. Since [<I>a</I>]<I><SUB>n</I></SUB> = {<I>a</I> + <I>kn </I>: <I>k</I> <img src="../images/memof12.gif"> <B>Z</B>}, the set <img src="816_e.gif"> is well defined. An example of such a group is<P>
<img src="816_f.gif"><P>
where the group operation is multiplication modulo 15. (Here we denote an element [<I>a</I>]<SUB>15</SUB> as <I>a</I>.) Figure 33.2(b) shows the group <img src="816_g.gif">. For example, 8 <FONT FACE="Times New Roman" SIZE=1><img src="../images/dot12.gif"></FONT> 11 <img src="../images/equiv10.gif"> 13 (mod 15), working in <img src="816_h.gif">. The identity for this group is 1.<P>
<a name="09ae_1b6e">Theorem 33.13<a name="09ae_1b6e"><P>
The system <img src="816_i.gif"> is a finite abelian group.<P>
<I><B>Proof     </I></B>Theorem 33.6 implies that <img src="816_j.gif"> is closed. Associativity and commutativity can be proved for <SUP>.</SUP><I><SUB>n</I></SUB> as they were for +<I><SUB>n</I></SUB> in the proof of Theorem 33.12. The identity element is [1]<I><SUB>n</I></SUB>. To show the existence of inverses, let <I>a</I> be an element of <img src="816_k.gif"> and let (<I>d, x, y</I>) be the output of <FONT FACE="Courier New" SIZE=2>EXTENDED</FONT>-<FONT FACE="Courier New" SIZE=2>EUCLID</FONT>(<I>a, n</I>). Then <I>d</I> = 1, since <I>a</I> <img src="../images/memof12.gif"><img src="816_l.gif">, and<P>
<pre><I>ax </I>+ <I>ny </I>= 1</sub></sup></pre><P>
or, equivalently,<P>
<pre><I>ax</I> <img src="../images/equiv10.gif"> 1 (mod <I>n</I>).</sub></sup></pre><P>
Thus, [<I>x</I>]<I><SUB>n</I></SUB> is a multiplicative inverse of [<I>a</I>]<I><SUB>n</I></SUB>, modulo <I>n</I>. The proof that inverses are uniquely defined is deferred until Corollary 33.26.      <P>
When working with the groups (<B>Z</B><I><SUB>n</SUB>,+<SUB>n</I></SUB>) and (<B>Z</B><I><SUB>n</I></SUB>, <FONT FACE="Times New Roman" SIZE=1><img src="../images/dot12.gif"><I><SUB>n</I></FONT></SUB>) in the remainder of this chapter, we follow the convenient practice of denoting equivalence classes by their representative elements and denoting the operations +<I><SUB>n</I></SUB> and <SUP>.</SUP><I><SUB>n</I></SUB> by the usual arithmetic notations + and <FONT FACE="Times New Roman" SIZE=1><img src="../images/dot12.gif"></FONT> (or juxtaposition) respectively. Also, equivalences modulo <I>n</I> may also be interpreted as equations in <B>Z</B><I><SUB>n</I></SUB>. For example, the following two statements are equivalent:<P>
<pre><I>ax  </I><img src="../images/equiv10.gif">  <I>b</I> (mod <I>n</I>) ,</sub></sup></pre><P>
<pre>[<I>a</I>]<I><SUB>n </I></SUB> <I><SUB>n</I></SUB> [<I>x</I>]<I><SUB>n  </I></SUB>=  [<I>b</I>]<I><SUB>n </I></SUB>.</sub></sup></pre><P>
As a further convenience, we sometimes refer to a group (<I>S</I>, <img src="../images/xor14.gif">) merely as <I>S</I> when the operation is understood from context. We may thus refer to the groups (<B>Z</B><I><SUB>n</I></SUB>, + <I><SUB>n</I></SUB>) and <img src="817_a.gif"> as Z<I><SUB>n</I></SUB> and <img src="817_b.gif"> respectively.<P>
The (multiplicative) inverse of an element <I>a</I> is denoted (<I>a<SUP>-1</SUP> mod <SUB>n</I></SUB>). Division in <img src="817_c.gif"><I> </I>is defined by the equation <I>a</I>/<I>b</I> <img src="../images/equiv10.gif"> <I>ab<SUP>-</I>1</SUP> (mod <I>n</I>). For example, in <img src="817_d.gif"> we have that 7<I><SUP>-</I>1</SUP> <img src="../images/equiv10.gif"> 13 (mod 15), since 7 . 13 <img src="../images/equiv10.gif"> 91 <img src="../images/equiv10.gif"> 1 (mod 15), so that 4/7 <img src="../images/equiv10.gif"> 4 . 13 <img src="../images/equiv10.gif"> 7 (mod 15).<P>
<a name="09ae_1b6a"><a name="09ae_1b6b">The size of <img src="817_e.gif"> is denoted <img src="../images/phicap12.gif"> (<I>n</I>). This function, known as <I><B>Euler's phi function</I></B>, satisfies the equation<P>
<img src="817_f.gif"><P>
<h4><a name="09ae_1b6f">(33.20)<a name="09ae_1b6f"></sub></sup></h4><P>
where <I>p</I> runs over all the primes dividing <I>n</I> (including <I>n</I> itself, if <I>n</I> is prime). We shall not prove this formula here. Intuitively, we begin with a list of the <I>n</I> remainders {0, 1, . . . , <I>n</I> - 1 } and then, for each prime <I>p</I> that divides <I>n</I>, cross out every multiple of <I>p</I> in the list. For example, since the prime divisors of 45 are 3 and 5,<P>
<img src="817_g.gif"><P>
If <I>p</I> is prime, then <img src="817_h.gif">, and<P>
<pre><img src="../images/phicap12.gif">(<I>p</I>) = <I>p </I>- 1.</sub></sup></pre><P>
<h4><a name="09ae_1b70">(33.21)<a name="09ae_1b70"></sub></sup></h4><P>
If <I>n</I> is composite, then <img src="../images/phicap12.gif">(<I>n</I>) &lt; <I>n</I> - 1.<P>
<P>







<h2>Subgroups</h2><P>
<a name="09af_1b6c">If (<I>S, </I><img src="../images/xor14.gif">) is a group, <I>S</I>' <img src="../images/rgtubar.gif"> <I>S</I>, and (<I>S</I>', <img src="../images/xor14.gif">) is also a group, then (<I>S</I>', <img src="../images/xor14.gif">) is said to be a <I><B>subgroup</I></B> of (<I>S</I>, <img src="../images/xor14.gif">). For example, the even integers form a subgroup of the integers under the operation of addition. The following theorem provides a useful tool for recognizing subgroups.<P>
<a name="09af_1b6f">Theorem 33.14<a name="09af_1b6f"><P>
If (<I>S</I>, <img src="../images/xor14.gif">) is a finite group and <I>S</I>' is any subset of <I>S</I> such that <I>a</I> <img src="../images/xor14.gif"> <I>b</I> <img src="../images/memof12.gif"> <I>S</I>' for all <I>a, b</I> <img src="../images/memof12.gif"> <I>S</I>', then (<I>S</I>',<img src="../images/xor14.gif">) is a subgroup of (<I>S</I>, <img src="../images/xor14.gif">).<P>
<I><B>Proof     </I></B>The proof is left as Exercise 33.3-2.      <P>
For example, the set {0, 2, 4, 6} forms a subgroup of <B>Z</B><SUB>8</SUB>,since it is closed under the operation + (that is, it is closed under +<SUB>8</SUB>).<P>
The following theorem provides an extremely useful constraint on the size of a subgroup.<P>
<a name="09af_1b70">Theorem 33.15<a name="09af_1b70"><P>
<a name="09af_1b6d">If (<I>S</I>, <img src="../images/xor14.gif">) is a finite group and (<I>S</I>, <img src="../images/xor14.gif">) is a subgroup of (<I>S</I>, <img src="../images/xor14.gif">), then |<I>S</I><I>'</I>| is a divisor of |<I>S|.     </I> <P>
<a name="09af_1b6e"><I>A </I>subgroup<I> S</I>' of a group <I>S</I> is said to be a <I><B>proper</I></B> subgroup if <I>S</I>' <img src="../images/noteq.gif"> <I>S</I>. The following corollary will be used in our analysis of the Miller-Rabin primality test procedure in Section 33.8.<P>
<a name="09af_1b71">Corollary 33.16<a name="09af_1b71"><P>
If <I>S</I>' is a proper subgroup of a finite group <I>S</I>, then |<I>S</I>'<I>| </I><img src="../images/lteq12.gif"> |<I>S|/2.      </I><P>
<P>







<h2>Subgroups generated by an element</h2><P>
Theorem 33.14 provides an interesting way to produce a subgroup of a finite group (<I>S</I>, <img src="../images/xor14.gif">): choose an element <I>a</I> and take all elements that can be generated from <I>a</I> using the group operation. Specifically, define <I>a</I><SUP>(k)</SUP> for <I>k</I> <img src="../images/gteq.gif"> 1 by<P>
<img src="818_a.gif"><P>
For example, if we take <I>a</I> = 2 in the group <I>Z</I><SUB>6</SUB>, the sequence <I>a</I><SUP>(1)</SUP>, <I>a</I><SUP>(2)</SUP>, . . . is<P>
<pre>2, 4, 0, 2, 4, 0, 2, 4, 0,... .</sub></sup></pre><P>
In the group <B>Z</B><I><FONT FACE="Courier New" SIZE=2>n,</I></FONT> we have <I>a</I><SUP>(<I>k</I>)</SUP> = <I>ka</I> mod <I>n</I>, and in the group <img src="818_b.gif">, we have <I>a</I><SUP>(k)</SUP> = <I>a<SUP>k</I></SUP> mod <I>n</I>. The <I><B>subgroup generated by a</I></B>, denoted <img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"> or (<img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"><I>, <img src="../images/xor14.gif">), is defined by</I><P>
<pre><img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"> = {<I>a</I><SUP>(<I>k</I>)</SUP>: <I>k</I> <img src="../images/gteq.gif"> 1}.</sub></sup></pre><P>
<a name="09b0_1b6f">We say that <I>a</I> <I><B>generates</I></B> the subgroup <img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"> or that <I>a</I> is a <I><B>generator</I></B> of <img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif">. Since <I>S</I> is finite, <img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"> is a finite subset of <I>S</I>, possibly including all of <I>S</I>. Since the associativity of <img src="../images/xor14.gif"> implies<P>
<pre><I>a</I><SUP>(<I>i</I>) </SUP><img src="../images/xor14.gif"> <I>a</I><SUP>(<I>j</I>)</SUP> = <I>a</I><SUP>(<I>i</I>+<I>j</I>)</SUP>,</sub></sup></pre><P>
<img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"> is closed and therefore, by Theorem 33.14, <img src="../images/lftwdchv.gif"><I>a</I><img src="../images/wdrtchv.gif"> is a subgroup of <I>S</I>. For example, in <B>Z</B><SUB>6</SUB>,we have<P>
<pre><img src="../images/lftwdchv.gif">0<img src="../images/wdrtchv.gif">  =  {0} ,</sub></sup></pre><P>
<pre><img src="../images/lftwdchv.gif">1<img src="../images/wdrtchv.gif">  =  {0, 1, 2, 3, 4, 5} ,</sub></sup></pre><P>
<pre><img src="../images/lftwdchv.gif">2<img src="../images/wdrtchv.gif">  =  {0, 2, 4} .</sub></sup></pre><P>
Similarly, in <img src="818_c.gif">, we have<P>
<pre><img src="../images/lftwdchv.gif">1<img src="../images/wdrtchv.gif">  =  {1} ,</sub></sup></pre><P>
<pre><img src="../images/lftwdchv.gif">2<img src="../imag