• | the set of nonnegative integers 0, 1, 2, 3, . . . |
•+ | the set of positive integers 1, 2, 3, . . . |
• | the set of integers . . . , −2, −1, 0, 1, 2, 3, . . . |
•n | the residue class ring modulo n over the integers (Chapter 5) |
•×n | reduced residue system modulo n |
•pn | finite field with pn elements |
ā | the residue class a + n• in •n |
a ≍ b | a approximately equal to b |
a | a less than and approximately equal to b |
a ← b | assignment: the variable a is given the value b |
|a| | absolute value of a |
a ∣ b | a divides b without remainder |
a ∤ b | a does not divide b |
a ≡ b mod n | a is congruent to b modulo n, that is, n | (a − b) |
a | a is not congruent to b modulo n, that is, n ∤ (a − b) |
gcd(a, b) | greatest common divisor of a and b (Section 10.1) |
lcm(a, b) | least common multiple of a and b (Section 10.1) |
Euler phi function (Section 10.2) | |
O( ) | "Big-Oh." For two real-valued functions f and g with g(x) ≥ 0 one writes f = O(g) and says "f is big-Oh of g" if there exists a constant C such that f(x) ≤ Cg(x) for all x sufficiently large. |
(a/b) | Jacobi symbol (Section 10.4.1) |
greatest integer less than or equal to x | |
⌈x⌉ | least integer greater than or equal to x |
P | the set of computational problems that can be solved in polynomial time |
NP | the set of computational problems that can be solved nondeterministically in polynomial time |
logbx | logarithm of x to the base b |
B | B = 216, the base for the representation of objects of type |
MAXb | maximal number of digits for a |
MAX2 | maximal number of digits for a |
Nmax | largest natural number that can be represented by a |
3.145.55.198