EFFICIENT VERIFICATION OF TUNNELL’S CRITERIONERIC BACH AND NATHAN C. RYAN

Abstract. An integer n is congruent if there is a triangle with rational sides
whose area is n. In the 1980s Tunnell gave an algorithm to test congruencewhich relied on counting integral points on the ellipsoids 2x2 + y 2 + 8z 2 = n
and 2x2 + y 2 + 32z 2 = n. The correctness of this algorithm is conditionalon the conjecture of Birch and Swinnerton-Dyer. The known methods fortesting Tunnell’s criterion use O(n) operations. In this paper we give several
methods with smaller exponents, including a randomized algorithm using time
n1/2+o(1) and space no(1) , and a deterministic algorithm using space and time
n1/2+o(1) .

1. Introduction
A positive integer n is said to be congruent if there exists a right triangle withrational sides whose area is n. Since this property is unaffected when we multiply
n by a square, we may as well assume that n is squarefree. A natural way to study
this property is to consider the elliptic curve En , whose Weierstrass equation isy 2 = x3 − n2 x. Let En (Q) denote the group of rational points on En . Its torsion
group has order 4 (the point at infinity, together with three points at which y = 0).
From this observation, one can see that n is congruent if and only if En (Q) has
positive rank.
In the 1980s, Tunnell [24], using results of Coates and Wiles, and the Shimura
correspondence, showed that when n is congruent, the number of integral points
on a specific ellipsoid was half the number of points on another specific one (seesection 2 for more details). Assuming the Birch and Swinnerton-Dyer conjecture(BSD), he also showed the converse.
Proofs of these assertions, as well as a statement of this conjecture, may be foundin the book of Koblitz [13].
Thus, assuming BSD, there is an algorithm to test congruence. The purpose ofthis article is to investigate efficient realizations of this algorithm. We will present
methods for verifying the congruence of an integer n that are more efficient thanthose present in the literature. In particular, our methods use n1/2+o(1) arithmetic
Date: June 27, 2006 and, in revised form, October 4, 2006.
1991 Mathematics Subject Classification. Primary 11F46, 11F60; Secondary 65D20, 65-04.
Key words and phrases. Congruent numbers, quadratic forms, class field theory, algorithms,
complexity.
The RMMC Summer School in Computational Number Theory and Cryptography was fundedby NSF grant DMS-0612103, the Rocky Mountain Mathematics Consortium, The Number Theory
Foundation, The Institute for Mathematics and its Applications (IMA), The Fields Institute, The
Centre for Information Security and Cryptography (CISaC) and iCORE of Canada. As this paper
is an outgrowth of this conference, the authors would like to thank all these sponsors. We would
also like to thank the University of Wyoming for hosting the conference. Thanks to Dieter van
Melkebeek for quantum advice.
1

2

ERIC BACH AND NATHAN C. RYAN

operations, whereas those previously known use O(n). Even with BSD, it is notclear whether congruence can be tested using O (nα ) arithmetic operations, withα < 1/2.
The paper is organized as follows. In section 2 we give Tunnell’s criterion, andin section 3 we review results we will need on representation by quadratic forms.
The algorithms themselves are described in sections 4 and 5, and their experimental
tests in section 6. In section 7, we review the other algorithms known to us, andin section 8, we conclude with an investigation of complexity classes containing theset of congruent numbers.
2. Tunnell’s Criterion
The main result of [24] is the following theorem.
Theorem 2.1 (Tunnell’s Criterion [24]). Assume the conjecture of Birch and
Swinnerton-Dyer. Then a squarefree positive integer n is congruent if and only
if
n
no
(2.1)
(x, y, z) ∈ Z3 : 2ax2 + y 2 + 8z 2 =n ano= 2 (x, y, z) ∈ Z3 : 2ax2 + y 2 + 32z 2 =
a
where
(
1 if n is odda=.
2 if n is even
We will refer to the quadratic form 2x2 + y 2 + 8z 2 as Q1 .
A couple of results can be checked immediately – they are both found in [13].
First, if n ≡ 5, 6, 7 (mod 8) we deduce that Tunnell’s criterion holds. Second,
Proposition 2.2. (2.1) holds for odd squarefree n if and only if
(2.2)(x, y, z) ∈ Z3 : Q1 (x, y, z) = n, z odd =
(x, y, z) ∈ Z3 : Q1 (x, y, z) = n, z even.

For even squarefree n, replace n by n/2 and Q1 by the quadratic form Q3 (x, y, z) =4x2 + y 2 + 8z 2 .
A brute force way to count√the number of solutions on either side of (2.1) is toiterate x, y and z from 0 to n and track the number of solutions to either side.
This requires examining O(n3/2 ) triples, as remarked by Tunnell. In what follows
we reduce the exponent to 1/2.
3. Some algebraic number theory
For a quadratic form (binary or ternary), let rQ (n) denote the number of integer
solutions to Q(x, y, z) = n (or Q(x, y) = n). The number rQ (n) is called therepresentation number of n.
Let Q(x, y) = 2x2 + y 2 . To produce our algorithm in section 4 we will need todetermine (a) for which odd n we have rQ (n) > 0 and, if possible, (b) the numberrQ (n) itself.

EFFICIENT VERIFICATION OF TUNNELL’S CRITERION

3√
Let K = Q( −2). Let p ∈ Z be an odd
Look at the ideal (p) in prime.
√a
OK = Z[ −2], the ring of integers of K. Let p be the Jacobi symbol. Then we
have the following standard result (see e.g., [12]): 
Lemma 3.1.
(a) p ≡ 1, 3 (mod 8) iff −2= 1 iff p splits in Kp (b) p ≡ 5, 7 (mod 8) iff −2= −1 iff p is inert in Kp(c) 2 ramifies.
Using Lemma 3.1 we can answer question (a) as posed above for Q(x, y) =2x2 + y 2 . Our argument is a special case of an argument that can be found in, forexample, [2]. Suppose n factors as
Y
Y
α
pj j
pβkk .
pj ≡1,3

pk ≡5,7(mod 8)(mod 8)Then the ideal (n) factors in OK as
Y α αj Y(n) =Pj j Pj0(pk )βk .
j

k

2
2
Each
√ y) to 2x + y = n corresponds to a factorization of (n) into
√ solution (x,(x + y −2)(x − y −2). Trying to reconcile this with the other factorization of (n)forces us to conclude that all the βk are even sinceY γ αj −γj Y√
βk(x + y −2) =Pj j Pj0(pk ) 2jk

and this only makes sense for βk even.
It is well-known that the class number of K is 1 and so every ideal is principal.
If we push our ideals into the ideal class group of K (this is denoted by [I] for someideal I) we see that each solution to Q(x, y) = n corresponds to the equality
Y γ αj −γj√[(x + y −2)] = [1] =Pj j Pj0,
jwhere 0 ≤ γj ≤ αj . (Note that we are not counting units.) This holds for
Q all suchγj since OK is a principal ideal domain. Thus, modulo units, there are j (1 + αj )solutions to 2x2 + y 2 = n, assuming that all the βk are odd.
It is well-known, also, that the unit group of OK has two elements. So we needto double the number of solutions to get the following result:
Theorem 3.2. Let n be odd with the prime factorization
Y
Y
α
n=
pj j
pβkk .
pj ≡1,3(mod 8)pk ≡5,7(mod 8)Let Q(x, y) = 2x2 + y 2 . Then(0, if some βk is odd;rQ (n) =Q
2 j (1 + αj ), if all βk are even.
To test congruence of even numbers we will need to determine the number ofsolutions to(3.1)

4x2 + y 2 = n

4ERIC BACH AND NATHAN C. RYAN

from the factorization of n. This can be reduced to studying sums of squares, as
follows. We note that (3.1) is the same as n = z 2 + y 2 , with z even. So we consider
the parity of z and y. If n is odd, exactly one of z, y is even, so the number ofsolutions to (3.1) is half the number of solutions to z 2 + y 2 = n. If n is even, then z
and y are both odd or both even. In the first case, we don’t get a solution to (3.1),
and in the second case, n must be divisible by 4. Hence, when n ≡ 2 mod 4, there
are no solutions to (3.1), and when n ≡ 0 mod 4, the number of solutions equals
the number of solutions to x2 + y 2 = n/4.
To count the number of solutions to x2 + y 2 = m, we first count the ideals ofnorm m in Z[i]. This number is the product of local factors, as follows. Supposethat pα ||m. Then the local factor is 1 for p = 2, 1 + α for p ≡ 1 mod 4, and 1 (resp.
0) for p ≡ 3 mod 4 and α even (resp. odd). To get the number of representations,
we multiply together the local factors for each prime dividing m, and multiply by
4 since Z[i] has 4 units. For example
2340 = 22 · 5 · 13 · 32
has 4 · 1 · 2 · 2 · 1 = 16 representations.
The local factors can be justified as follows. In Z[i], 2 is ramified, so there is only
one ideal of norm 2α . An odd prime p is inert if it is 3 mod 4, and split otherwise.
In the first case, there will be an ideal of norm pα exactly when α is even, and only
one such. In the second case, write p = P P 0 for prime ideals P and P 0 . By uniqueideal factorization, an ideal Q has norm pα iff
Q = P γ (P 0 )α−γ ,0 ≤ γ ≤ α.

As before, there are α + 1 choices for γ.
We conclude this section with a historical note. Certainly, counting representations of integers by quadratic forms is a classical problem. For the forms of interest
to us, these counts were often expressed by tallying divisors in various congruenceclasses. A number of such results appear in Hua [11, pp. 307-309]; see also Dickson[4, v. 2, p. 248; v. 3, p. 38]. Gauss [10, art. 182] counted the solutions to x2 + y 2
as we have, by grouping prime factors into arithmetic progressions. Nowadays, werecognize this as a superior method, because factoring is generally more efficientthan listing divisors.
4. An improvement
Our improvement over the brute force method
replaces a triple loop (over x, y, z)
pby a single one that iterates z from 0 to n/8. By Proposition 2.2 we need only
count solutions to Q(x, y, z) = n, and tally these separately for even and odd z.
The solution-counts use the theorems in section 3.
Using Algorithm 1 we can derive Algorithm 2, implicit in Theorem 2.1.
In broad strokes, Algorithm 2 proceeds as follows: factor all m of the formpn − 8z 2 where 0 ≤ z ≤ n/8.
Using the formula for the number of solutions to x2 + 2y 2 = m derived in Theorem 3.2, we count the solutions for all such solutions. If the total for even z
equals the total for odd z, then we know Tunnell’s criterion is satisfied. Note that
Proposition 2.2 allows us to consider only one quadratic form, rather than two.

EFFICIENT VERIFICATION OF TUNNELL’S CRITERION

5

Algorithm 1 Counts representations by the quadratic forms in (2.1)
Require: n ∈ Z+ odd.
evenCount ← 0
oddCount ←p0
for z = 0 to n/8 do
Q
α Q
Factor n − 8z 2 as pj ≡1,3 (mod 8) pj j pk ≡5,7 (mod 8) pβkk
if all βk odd then Q
count ← count + 2 j (1 + αj )end if
if z even thenevenCount ← evenCount + countelse
oddCount ← oddCount + countend ifend forreturn oddCount, evenCount
Algorithm 2 Determines if odd squarefree n is congruent
Require: n ∈ Z+ odd squarefree
Apply Algorithm 1 to n
if oddCount(n) = evenCount(n) thenreturn true
else
return false
end ifWhat is the cost of this algorithm? With present knowledge, the complexity offactoring depends on what kind of algorithm is allowed. More precisely, to factor anumber less than n uses nc+o(1) operations, where1 4 unconditionally [15]c = 15 assuming ERH [18]
0 if random choices are allowed [5].
Therefore, Algorithm 2 will determine if n satisfies Tunnell’s criterion using a number of operations that is
 3
+o(1)

unconditionally
n 4
7
+o(1)
10
n
assuming ERH
 21 +o(1)nwith randomness .
Note that the first two results refer to deterministic algorithms. Since probabilistic
factoring algorithms can be made errorless [23], the third algorithm is of Las Vegas
type (always correct, probably fast).
Since Algorithm 1 actually factors n, it can be used to tell if n is squarefree. If
n is not squarefree, the factorizations it computes are still useful, since if n = n0 r2 ,and z = z 0 r, we haven − 8z 2 = r2 (n0 − 8z 02 ).

6

ERIC BACH AND NATHAN C. RYAN

We remark that the above algorithm will find representation numbers for any
ternary quadratic form
x2 + by 2 + cz 2
so that the class number of x2 + by 2 is 1, in particular if b is a Heegner number.
5. Factoring with Sieves
In this section we discuss a modification to Algorithm 1 that improves the run2
ning time, at thep cost of more space. Recall that Algorithm 1 factors n − 8z forall z, 0 ≤ z < n/8. Because these are successive values of a fixed polynomial,
we can factor them together using a sieve. This is similar to what is done in thequadratic sieve factoring algorithm [16].
We will assume that n is odd. (Modifications for n even are left to√ the reader.)It will be enough to partially factor n − 8z 2 over the primes up to n, since any
unfactored part left must be prime. We use the sieve for these partial factorizations,following with a “clean up” phase to obtain complete factorizations.
In the sieving process, p = 2 can be skipped, since n − 8z 2 is odd if n is. We notealso that for odd p, we have p|n − 8z 2 iff z 2 ≡ n/8 mod p. This is only possible if
p|n, or if the Jacobi symbol (2n|p) = +1.
Algorithm 3 Factors all positive n − 8z 2
Require: n ∈ Z+ odd √for primes p, 3 ≤ p ≤ n do
if p|n, mark all z ≡ 0 mod p with the factor p
if (2n|p) = −1, skip this prime.
if (2n|p) = +1, let z1 , z2 be the roots of 8z 2 ≡ n mod p, with 0 < z1 < z2 < p.
Markz1 , z1 + p, z1 + 2p, . . . , z1 + k1 p
andz2 , z2 + p, z2 + 2p, . . . , z2 + k2 p
pwith the factor p. It will be necessary to go up to ki ≤ ( n/8 − zi )/p.
end for pp
for z = − n/8 to n/8 do
let p1 , . . . , pr be the factors of n − 8z 2 found above.
for each i, find ei such that pei i ||n − 8z 2 .
if q = n/(pe11 · · · perr ) is greater than 1, let
pr+1 = q,er+1 = 1.

end forWe now analyze the complexity of this procedure. By Mertens’s theorem, thecost of marking the z’s will be about√ X 2n= O(n1/2 log log n)
√ p
p≤ n

√
√
operations. We need to solve π( n) − 1 ∼ 2 n/ log n quadratic equations mod p.
Such equations are solvable in polynomial time, using the Tonelli-Shanks algorithm[19], provided a quadratic nonresidue for p is available. Since we will do this forEFFICIENT VERIFICATION OF TUNNELL’S CRITERION

7

many p, it will suffice to test a = 2, 3, 5, . . . until we find a number with (a|p) = −1.
Erdős [7] proved that if n(p) is the least quadratic nonresidue for p, thenX1n(p) = O(1).
π(x) − 13≤p≤x

Thus, the number of Jacobi symbols that will be computed in this process is at
most a constant times√
π( n) = O(n1/2 /(log n)).
Each Jacobi symbol can be computed in polynomial time, using a variant of the
Euclidean algorithm [3]. Processing each z in the last stage will use O(log n) operations, since a number bounded by n can have at most log2 n prime factors. Putting
everything together, we see that Algorithm 3 uses n1/2+o(1) operations.
In practice, one might want to use a randomized algorithm to solve the quadratic
equations, and there are several choices available for this. As we have stated it,
however, Algorithm 3 is deterministic and does not rely on ERH or any otherheuristic assumption. We thus get an improvement on the running times of the lastsection.
√
Algorithm
3 will√need space for the factorizations of O( n) numbers bounded√by n, that is, O( n log n) bits. Thus it will require more space than a version
of Algorithm 1 that “outsources” factorization. The space required by most recent
factoring algorithms, including the quadratic sieve [16], is no(1) .
6. Implementations of the Algorithms
Both Algorithm 2 and Algorithm 3 were implemented and timed using Victor
Shoup’s NTL [20]. NTL had all the required functionality except an integer factorization algorithm. The second author implemented Richard Brent’s [1] variantof Pollard’s rho algorithm. We tested each algorithm against the odd squarefree
integers less than a million. We tested each algorithm a number of times, and on average Algorithm 3 took fifty percent longer than Algorithm 2. Tunnell conjectured
that for non-congruent squarefree numbers, the modular form coefficient describedin the main theorem of [24] is always an integral multiple of the number of divisorsof n. We found no exceptions to this conjecture.
7. Other Methods
In this section we review the other known methods for testing Tunnell’s criterion.
As we noted above, a brute force computation uses O(n3/2 ) operations. The
exponent can be reduced to 1 by a “collision”√
method. We first make a list of O(n)triples (x2 + 2y 2 , x, y) and another list of O( n) pairs (n − 8z 2 , z). Sorting theseon the first component provides us with all solutions to 2x2 + y 2 + 8z 2 = n.
Another possibility is to use an analytic formula to compute L(En , 1) [13, p. 95].
This value is essentially the square of the difference count in Proposition 2.2, as theratio of these two values is an easily computed constant times n−1/2 . Thus, L(1) iseither 0 or Ω(n−1/2 ). By the estimates in [13] the coefficients in the series for L(1)are such that we would need O(n log n) terms in this series to tell these two cases
apart. This is thus another method with cost n1+o(1) .
Results of Elkies [6] suggest a point of infinite rank on the curve y 2 = x3 − n2 x
can be found in time O(n1/2 ). These results hold only for n ≡ 5, 7 mod 8, which

8

ERIC BACH AND NATHAN C. RYAN

we know satisfy Tunnell’s criterion. So this method is not an improvement over our
methods.
Yet another method was suggested to the second author by William Stein andalso requires looking at the curve En : y 2 = x3 − n2 x. The curve En is thequadratic twist of E1 , by a quadratic character of conductor dividing 4n. Thus
L(En , 1) 6= 0 if and only if the χ-twisted winding element in the 1-dimensional space
H1 (X0 (32), Q)+ of modular symbols of level 32 and weight 2 for Γ0 (32) is nonzero.
Computing this χ-twisted winding element takes O(n) arithmetic operations as it
requires one to sum over the a in Z/nZ. Our methods have exponents less than 1,
and so are asymptotically faster than this method.
In practice, elliptic curve ranks are often computed by methods using descent.
(See Chapter X of Silverman [21] for an overview.) There is no guarantee, however,that a computation of this kind will terminate.
8. Complexity-Theoretic Aspects of Tunnell’s Criterion
For this section, we assume knowledge of standard complexity classes, as can befound in [17]. At the end we assume some facts about quantum computation, forwhich [14] is a good reference.
Unconditionally, the best we can say is that the set of congruent numbers isrecursively enumerable. Indeed, one could enumerate congruent numbers by either
systematically considering all Pythagorean triples, or by searching for non-torsion
points on En (Q), n ≥ 1. (Since all square multiples of n give Q-isomorphic curves,the existence of such points is oblivious to square factors.) If Lang’s conjecture [21,p. 235] is true, this search could be restricted to rational points whose x-coordinateshave bit length ≤ n3+o(1) , as the discriminant of En is O(n6). (Technically, Langreferred to canonical height, but there are explicit bounds relating this to naive
height; see [22].) This would give an algorithm of cost exp(n3+o(1) ) to test congruence.
Let us now revert to assuming BSD. First, the non-congruent squarefree numbers
and their square multiples can also be enumerated, by testing Tunnell’s criterion.
Running both enumeration procedures in parallel, we would eventually classify every number as congruent or not. It is worth observing that any determination
resulting from this procedure is unconditionally correct; we only need BSD to guarantee that no number escapes.
Under BSD, the set of congruent numbers also belongs to PSPACE. To prove thiswe can use Algorithm 1, together with any factoring algorithm that uses polynomial
space (e.g. trial division).
One interesting subclass of PSPACE is C= P, defined as follows [25]. A language(set of integers in binary) L belongs to C= P when there is a nondeterministic
polynomial-time Turing machine M such that n ∈ L precisely when the number of
accepting paths for n equals the number of rejecting paths. We can show that theset of squarefree congruent numbers belongs to C= P, as follows. First, the set ofsquarefree numbers is in co-NP, which is a subclass of C= P [9, Cor. 4.11]. Second,
C= P is closed under intersection, which is easy to prove by observing that GapP
is closed under multiplication [9, Lemma 3.9]. By these observations, it is enoughto show how M works on squarefree inputs. We will show this for odd n, leaving
the other case to the reader. On input n, guess integers x, y, z with |x|, |y| ≤ n and−n − 1 ≤ z ≤ n. (The extra −1 is there to balance even and odd values of z.)

EFFICIENT VERIFICATION OF TUNNELL’S CRITERION

9

Then, evaluate Q1 (x, y, z). Accept the input if Q1 = n and z is even, or if Q1 6= n
and z is odd. Reject otherwise.
There is an interesting connection between this class and quantum computation.
Fenner, et al. [8] proved that the languages in C= P are exactly those whose complements are in NQP, the quantum analog of NP. This means, then, that there is apolynomial-time quantum algorithm with the following property: when applied toa squarefree integer n, the amplitude for the accepting output cancels to zero iff n iscongruent. Here we sketch a quantum circuit with this property, again considering
only odd n. The basic idea is to adapt the√Deutsch-Josza algorithm. First, chooser so that the integers of absolute value ≤ n are distinct mod 2r . It will suffice totake r = (1/2) log2 n+O(1). We dedicate an r-qubit register to each of x, y, z, using
2’s complement notation. (That is, a bit pattern with the leftmost bit equal to 1
represents a negative number.) Note that the number of even and odd z’s are automatically balanced. There is an additional qubit b, making ν = 3r + 1 qubits in all.
Let f be the Boolean function computed in the last paragraph, i.e. f (x, y, z) = 1
iff Q1 = n and z is even, or Q1 6= n and z is odd. Let H be a 2 × 2 Hadamard
matrix, and Uf the unitary matrix that takes |x, y, z, bi to |x, y, z, b ⊕ f (x, y, z)i;a quantum circuit for Uf can be built as indicated in [14, p. 158]. We begin thealgorithm by preparing the state|x, y, z, bi = |0 · · · 0, 0 · · · 0, 0 · · · 0, 1i.
⊗ν⊗νThen, apply H Uf H , observe all qubits, and accept iff x = y = z = 0. By theargument in [14, p. 35], the amplitude for this vanishes iff f is balanced, that is, iff
n is congruent.

10

ERIC BACH AND NATHAN C. RYAN

References
1. Richard P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), no. 2,
176–184.
2. J. Cilleruelo and A. Córdoba, Lattice points on ellipses, Duke Math. J. 76 (1994), no. 3,
741–750.
3. G. E. Collins and R. G. K. Loos, The Jacobi symbol algorithm, SIGSAM Bull. 16 (1982),
no. 1, 12–16.
4. L. E. Dickson, History of the Theory of Numbers. Three Volumes, Chelsea Publishing Co.,New York, 1966.
5. J. D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153,
255–260.
6. N. D. Elkies, Curves Dy 2 = x3 − x of odd analytic rank, Algorithmic number theory (Sydney,2002), Lecture Notes in Comput. Sci., vol. 2369, Springer-Verlag, Berlin, 2002, pp. 244–251.
7. P. Erdős, Remarks on number theory. I, Mat. Lapok 12 (1961), 10–17.
8. S. A. Fenner, F. Green, S. Homer, and R. Pruim, Determining acceptance possibility for aquantum computation is hard for the polynomial hierarchy, Proc. Royal Society, London (A)(1999), 3953–3966.
9. L. Fortnow, Counting complexity, Complexity Theory Retrospective II (L. Hemaspaandra and
A. Selman, eds.), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 1997, pp. 81–107.
10. C. F. Gauss, Disquisitiones Arithmeticae, Springer-Verlag, New York, 1986.
11. L. K. Hua, Introduction to Number Theory, Springer-Verlag, Berlin, 1982.
12. K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, second ed.,
Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990.
13. N. Koblitz, Introduction to Elliptic Curves and Modular Forms, Graduate Texts in Mathematics, vol. 97, Springer-Verlag, New York, 1984.
14. M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge
University Press, Cambridge, 2000.
15. J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc.
76 (1974), 521–528.
16. C. Pomerance, The quadratic sieve factoring algorithm, Advances in cryptology (Paris, 1984),
Lecture Notes in Comput. Sci., vol. 209, Springer-Verlag, Berlin, 1985, pp. 169–182.
17. S. Rudich and A. Wigderson, Computational Complexity Theory, American MathematicalSociety, Providence, 2004.
18. R. J. Schoof, Quadratic fields and factorization, Computational methods in number theory,
Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 235–286.
19. D. Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), Utilitas Math., 1973, pp. 51–70. Congressus
Numerantium, No. VII.
20. V. Shoup, NTL: A library for doing number theory, Available from the author’s home pageat New York University.
21. J. H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, New York, 1986.
22. N. P. Smart, The Algorithmic Resolution of Diophantine Equations, Cambridge U. Press,
New York, 1998.
23. M. Tompa, Probabilistic factoring algorithms can be made errorless, Technical Report 83-0901, Univ Washington, Dept. of Computer Science, 1983.
24. J. B. Tunnell, A classical Diophantine problem and modular forms of weight 3/2, Invent.
Math. 72 (1983), no. 2, 323–334.
25. K. Wagner, The complexity of combinatorial problems with succinct input representation,
Acta Inform. 23 (1986), 325–356.
Computer Sciences Department, University of Wisconsin, 1210 W. Dayton St., Madison, WI 53706-1685
E-mail address: bach@cs.wisc.edu
UCLA Department of Mathematics, Box 951555, Los Angeles, CA 90095-1555
E-mail address: nathan@math.ucla.edu