Cryptography Reference
In-Depth Information
particularly important, because it controls whether the running time is exponential
in ln n (if a =1) or subexponential in ln n (if a< 1). The parameter c
R
is less
important for our purposes.
In the running time analyses of integer factoring algorithms and algorithms to
compute discrete logarithms, the following two cases occur frequently ( a =1 / 2 and
a =1 / 3):
L n [1 / 2 ,c ]= O ( e ( c + o (1)) ln n ln ln n ) )= O ( e ( c + o (1)) ln n ln ln n ) )
L n [1 / 3 ,c ]= O ( e ( c + o (1))(ln n ) 1 / 3 (ln ln n ) 2 / 3 )
The second case occurs with the most efficient algorithm to factorize integers
and compute discrete logarithms (see Chapter 7).
6.5
COMPUTATIONAL MODELS
In the theory of computation, the following computational models are usually
considered:
Boolean circuits;
Turing machines;
Random access machines. 6
As mentioned earlier, Church's thesis says that all computational models
itemized here are equivalent, meaning that if a function (problem) is computable
(solvable) in one model, then it is also computable (solvable) in the other models.
It also means that the computational complexities are equal (up to polynomial
transformations). For example, simulating a random access machine by a Turing
machine generally squares the number of steps. Consequently, from a theoretical
point of view, it doesn't really matter which model is used. As mentioned earlier, the
model that is most frequently used in theoretical computer science and complexity
theory is the Turing machine.
A Turing machine is an imaginary computing device that yields a primitive
but sufficiently general computational model. In fact, a Turing machine is more like
a computer program (software) than a computer (hardware) and can be realized
6
A random access machine is similar to a Turing machine. The major distinguishing feature is that
it provides access to arbitrary (i.e., randomly chosen) memory cells. As such, the random access
machine even more closely represents contemporary computer systems.
Search WWH ::




Custom Search