Computing with large integers
Victor Shoup · Cambridge University Press eBooks · 2008
In this chapter, we review standard asymptotic notation, introduce the formal computational model that we shall use throughout the rest of the text, and discuss basic algorithms for computing with large integers. Asymptotic notation We review some standard notation for relating the rate of growth of functions. This notation will be useful in discussing the running times of algorithms, and in a number of other contexts as well. Let f and g be real-valued functions. We shall assume that each is defined on the set of non-negative integers, or, alternatively, that each is defined on the set of non-negative reals. Actually, as we are only concerned about the behavior of f(x) and g(x) as x → ∞, we only require that f(x) and g(x) are defined for all sufficiently large x (the phrase “for all sufficiently large x ” means “for some x 0 and all x ≥ x 0 ”). We further assume that g is eventually positive , meaning that g(x) > 0 for all sufficiently large x . Then f = O(g) means that | f(x) | ≤ cg(x) for some positive constant c and all sufficiently large x (read, “ f is big-O of g ”), f = Ω( g ) means that f(x) ≥ cg(x) for some positive constant c and all sufficiently large x (read, “ f is big-Omega of g ”), f = Θ( g ) means that cg(x) ≤ f(x) ≤ dg(x) for some positive constants c and d and all sufficiently large x (read, “ f is big-Theta of g ”), […]