📄 chap33.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 33: NUMBER-THEORETIC ALGORITHMS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap34.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap32.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="099d_1b31">CHAPTER 33: NUMBER-THEORETIC ALGORITHMS<a name="099d_1b31"></h1><P>
Number theory was once viewed as a beautiful but largely useless subject in pure mathematics. Today number-theoretic algorithms are used widely, due in part to the invention of cryptographic schemes based on large prime numbers. The feasibility of these schemes rests on our ability to find large primes easily, while their security rests on our inability to factor the product of large primes. This chapter presents some of the number theory and associated algorithms that underlie such applications.<P>
Section 33.1 introduces basic concepts of number theory, such as divisibility, modular equivalence, and unique factorization. Section 33.2 studies one of the world's oldest algorithms: Euclid's algorithm for computing the greatest common divisor of two integers. Section 33.3 reviews concepts of modular arithmetic. Section 33.4 then studies the set of multiples of a given number <I>a</I>, modulo<I> n</I>, and shows how to find all solutions to the equation <I>ax </I><img src="../images/equiv10.gif"> <I>b</I> (mod <I>n</I>) by using Euclid's algorithm. The Chinese remainder theorem is presented in Section 33.5. Section 33.6 considers powers of a given number <I>a</I>, modulo <I>n</I>, and presents a repeated-squaring algorithm for efficiently computing <I>a<SUP>b</I></SUP> mod <I>n</I>, given <I>a</I>, <I>b</I>, and<I> n</I>. This operation is at the heart of efficient primality testing. Section 33.7 then describes the RSA public-key cryptosystem. Section 33.8 describes a randomized primality test that can be used to find large primes efficiently, an essential task in creating keys for the RSA cryptosystem. Finally, Section 33.9 reviews a simple but effective heuristic for factoring small integers. It is a curious fact that factoring is one problem people may wish to be intractable, since the security of RSA depends on the difficulty of factoring large integers.<P>
Size of inputs and cost of arithmetic computations<P>
<a name="099d_1b2f">Because we shall be working with large integers, we need to adjust how we think about the size of an input and about the cost of elementary arithmetic operations.<P>
<a name="099d_1b30">In this chapter, a "large input<FONT FACE="CG Times (W1)" SIZE=2>"</FONT> typically means an input containing <FONT FACE="CG Times (W1)" SIZE=2>"</FONT>large integers" rather than an input containing "many integers<FONT FACE="CG Times (W1)" SIZE=2>"</FONT> (as for sorting). Thus, we shall measure the size of an input in terms of the <I>number of bits</I> required to represent that input, not just the number of integers in the input. An algorithm with integer inputs <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>k</I></SUB> is a <I><B>polynomial-time algorithm</I> </B>if it runs in time polynomial in lg <I>a</I><SUB>1</SUB>, lg <I>a</I><SUB>2</SUB>, . . . , lg<I> a<SUB>k</I></SUB>, that is, polynomial in the lengths of its binary-encoded inputs.<P>
In most of this book, we have found it convenient to think of the elementary arithmetic operations (multiplications, divisions, or computing remainders) as primitive operations that take one unit of time. By counting the number of such arithmetic operations an algorithm performs, we have a basis for making a reasonable estimate of the algorithm's actual running time on a computer. Elementary operations can be time-consuming, however, when their inputs are large. It thus becomes convenient to measure how many <I><B>bit operations</I> </B>a number-theoretic algorithm requires. In this model, a multiplication of two <img src="../images/beta14.gif">-bit integers by the ordinary method uses <img src="../images/bound.gif">(<img src="../images/beta14.gif"><I></I><SUP>2</SUP>) bit operations. Similarly, the operation of dividing a <img src="../images/beta14.gif"><I></I>-bit integer by a shorter integer, or the operation of taking the remainder of a <img src="../images/beta14.gif"><I></I>-bit integer when divided by a shorter integer, can be performed in time <img src="../images/bound.gif">(<img src="../images/beta14.gif"><I></I><SUP>2</SUP>) by simple algorithms. (See Exercise 33.1-11.) Faster methods are known. For example, a simple divide-and-conquer method for multiplying two <img src="../images/beta14.gif"><I>-</I>bit integers has a running time of <img src="../images/bound.gif">(<img src="../images/beta14.gif"><I></I><SUP>lg<FONT FACE="Times New Roman" SIZE=1>2 3</FONT></SUP>), and the fastest known method has a running time of <img src="../images/bound.gif">(<img src="../images/beta14.gif"><I> </I>lg <img src="../images/beta14.gif"><I> </I>lg lg <img src="../images/beta14.gif"><I></I>). For practical purposes, however, the <img src="../images/bound.gif">(<img src="../images/beta14.gif"><I></I><SUP>2</SUP>) algorithm is often best, and we shall use this bound as a basis for our analyses.<P>
In this chapter, algorithms are generally analyzed in terms of both the number of arithmetic operations and the number of bit operations they require.<P>
<h1><a name="099f_0001">33.1 Elementary number-theoretic notions<a name="099f_0001"></h1><P>
This section provides a brief review of notions from elementary number theory concerning the set<B> Z </B>= {. . . , -2, -1, 0, 1, 2, . . .} of integers and the set<B> N</B> = {0, 1, 2, . . .} of natural numbers.<P>
<h2>Divisibility and divisors</h2><P>
<a name="09a0_1b31"><a name="09a0_1b32">The notion of one integer being divisible by another is a central one in the theory of numbers. The notation<I> d | a</I> (read "<I>d</I> <I><B>divides</I> </B><I>a</I>") means that <I>a</I> = <I>kd</I> for some integer<I> k</I>. Every integer divides 0. If <I>a</I> > 0 and <I>d</I> <I>| a</I>, then <I>|d| <img src="../images/lteq12.gif"> </I>|a|. If <I>d</I> <I>|</I> <I>a</I>, then we also say that <I>a</I> is a <I><B>multiple</I></B> of <I>d</I>. If <I>d</I> does not divide <I>a</I>, we write <img src="802_a.gif">.<P>
<a name="09a0_1b33">If <I>d</I> <I>|</I> <I>a</I> and <I>d</I> <img src="../images/gteq.gif"> 0, we say that <I>d</I> is a <I><B>divisor</I> </B>of<I> a</I>. Note that<I> d</I> <I>|</I> <I>a</I> if and only if -<I>d</I> <I>|</I> <I>a</I>, so that no generality is lost by defining the divisors to be nonnegative, with the understanding that the negative of any divisor of <I>a </I>also divides <I>a.</I> A divisor of an integer <I>a</I> is at least 1 but not greater than <I>|a|</I>. For example, the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24.<P>
<a name="09a0_1b34"><a name="09a0_1b35">Every integer<I> a </I>is divisible by the<I><B> trivial divisors</I></B> 1 and <I>a</I>. Nontrivial divisors of<I> a</I> are also called <I><B>factors</I></B> of <I>a</I>. For example, the factors of 20 are 2, 4, 5, and 10.<P>
<P>
<h2>Prime and composite numbers</h2><P>
<a name="09a1_1b36">An integer <I>a</I> > 1 whose only divisors are the trivial divisors 1 and <I>a</I> is said to be a<I><B> prime </I></B>number (or, more simply, a<I><B> prime</I></B>). Primes have many special properties and play a critical role in number theory. The small primes, in order, are<P>
<pre>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,... .</sub></sup></pre><P>
<a name="09a1_1b37">Exercise 33.1-1 asks you to prove that there are infinitely many primes. An integer <I>a</I> > 1 that is not prime is said to be a<I><B> composite </I></B>number (or, more simply, a <I><B>composite</I></B>). For example, 39 is composite because 3 <I>|</I> 39. The integer 1 is said to be a<B> </B><I><B>unit</I> </B>and is neither prime nor composite. Similarly, the integer 0 and all negative integers are neither prime nor composite.<P>
<P>
<h2>The division theorem, remainders, and modular equivalence</h2><P>
<a name="09a2_1b38"><a name="09a2_1b39">Given an integer <I>n</I>, the integers can be partitioned into those that are multiples of <I>n </I>and those that are not multiples of<I> n</I>. Much number theory is based upon a refinement of this partition obtained by classifying the nonmultiples of<I> n</I> according to their remainders when divided by <I>n. </I>The following theorem is the basis for this refinement. The proof of this theorem will not be given here (see, for example, Niven and Zuckerman [151]).<P>
<a name="09a2_1b42">Theorem 33.1<a name="09a2_1b42"><P>
For any integer <I>a</I> and any positive integer<I> n</I>, there are unique integers <I>q </I>and<I> r</I> such that 0 <img src="../images/lteq12.gif"><I> r</I> < <I>n</I> and <I>a</I> = <I>qn</I> + <I>r. </I> <P>
<a name="09a2_1b3a"><a name="09a2_1b3b"><a name="09a2_1b3c">The value<I> q </I>= <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"><I>a</I>/</FONT><I>n</I><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> is the <I><B>quotient</I></B> of the division. The value<I> r</I> = <I>a</I> mod <I>n</I> is the <I><B>remainder</I> </B>(or <I><B>residue</I></B>) of the division. We have that <I>n</I> <I>| </I><I>a </I>if and only if <I>a</I> mod <I>n</I> = 0. It follows that<P>
<pre><I>a</I> = <img src="../images/hfbrdl12.gif"><I>a</I>/<I>n</I><img src="../images/hfbrdr12.gif"> <I>n</I> + (<I>a</I> mod <I>n</I>)</sub></sup></pre><P>
<h4><a name="09a2_1b43">(33.1)<a name="09a2_1b43"></sub></sup></h4><P>
or<P>
<pre><I>a</I> mod <I>n</I> = <I>a</I> - <img src="../images/hfbrdl12.gif"><I>a</I>/<I>n</I><img src="../images/hfbrdr12.gif"> <I>n</I> .</sub></sup></pre><P>
<h4><a name="09a2_1b44">(33.2)<a name="09a2_1b44"></sub></sup></h4><P>
<a name="09a2_1b3d"><a name="09a2_1b3e">Given a well-defined notion of the remainder of one integer when divided by another, it is convenient to provide special notation to indicate equality of remainders. If (<I>a</I> mod <I>n</I>) = (<I>b</I> mod<I> n</I>), we write<I> a </I><img src="../images/equiv10.gif"> <I>b </I>(mod <I>n</I>) and say that <I>a</I> is <I><B>equivalent</I> </B>to<I> b,</I> modulo<I> n</I>. In other words,<I> a</I> <img src="../images/equiv10.gif"> <I>b </I>(mod<I> n</I>) if <I>a</I> and<I> b</I> have the same remainder when divided by<I> n. </I>Equivalently, <I>a </I><img src="../images/equiv10.gif"> <I>b</I> (mod <I>n</I>) if and only if <I>n</I> <I>|</I> (<I>b</I> - <I>a</I>). We write <I>a</I> <img src="804_a.gif"> <I>b</I> (mod <I>n</I>) if <I>a</I> is not equivalent to <I>b</I>, modulo <I>n</I>. For example, 61 <img src="../images/equiv10.gif"> 6 (mod 11). Also, -13 <img src="../images/equiv10.gif"> 22 <img src="../images/equiv10.gif"> 2 (mod 5).<P>
<a name="09a2_1b3f"><a name="09a2_1b40"><a name="09a2_1b41">The integers can be divided into <I>n </I>equivalence classes according to their remainders modulo <I>n</I>. The <I><B>equivalence class modulo n</I> </B>containing an integer <I>a</I> is<P>
<pre>[<I>a</I>]<I><SUB>n</I></SUB> = {<I>a </I>+ <I>kn </I>: <I>k</I> <img src="../images/memof12.gif"><I><B> Z</I></B>} .</sub></sup></pre><P>
For example, [3]<SUB>7</SUB> = {. . . , -11, -4, 3, 10, 17, . . .}; other denotations for this set are [-4]<SUB>7</SUB> and [10]<SUB>7</SUB>. Writing <I>a </I><I><img src="../images/memof12.gif"> </I>[<I>b</I>]<I><SUB>n</I></SUB> is the same as writing<I> a</I> <img src="../images/equiv10.gif"> <I>b </I>(mod <I>n</I>). The set of all such equivalence classes is<P>
<pre><I><B>Z</I></B><I><SUB>n </I></SUB>= {[<I>a</I>]<I><SUB>n </I></SUB>: 0 <img src="../images/lteq12.gif"> <I>a </I><img src="../images/lteq12.gif"> <I>n </I>- 1}.</sub></sup></pre><P>
<h4><a name="09a2_1b45">(33.3)<a name="09a2_1b45"></sub></sup></h4><P>
One often sees the definition<P>
<pre><I><B>Z</I></B><I><SUB>n</I></SUB> = {0, 1,...,<I> n</I> - 1},</sub></sup></pre><P>
<h4><a name="09a2_1b46">(33.4)<a name="09a2_1b46"></sub></sup></h4><P>
which should be read as equivalent to equation (33.3) with the understanding that 0 represents [0]<I><SUB>n</I></SUB>, 1 represents [1]<I><SUB>n</I></SUB>, and so on; each class is represented by its least nonnegative element. The underlying equivalence classes must be kept in mind, however. For example, a reference to - 1 as a member of <I><B>Z</I></B><I><SUB>n</I></SUB> is a reference to [<I>n</I> - 1]<I><SUB>n</I></SUB>, since - 1 <img src="../images/equiv10.gif"><I> n </I>- 1 (mod <I>n</I>).<P>
<P>
<h2>Common divisors and greatest common divisors</h2><P>
<a name="09a3_1b42"><a name="09a3_1b43">If <I>d</I> is a divisor of <I>a</I> and also a divisor of <I>b</I>, then <I>d </I>is a<I><B> common divisor </I></B>of <I>a</I> and <I>b</I>. For example, the divisors of 30 are 1, 2, 3, 5, 6, 10, 15, and 30, and so the common divisors of 24 and 30 are 1, 2, 3, and 6. Note that 1 is a common divisor of any two integers.<P>
An important property of common divisors is that<P>
<pre><I>d</I> <I>| </I>a<I> and </I>d<I> </I>| <I>b</I> implies <I>d</I> <I>| (</I>a<I> + </I>b<I>) and </I>d<I> </I>| (<I>a</I> - <I>b</I>).</sub></sup></pre><P>
<h4><a name="09a3_1b46">(33.5)<a name="09a3_1b46"></sub></sup></h4><P>
More generally, we have that<P>
<pre><I>d</I> <I>| </I>a<I> and </I>d<I> </I>| <I>b</I> implies<I> d</I> <I>| (</I>ax<I> + </I>by<I>)</I></sub></sup></pre><P>
<h4><a name="09a3_1b47">(33.6)<a name="09a3_1b47"></sub></sup></h4><P>
for any integers <I>x </I>and <I>y</I>. Also, if <I>a</I> <I>| </I><I>b</I>, then either <I>|a| <img src="../images/lteq12.gif"></I> <I>|b|</I> or <I>b</I> = 0, which implies that<P>
<pre><I>a</I> <I>| </I>b<I> and </I>b<I> </I>| <I>a</I> implies <I>a</I> = <img src="../images/plmi12.gif"><I>b</I>.</sub></sup></pre><P>
<h4><a name="09a3_1b48">(33.7)<a name="09a3_1b48"></sub></sup></h4><P>
<a name="09a3_1b44"><a name="09a3_1b45">The <I><B>greatest common divisor</I></B> of two integers <I>a</I> and <I>b</I>, not both zero, is the largest of the common divisors of <I>a</I> and <I>b</I>; it is denoted gcd(<I>a</I>, <I>b</I>). For example, gcd(24, 30) = 6, gcd(5, 7) = 1, and gcd(0, 9) = 9. If <I>a</I> and <I>b</I> are not both 0, then gcd(<I>a, b</I>) is an integer between 1 and min(<I>|a|, </I>|b|). We define gcd(0, 0) to be 0; this definition is necessary to make standard properties of the gcd function (such as equation (33.11) below) universally valid.<P>
The following are elementary properties of the gcd function:<P>
<pre>gcd(<I>a,b</I>) = gcd(<I>b,a</I>),</sub></sup></pre><P>
<h4><a name="09a3_1b49">(33.8)<a name="09a3_1b49"></sub></sup></h4><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -