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