The CREW PRAM Complexity of Modular Inversion.
One of the long-standing open questions in the theory of parallel computation is the parallel complexity of the integer gcd and related problems, such as modular inversion. We present a lower bound $\Omega (\log n)$ for the parallel time on a concurrent-read exclusive-write parallel random access machine (CREW PRAM) computing the inverse modulo certain n-bit integers, including all such primes. For infinitely many moduli, our lower bound matches asymptotically the known upper bound. We obtain a similar lower bound for computing a specified bit in a large power of an integer. Our main tools are certain estimates for exponential sums in finite fields.
Introduction
. In this paper we address the problem of parallel computation of the inverse of
integers modulo an integer M . That is, given positive integers M # 3 and x < M , with gcd(x,
we want to compute its modular inverse inv M (x) # N defined by the conditions
is the Euler function, inversion can be considered as a special
case of the more general question of modular exponentiation. Both these problems can also be considered
over finite fields and other algebraic domains.
For inversion, exponentiation and gcd, several parallel algorithms are in the literature [1, 2, 3, 9, 10, 11,
12, 13, 14, 15, 18, 20, 21, 23, 28, 30]. The question of obtaining a general parallel algorithm running in
poly-logarithmic time (log n) O(1) for n-bit integers M is wide open [11, 12].
Some lower bounds on the depth of arithmetic circuits are known [11, 15]. On the other hand, some
examples indicate that for this kind of problem the Boolean model of computation may be more powerful
than the arithmetic model; see discussions of these phenomena in [9, 11, 15].
In this paper we show that the method of [5, 26] can be adapted to derive non-trivial lower bounds on
Boolean concurrent-read exclusive-write parallel random access machines (CREW PRAMs). It is based
on estimates of exponential sums.
Our bounds are derived from lower bounds for the sensitivity #(f) (or critical complexity) of a Boolean
function . It is defined as the largest integer m # n such
that there is a binary vector
the vector obtained from x by flipping its ith coordinate. In other words, #(f) is the maximum, over all
input vectors x, of the number of points y on the unit Hamming sphere around x with f(y) #= f(x); see
e.g., [31].
Since [4], the sensitivity has been used as an e#ective tool for obtaining lower bounds of the CREW PRAM
complexity, i.e., the time complexity on a parallel random access machine with an unlimited number of
all-powerful processors, where each machine can read from and write to one memory cell at each step, but
where no write conflicts are allowed: each memory cell may be written into by only one processor, at each
time step.
Fachbereich Mathematik-Informatik, Universitat Paderborn, 33095 Paderborn, Germany (gathen@uni-paderborn.de)
School of MPCE, Macquarie University, Sydney, NSW 2109, Australia (igor@mpce.mq.edu.au)
J. VON ZUR GATHEN AND I. E. SHPARLINSKI
By [22], 0.5 log 2
(#(f)/3) is a lower bound on the parallel time for computing f on such machines, see
also [6, 7, 8, 31]. This yields immediately the lower bound #(log n) for the OR and the AND of n input
bits. It should be contrasted with the common CRCW PRAM, where write conflicts are allowed, provided
every processor writes the same result, and where all Boolean functions can be computed in constant time
(with a large number of processors).
The contents of the paper is as follows. In Section 2, we prove some auxiliary results on exponential sums.
We apply these in Section 3 to obtain a lower bound on the sensitivity of the least bit of the inverse modulo
a prime. In Section 4, we use the same approach to obtain a lower bound on the sensitivity of the least
bit of the inverse modulo an odd squarefree integer M . The bound is somewhat weaker, and the proof
becomes more involved due to zero-divisors in the residue ring modulo M , but for some such moduli we are
able to match the known upper and the new lower bounds. Namely, we obtain the lower bound #(log n) on
the CREW PRAM complexity of inversion modulo an n-bit odd squarefree M with not 'too many' prime
divisors, and we exhibit infinite sequences of M for which this bound matches the upper bound O(log n)
from [11] on the depth of P-uniform Boolean circuits for inversion modulo a 'smooth' M with only `small'
prime divisors; see (4.6) and (4.7). For example, the bounds coincide for moduli
are any #s/ log s# prime numbers between s 3 and 2s 3 .
We apply our method in Section 5 to the following problem posed by Allan Borodin (see Open Question 7.2
of [11]): given n-bit positive integers m, x, e, compute the mth bit of x e .
Generally speaking, a parallel lower bound #(log n) for a problem with n inputs is not a big surprise. Our
interest in these bounds comes from their following features:
. some of these questions have been around for over a decade;
. no similar lower bounds are known for the gcd;
. on the common CRCW PRAM, the problems can be solved in constant time;
. for some types of inputs, our bounds are asymptotically optimal;
. the powerful tools we use from the theory of finite fields might prove helpful for other problems
in this area.
2. Exponential sums. The main tool for our bounds are estimates of exponential sums. For positive
integers M and z, we write eM
The following identity follows from the formula for a geometric sum.
Lemma 2.1. For any integer a,
Lemma 2.2. For positive integers M and H, we have
X
is the remainder of H - 1 modulo M .
THE CREW PRAM COMPLEXITY OF MODULAR INVERSION 3
Proof. We note that
Thus
X
From Lemma 2.1 we see that the last sum is equal to MW , where W is the number of (x, y) with
It is easy to see that
and the result follows.
Taking into account that (r we derive from Lemma 2.2 that the bound
X
holds for any H and M .
Also, it is easy to see that for H # M , then the identity of Lemma 2.2 takes the form
X
Finally, we have
X
Indeed, this sum is smaller by the term corresponding to a = 0, which equals H 2 .
4 J. VON ZUR GATHEN AND I. E. SHPARLINSKI
In the sequel, we consider several sums over values of rational functions in residue rings, which may not
be defined for all values. We use the symbol
P # to express that the summation is extended over those
arguments for which the rational function is well-defined, so that its denominator is relatively prime to the
modulus. We give an explicit definition only in the example of the following statement, which is known as
the Weil bound ; see [19, 25, 32].
Lemma 2.3. Let f, g # Z[X] be two polynomials of degrees n, m, respectively, and p a prime number such
that the rational function f/g is defined and not constant modulo p. Then
X
# (n +m- 1)p 1/2 .
Let #(k) denote the number of distinct prime divisors of an integer k. The following statement is a
combination of the Chinese Remainder Theorem and the Weil bound.
Lemma 2.4. Let M # N be squarefree with M # 2, d a divisor of M , and f, g # Z[X] of degrees n, m,
respectively, such that the rational function f/g is defined and not constant modulo each prime divisor
of M . Then
X
Proof. In the following, p stands for a prime divisor of M . We define M p # N by the conditions
Then, one easily verifies the identity
We use the estimate of Lemma 2.3 for those p for which p |
/ d and p > max{n, m}, and estimate trivially
by p the sum for each other p. Then
X
# Y p |
(n +m- 1)p 1/2
Y p|d
Since #(M/d) #(M), we obtain the desired estimate.
Lemma 2.5. Let M # 2 be a squarefree integer, f, g # Z[X] of degrees n, m, respectively, such that f/g
is defined and neither constant nor a linear function modulo each prime divisor p of M . Then for any
N,H, d # N with H # M and d|M , we have
X
Proof. From Lemma 2.1 we obtain
X
X
X
X
X
From Lemma 2.4 we see that for each a < M the sum over u can be estimated as
X
d. Applying the estimate (2.2), we obtain the result.
The following result is the particular case Theorem 1 of [29].
Lemma 2.6. There exists a constant c such that for all polynomials
with gcd(a t , . , a 1 ,
X
For a 0 , . , a k-1 # Z, not all zero, we define (a 0 , . , a k-1 ) to be the largest exponent e for which 2 e
divides a 0 , . , a k-1 .
Lemma 2.7. Let a 0 , . , a k-1 # Z not be all zero, and
a
Proof. We extend  to Q by (a/b) = (a)-(b) and to nonzero matrices in Q kk by taking the minimum
value at all nonzero columns. Then (U  v) # (U)+(v) for a matrix U and a vector v such that Uv #= 0.
. The determinant of this Vandermonde matrix has value
6 J. VON ZUR GATHEN AND I. E. SHPARLINSKI
We consider an entry of the adjoint adC k of C k . Each of the summands contributing to the determinant
expansion of that entry is divisible by
so that
(In fact, we have equality, since det C k-1 has the right hand side as its -value and is one entry of adC k .)
Therefore
Now from the inequality
(b) the result follows.
We also need an estimate on the number of terms in the sum of Lemma 2.5. For a polynomial g # Z[X]
and M,H # Z, we denote by T g (M,H) the number of x # Z for which 0 # x < H and gcd (g(x), M) = 1.
The following result is, probably, not new and can be improved via more sophisticated sieve methods.
Lemma 2.8. Let M > 1 be squarefree and g # Z[x] of degree m such that gcd(g(x),
Z. Then for all integers H # M , we have
Proof. We denote by #(M, H) the number of x # {0, . , H - 1} such that
and set is squarefree, the inclusion-exclusion principle yields
#(d)=k
#(d, H).
For any divisor d of M we have
d
#(p).
Therefore,
#(d)=k
#(d)
#(d)
By assumption, g takes a nonzero value modulo every prime divisor p of M . Thus #(p) # min{m, p - 1},
and the claim follows.
Throughout this paper, log z means the logarithm of z in base 2, ln z means the natural logarithm, and
1, if z # 1.
Lemma 2.9. For positive integers m and M , with M > 1 squarefree, we have
Y
Proof. We split the logarithm of the product as follows
p#2m
p>2m
,
and prove a lower bound on each summand. For the first one, we use that
for x > 1
by [24], (3.15). Thus, for m > 1
p#2m
p#2m
It is easy to verify that for the sum on the left hand side does not exceed 3m as well.
For the second summand, we use that (1
This implies that
p>2m
p>2mp
From [24], (3.20), we know that
s be the sth prime number, so that p s # s 2 for s # 2.
Thus for s # 2 we have
2.
The inequality between the first and last term is also valid for s = 1. Now (2.4), (2.5), and (2.6) imply
the claim.
8 J. VON ZUR GATHEN AND I. E. SHPARLINSKI
3. PRAM complexity of the least bit of the inverse modulo a prime number. In this
section, we prove a lower bound on the sensitivity of the Boolean function representing the least bit of
the inverse modulo p, for an n-bit prime p. For x # N with gcd(x, we recall the definition of
in (1.1). Furthermore, for x 0 , . , x n-2 # {0, 1}, we let
We consider Boolean functions f with n - 1 inputs which satisfy the congruence
for all x 0 , . , x n-2 # {0, 1} with no condition is imposed for the value
of f(0, . , 0).
Finally we recall the sensitivity # from the introduction.
Theorem 3.1. Let p be a su#ciently large n-bit prime. Suppose that a Boolean function f(x 0 , . , x n-2 )
satisfies the congruence (3.2). Then
log n - 1.
Proof. We let k be an integer parameter to be determined later, with 2 # k # n - 3, and show that
large enough. For this, we prove that there is some integer z with 1 # z # 2 n-k-1 and
provided that p is large enough. We note that all these 2 k z and 2 k z are indeed invertible modulo p.
We set e k. Then it is su#cient to show that there exist
integers z, w 0 , . , w k with
Next we set k. Then it is su#cient
to find integers x, y, u 0 , . ,
Indeed from each solution of the system (3.4) we obtain a solution of the system (3.3) by putting
On the other hand, the system (3.4) contains more variables
and is somewhat easier to study. A typical application of character sum estimates to systems of equations
proceeds as follows. One expresses the number of solutions as a sum over a # Z p , using Lemma 2.1, then
isolates the term corresponding to a = 0, and (hopefully) finds that the remaining sum is less than the
isolated term. Usually, the challenge is to verify the last part. In the task at hand, Lemma 2.1 expresses
the number of solutions of (3.4) as
THE CREW PRAM COMPLEXITY OF MODULAR INVERSION 9
a
a
a
where the first summand corresponds to a R to the remaining sum, and we used
(2.2). For other the sum over x, y satisfies the conditions of Lemma 2.5, with
a
where
a i
Therefore f/g is neither constant nor linear modulo p. Thus,
Y
X
We have left out the factors |e p (-a i # i )|, which equal 1, transformed the summation index 2a i into a i ,
and used the identity (2.2).
It is su#cient to show that H 2 K 2(k+1) is larger than |R|, or that
Since K # (p - 6)/4, it is su#cient that
(3.
J. VON ZUR GATHEN AND I. E. SHPARLINSKI
We now set log n)/6#, so that 6(k 2. Now (1
real z > 0, and
2.
Furthermore, p 1/2 < 2 n/2 and 32n/3 < n 3/2 , and (3.6) follows from
log n
Hence the inequality (3.5) holds, and we obtain #(f) # k # n/6 - 0.5 log n - 1.
From [22] we know that the CREW PRAM complexity of any Boolean function f is at least 0.5 log(#(f)/3),
and we have the following consequence.
Corollary 3.2. Any CREW PRAM computing the least bit of the inverse modulo a su#ciently large
n-bit prime needs at least 0.5 log n - 3 steps.
4. PRAM complexity of inversion modulo an odd squarefree integer. In this section, we
prove a lower bound on the PRAM complexity of finding the least bit of the inverse modulo an odd
squarefree integer.
To avoid complications with gcd computations, we make the following (generous) definition. Let M be an
odd squarefree n-bit integer, and f a Boolean function with n inputs. Then f computes the least bit of the
inverse modulo M if and only if
for all x # {0, 1} n-1 with gcd(num(x), is the nonnegative integer with binary
representation x, similar to (3.1). Thus no condition is imposed for integers x # 2 n or that have a
nontrivial common factor with M .
Theorem 4.1. Let M > 2 be an odd squarefree integer with #(M) distinct prime divisors, and f the
Boolean function representing the least bit of the inverse modulo M , as above. Then
4Lnln #(M) +O(1) .
Proof. We let k an integer parameter to be determined later. We want to show that
there is some integer z with 1 # z # 2 n-k-1 for which
As in the proof of Theorem 3.1 we see that in this case #(f) # k.
We put e k. It is su#cient to show that there exist integers
such that
Next, we set As in the proof of
Theorem 3.1 we see that it is su#cient to find integers x, y, u 0 , . , satisfying the following
THE CREW PRAM COMPLEXITY OF MODULAR INVERSION 11
conditions for
Lemma 2.1 expresses the number of solutions as
a
a
a
a
where S d is the subsum over those 0 # a 0 , . , a k < M for which
It is su#cient to show that
d<M
|S d |.
First we note that SM consists of only one summand corresponding to a
to be added equal 1, we only have to estimate the number of terms for which the argument of
defined. For each y with 0 # y < H, we apply Lemma 2.8 to the polynomial
of degree k + 1. We set using Lemmas 2.8 and 2.9, we deduce that
The other |S d | are bounded from above by
X
a
J. VON ZUR GATHEN AND I. E. SHPARLINSKI
a
Now let
a i
d
Then
a i
d
and f/g is neither constant nor linear modulo any prime divisor . Thus we can apply
Lemma 2.5 and find that
X
a
the hypothesis of the lemma is satisfied because M is squarefree. If d < M , then a
M/d, with at least one b i #= 0. Then
e M/d
e M/d
1#b0<M/d
X
X
Since M/d is odd, we may replace the summation index 2b i by b i . From the inequalities (2.3) and (2.1)
we find
1#b0<M/d
X
X
Combining these inequalities, we obtain
therefore
d<M
d -3/2
where
Using (4.1) and (4.2) it is now su#cient to prove that
for some
To do so we suppose that
and will show that k satisfies the opposite inequality. Obviously, we may assume that
We also recall that K # (M - 6)/4 and
# M2 -k-3 . Now if
immediately obtain (4.3). Otherwise, we derive from (4.4) that
Comparing this inequality with the inequality (4.3) we obtain the desired statement.
Our bound takes the form
for an odd squarefree n-bit M with #(M) # ln M/LnlnM for some constant # < 0.5. We recall that
almost all odd squarefree
numbers M .
14 J. VON ZUR GATHEN AND I. E. SHPARLINSKI
We denote by i PRAM (M) and i BC (M) the CREW PRAM complexity and the Boolean circuit complexity,
respectively, of inversion modulo M . We know from [11, 21] that
for any n-bit integer M . The smoothness #(M) of an integer M is defined as its largest prime divisor, and
M is b-smooth if and only if #(M) # b. Then
Since we are mainly interested in lower bounds in this paper, we do not discuss the issue of uniformity.
Corollary 4.2.
for any odd squarefree n-bit integer M with #(M) # 0.49 ln M/LnlnM .
Theorem 4.3. There is an infinite sequence of moduli M such that the CREW PRAM complexity and
the Boolean circuit complexity of computing the least bit of the inverse modulo M are both #(log n), where
n is the bit length of M .
Proof. We construct infinitely many odd squarefree integers M with #(M) # 0.34 ln M/LnlnM , thus
satisfying the lower bound (4.8), and with smoothness thus satisfying the upper
bound O(ln ln O(log n) of [11] on the depth of Boolean circuits for inversion modulo such M .
For each integer s > 1 we select #s/ ln s# primes between s 3 and 2s 3 , and let M be the product of these
primes. Then, M # s 3s/
large enough.
5. Complexity of one bit of an integer power. For nonnegative integers u and m, we let Btm (u)
be the mth lower bit of u, i.e., Btm
with each u i # {0, 1}. If u
In this section, we obtain a lower bound on the CREW PRAM complexity of computing Btm (x e ). For
small m, this function is simple, for example Bt 0 can be computed in one step. However, we
show that for larger m this is not the case, and the PRAM complexity is #(log n) for n-bit data.
Exponential sums modulo M are easiest to use when M is a prime, as in Section 3. In Section 4 we had
the more di#cult case of a squarefree M , and now we have the extreme case
Theorem 5.1. Let m and n be positive integers with f be the Boolean function
with 2n inputs and
Proof. We set
, and consider so that #(f) #(g). Furthermore, k is an integer
parameter with e # k # 2 to be determined later.
To prove that #(g) # k, it is su#cient to show that there exists an integer x with
The first equality holds for any such x because e 2
# m, and thus the conditions are equivalent to the
existence of integers x, u 0 , . , u k-1 such that
which is implied by the existence of x, u 0 . , u k-1 , v 0 , . , v k-1 with
We set
Lemma 2.1 expresses the number of solutions of (5.1) as
a
a
a
is the subsum over all integers 0 # a 0 , . , a k-1 < 2 m with
It is su#cient to show that
0#<m
Sm contains only one summand, for a
Using the function  from Section 2, we have for # < m that
(a 0 ,.,a k-1 )=#
X
a
J. VON ZUR GATHEN AND I. E. SHPARLINSKI
Now let a 0 , . , a k-1 < 2 m . We set
a
0#j#e
so that
a
We put
X
where c is the constant from Lemma 2.6. This bound also holds for # m, because the sum contains
terms with absolute value 1. Using the (crude) estimate
e
e,
and noting that
a
from Lemma 2.7 we derive that for tuples with (a 0 , . , a k-1
provided that k # 2. Substituting this bound in (5.5), we obtain
where
(a
THE CREW PRAM COMPLEXITY OF MODULAR INVERSION 17
We set
2.
and as in the proof of Theorem 4.1, from Lemma 2.2 we find
Next, we obtain
0#<m
0#<m
ck  2 n+2mk-k-e-m/e-k 2 /2e+3
0#<m
< ck  2 n+2mk-k-e-m/e-k 2 /2e+4 .
We set
-m 1/3
It easy to verify that the inequality (5.2)
holds for this choice of k, provided that m is large enough.
Corollary 5.2. Let . The CREW PRAM complexity of finding the mth bit of an n-bit
power of an n-bit integer is at least 0.25 log m- o(log m). In particular, for
6. Conclusion and open problems. Inversion in arbitrary residue rings can be considered along
these lines. There are two main obstacles for obtaining similar results. Instead of the powerful Weil estimate
of Lemma 2.3, only essentially weaker (and unimprovable) estimates are available [17, 27, 29]. Also, we
need a good explicit estimate, while the bounds of [17, 27] contain non-specified constants depending on
the degree of the rational function in the exponential sum. The paper [29] deals with polynomials rather
than with rational functions, and its generalization has not been worked out yet.
Open Question 6.1. Extend Theorem 4.1 to arbitrary moduli M .
Moduli of the form prime number, are of special interest because Hensel's lifting
allows to design e#cient parallel algorithms for them [2, 11, 15]. Theorem 5.1 and its proof demonstrate
how to deal with such moduli and what kind of result should be expected.
Each Boolean function f(X 1 , . , X n ) can be uniquely represented as a multilinear polynomial of degree
of the form
0#k#d
1#i1<.<ik #r
We define its weight as the number of nonzero coe#cients in this representation. Both the weight and the
degree can be considered as measures of complexity of f . In [5, 26], the same method was applied to obtain
J. VON ZUR GATHEN AND I. E. SHPARLINSKI
good lower bounds on these characteristics of the Boolean function f deciding whether x is a quadratic
residue modulo p. However, for the Boolean functions of this paper, the same approach produces rather
poor results.
Open Question 6.2. Obtain lower bounds on the weight and the degree of the Boolean function f of
Theorem 4.1.
It is well known that the modular inversion problem is closely related to the GCD-problem.
Open Question 6.3. Obtain a lower bound on the PRAM complexity of computing integers u, v such
that relatively prime integers M # N > 1.
In the previous question we assume that gcd(N, M) = 1 is guaranteed. Otherwise one can easily obtain
the lower bound #(f) #(n) on the sensitivity of the Boolean function f which on input of two n-bit
integers M and N , returns 1 if they are relatively prime, and 0 otherwise. Indeed, if is an n bit
integer, then the function returns 0 for That is, the PRAM
complexity of this Boolean function is at least 0.5 log n +O(1).

Acknowledgment

. This paper was essentially written during a sabbatical visit by the second author
to the University of Paderborn, and he gratefully acknowledges its hospitality and excellent working
conditions.



--R



'Parallel Implementation of Schonhage's Integer GCD Algorithm'






Joachim von zur Gathen and Daniel Panario
Joachim von zur Gathen
Joachim von zur Gathen
Joachim von zur Gathen
Joachim Von Zur Gathen
Joachim von zur Gathen and Gadiel Seroussi
Introduction to number theory




Michal M



Theory and computation
Number theoretic methods in cryptography: Complexity lower bounds




The complexity of Boolean functions

--TR
parallel computation;CREW PRAM complexity;exponential sums;modular inversion