Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| polynomial-time algorithm | An algorithm with integer inputs a1, a2, . . . , ak is a polynomial-time algorithm if it runs in time polynomial in lg a1, lg a2, . . . , lg ak, that is, polynomial in the lengths of its binary-encoded inputs.
(See page 850)
|
 |
|
|
| divides | d | a (read "d divides a") means that a = kd for some integer k. Every integer divides 0. If a > 0 and d | a, then |d| ≤ |a|.
(See page 850)
|
|
|
|
| multiple | If d | a, then a is a multiple of d.
(See page 850)
|
|
|
|
| divisor | If d | a and d ≥ 0, d is a divisor of a. Note that d | a if and only if -d | a, so that no generality is lost by defining the divisors to be nonnegative, with the understanding that the negative of any divisor os a also divides a. A divisor of an integer a is at least 1 but not greater than |a|.
(See page 850)
|
|
|
|
| trivial divisors | Every integer a is divisible by the trivial divisors 1 and a.
(See page 851)
|
|
|
|
| nontrivial divisors | Nontrivial divisors of a are also called factors of a.
(See page 851)
|
|
|
|
| prime | An integer a > 1 whose only divisors are the trivial divisors 1 and a is said to be a prime number (or, more simply, a prime). Primes have many special properties and play a critical role in number theory.
(See page 851)
|
|
|
|
| composite | An integer a > 1 that is not prime is said to be a composite number (or, more simply, a composite).
(See page 851)
|
|
|
|
| unit | The integer 1 is a unit and is neither prime nor composite. Similarly, the integer 0 and all negative integers are neither prime nor composite.
(See page 851)
|
|
|
|
| quotient | The value q = ⌊a/n⌋ is the quotient of the division.
(See page 851)
|
|
|
|
| remainder | The value r = a mod n is the remainder (or residue) of the division.
(See page 851)
|
|
|
|
| common divisor | If d is a divisor of a and d is also a divisor of b, then d is a common divisor of a and b.
(See page 852)
|
|
|
|
| greatest common divisor | of two integers a and b, not both zero, is the largest of the common divisors of a and b; it is denoted gcd(a,b).
(See page 852)
|
|
|
|
| relatively prime | Two integers a, b are relatively prime if their only common divisor is 1, that is if gcd(a, b) = 1.
(See page 854)
|
|
|
|
| pairwise relatively prime | integers n1, n2, . . . , nk are pairwise relatively prime if, whenever
i ≠ j, we have gcd(ni, nj) = 1.
(See page 854)
|
|
|
|
| kth power | For any integer k > 0, an integer n is a kth power if there exists an integer a such that ak = n.
(See page 855)
|
|
|
|
| nontrivial power | n > 1 is a nontrivial power if it is a kth power for some integer k > 1.
(See page 855)
|
|
|
|
| least common multiple | Define lcm(a1, a2, . . . , an) to be the least common multiple of the n integers a1, a2, . . . , an, that is, the least nonnegative integer that is a multiple of each ai.
(See page 861)
|
|
|
|
| identity | There is an element e ⊆ S, called the identity of the group, such that
e ⊕ a = a ⊕ e = a for all a ⊆ S.
(See page 862)
|
|
|
|
| inverse | For each a ⊆ S, there exists a unique element of b ⊆ S, called the inverse of a, such that a ⊕ b = b ⊕ a = e.
(See page 862)
|
|
|
|
| commutative law | a ⊕ b = b ⊕ a for all a, b ⊆ S.
(See page 862)
|
|
|
|
| abelian group | If a group (S, ⊕) satisfies the commutative law, then it is an abelian group.
(See page 862)
|
|
|
|
| finite group | If a group (S, ⊕) satisfies |S| < ∞, then it is a finite group.
(See page 862)
|
|
|
|
| subgroup | a nonempty closed subset of a finite group
(See page 866)
|
|
|
|
| proper | A subgroup S′ of a group S is a proper subgroup if S′ ≠ S.
(See page 866)
|
|
|
|
| subgroup generated by a | The subgroup generated by a, denoted ⟨a⟩ or (⟨a⟩, ⊕), is defined by ⟨a⟩ = {a(k) : k ≥ 1}. We say that a generates the subgroup ⟨a⟩ or that a is a generator of ⟨a⟩.
(See page 867)
|
|
|
|
| primitive root | If ordn(g) = |Zn*|, then every element in Zn* is a power of g, modulo n, and we say that g is a primitive root or a generator of Zn*.
(See page 877)
|
|
|
|
| nontrivial square root of 1, modulo n | A number x is a nontrivial square root of 1, modulo n, if it satisifies the equation s2 ≡ 1 (mod n) but x is equivalent to neither of the two "trivial" square roots: 1 or -1, modulo n.
(See page 879)
|
|
|
|
| modular exponentiation | A frequently occurring operation in number-theoretic computations is raising one number to a power modulo another number, also know as modular exponentiation.
(See page 879)
|
|
|
|
| digital signature | σ for the message M′ using key SA and the equation σ = SA(M′).
(See page 883)
|
|
|
|
| prime distribution function | π(n) specifies the number of primes that are less than or equal to n.
(See page 888)
|
|
|
|
| base-a pseudoprime | n is a base-a pseudoprime if n is compositie and an-1 ≡ 1 (mod n).
(See page 889)
|
|
|
|
| factor | to decompose into a product of primes.
(See page 896)
|
|
|
|
| quadratic residue | Let p be an odd prime. A number a ⊆ Zp* is a quadratic residue if the equation x2 = a (mod p) has a solution for the unknown x.
(See page 903)
|
2002 McGraw-Hill Higher Education