40 1. Classical Computation
Euclid’s algorithm for gcd(a, b) has complexity
O(n3),
but there is also
a so-called “binary” gcd algorithm (see [43, vol. 2, Sec. 4.5.2]) of complexity
O(n2).
It does not solve the equation xa + yb = gcd(a, b), though.
We will also use modular arithmetic. It is clear that the addition of
(mod q)-residues is done by a circuit of size O(n), whereas modular multi-
plication can be reduced to integer multiplication and division; therefore
it is performed by a circuit of size
O(n2)
(by the standard technique).
To invert a residue a
(Z/qZ)∗,
we need to find an integer x such that
xa 1 (mod q), i.e., xa + yq = 1. This is done by extended Euclid’s
algorithm, which has complexity
O(n3).
It is also possible to compute
(am
mod q) by a polynomial time algo-
rithm. (Note that we speak about an algorithm that is polynomial in the
length n of its input (a, m, q); therefore performing m multiplications is out
of the question. Note also that the size of the integer
am
is exponential.) But
we can compute
(a2k
mod q) for k = 1, 2,..., log2 m by repeated squaring,
applying the (mod q) reduction at each step. Then we multiply some of the
results in such a way that the powers, i.e., the numbers
2k,
add to m (us-
ing the binary representation of m). This takes O(log m) = O(n) modular
multiplications, which translates to circuit size
O(n3).
4.2.3. The algorithm. Assume that a number q is given.
Step 1. If q is even (and q = 2), then q is composite. If q is odd, we
proceed to Step 2.
Step 2. Let q 1 =
2k
l, where k 0, and l is odd.
Step 3. We choose a random a {1,...,q 1}.
Step 4. We compute
al,a2l,a4l,..., a2kl
=
aq−1
modulo q.
Test 1. If
aq−1
= 1 (where modular arithmetic is assumed), then q is
composite.
Test 2. If the sequence
al,a2l,...,a2kl
(Step 4) contains a 1 that is
preceded by anything except ±1, then q is composite. In other words, if
there exists j such that
a2jl
= ±1 but
a2j+1l
= 1, then q is composite.
In all other cases the algorithm says that “q is prime” (though in fact it
is not guaranteed).
Theorem 4.3. If q is prime, then the algorithm always (with probability 1)
gives the answer “prime”.
If q is composite, then the answer “composite” is given with probability
at least 1/2.
http://dx.doi.org/10.1090/gsm/047/06
Previous Page Next Page