Future directions in algorithmic number theory

The American Institute of Mathematics

This is a hard–copy version of a web page available through http://www.aimath.org

Input on this material is welcomed and can be sent to workshops@aimath.org Version: Wed Apr 30 11:57:16 2003

This document is an outcome of the ARCC workshop “Future directions in algorithmic number theory,” held at AIM in Palo Alto, March 24-28, 2003.

Table of Contents

A. Lecture Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Agrawal: Primality Testing

2. Agrawal: Finding Quadratic Nonresidues

3. Bernstein: Proving Primality After Agrawal-Kayal-Saxena 4. Edixhoven: Point Counting

5. Gao: Factoring Polynomials under GRH

6. Kedlaya: Counting Points using p-adic Cohomology

7. Lauder: Counting Points over Finite Fields

8. Lenstra: Primality Testing with Pseudofields

9. Pomerance and Bleichenbacher: Constructing Finite Fields 10. Silverberg: Applications of Algebraic Tori to Crytography

11. Stein: Modular Forms Database

12. Voloch: Multiplicative Subgroups of a Finite Field

13. Wan: Partial Counting of Rational Points over Finite Fields B. Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1. Remarks on Agrawal’s Conjecture

Chapter A: Lecture Notes

Lecture notes were TeXed in real time by John Voight.

A.1 Agrawal: A Polynomial Time Algorithm for Testing Primality

The primality testing algorithm we present is based upon the following identity: n is prime if and only if

(1 + X)^{n} ≡ 1 + X^{n} (mod n),

where we consider this congruence as an identity in the polynomial ring (ℤ/nℤ)[X]. This easily gives a randomized algorithm which runs in polynomial time: rather than verifying it completely (which would be far too expensive), you verify it modulo a randomly chosen degree log n polynomial Q(X); repeating this sufficiently often, you expect to witness a failure of this congruence to hold fairly quickly if n is composite.

Conjecture. To prove that n is prime, it is enough to let Q(X) run over the set

{X − 1, X^{2} − 1, …, X^{log^{2} n} − 1}.

We were unable to prove this conjecture, but, instead the modified conjecture, which is then a proposition:

Proposition (Modified conjecture). To prove that n is prime, it is enough to let Q(X) run over the set

R = {(X + a)^{r} − 1 : 1 ≤ r ≤ 16(log n)^{5}, 1 ≤ a ≤ 8(log n)^{7/2}},

except when n has a ‘small’ prime factor (≤ (log n)^{5}).

Remark. One can replace the assumption that n does not have a small prime factor by adding to the list the polynomials X^{k}.

For a fixed r, this gives only that n is a prime power, which is a condition readily checked.

We now prove the modified conjecture.

If n is prime, clearly all of these conditions will hold.

Assume that n is composite and does not have a ‘small’ prime factor. Assume that

(1 + X)^{n} ≡ 1 + X^{n} (mod n, Q(X))

for every Q(X) ∈ R. First, observe that n is not a prime power. This follows as

(1 + X)^{n} ≡ 1 + X^{n} (mod n, (X + 1)^{r} − 1)

so substituting X for X + 1 everywhere we get

(X − 1)^{n} ≡ X^{n} − 1 (mod n, X^{r} − 1)

and substituting X^{k} for X we get

(X^{k} − 1)^{n} ≡ X^{nk} − 1 (mod n, X^{r} − 1)

hence

∏_{k<r}(X^{k} − 1)^{n} ≡ ∏_{k<r}(X^{kn} − 1)

so r^{n} ≡ r (mod n) for all r ≤ 16(log n)^{5}.

Suppose p^{2} | n for p a prime. Then r^{n−1} ≡ 1 (mod p^{2}) (n does not have a small prime divisor) so r^{gcd(n−1,p(p−1))} ≡ 1 (mod p^{2}) as the group is cyclic. Therefore r^{p−1} ≡ 1 (mod p^{2}) for all r ≤ 16(log n)^{5}. A simple counting argument (look at all of the possible numbers whose prime divisors are all smaller than (log n)^{2}, the identity holds for them but there are more than p of them) shows that this cannot happen.

Assume that n is composite but not a prime power. Let p | n, p prime, and fix r. Now:

Claim. We have

(1 + X)^{n} ≡ 1 + X^{n} (mod n, (X + a)^{r} − 1)

for 1 ≤ a ≤ 8(log n)^{7/2} if and only if

(X − a)^{n} ≡ X^{n} − a (mod n, X^{r} − 1)

for 1 ≤ a ≤ 8(log n)^{7/2}.

This can be seen by replacing X by X − a as appropriate.

Definition. A number m is introspective for g(X) if

g(X)^{m} ≡ g(X^{m}) (mod p, x^{r} − 1).

Both n and p are introspective for X − a, 1 ≤ a ≤ 8(log n)^{7/2}. Indeed, a prime p is trivially introspective for every polynomial.

Observe that if m_{1} and m_{2} are introspective for g(X), then so is m_{1}m_{2}. This is clear as

g(X)^{m_{1}m_{2}} ≡ g(X^{m_{1}})^{m_{2}} ≡ g(X^{m_{1}m_{2}}) (mod p, X^{r} − 1).

Secondly, observe trivially that if m is introspective for g_{1}(X) and g_{2}(X), then it is for g_{1}(X)g_{2}(X).

Now let I = {n^{i}p^{j} : i, j ≥ 0} and

T = {∏_{1≤a≤8(log n)^{7/2}}(X − a)^{e_{a}} : e_{a} ≥ 0} .

Observe that every m ∈ I is introspective for every g(X) ∈ T.

Let t be the order of the group generated by n and p in (ℤ/rℤ)^{∗}. There are > t elements in I less than or equal to n^{2\sqrt{t}}.

Furthermore, there are > n^{2\sqrt{t}} distinct polynomials of degree < t which are distinct modulo p and h(X), where h(X) is an irreducible factor of the rth cyclotomic polynomial in 𝔽_{p}. We show this as follows.

The number of polynomials in T of degree < t is at least 2^{min{t,8(log n)^{7/2}}} by simply considering products of distinct linear factors in T. Assume that t > 4(log n)^{2} and t < 16(log n)^{5}. (We will come back to this: we can choose the value of r to obtain it.) Then

n^{2\sqrt{t}} = 2^{2\sqrt{t} log n} < 2^{t}

and

n^{2\sqrt{t}} < n^{8(log n)^{5/2}} = 2^{8(log n)^{7/2}}.

Let F = 𝔽_{p}[X]/(h(X)), and let g_{1}(X), g_{2}(X) be of degree < t in T and g_{1}(X) ≠ g_{2}(X). Suppose g_{1}(X) = g_{2}(X) (mod p, h(X)). Then

g_{1}(X^{m}) ≡ g_{1}(X)^{m} ≡ g_{2}(X)^{m} ≡ g_{2}(X^{m}) (mod p, h(X))

for all m ∈ I. Therefore X^{m} is a root in F of the polynomial g_{1}(Y) − g_{2}(Y). This is a contradiction, as each of the elements X^{m} are distinct (they are roots of unity in the field) for the t representatives of the group generated by n and p, but the degree of g_{1}(Y) − g_{2}(Y) is < t.

Let m_{1} ≡ m_{2} (mod r), m_{1} ≠ m_{2} ∈ I and m_{1}, m_{2} ≤ n^{2\sqrt{t}}; this is possible as t is the order of the group generated by n and p in ℤ/rℤ. Let g(X) ∈ T be of degree < t. Then

g(X)^{m_{1}} ≡ g(X^{m_{1}}) ≡ g(X^{m_{2}}) ≡ g(X)^{m_{2}} (mod p, h(X))

so g(X) (mod h(X), p) is a root in F of the polynomial Y^{m_{1}} −Y^{m_{2}}. Since g was an arbitrary element of T, each g(X) is a root of this polynomial with degree ≤ n^{2\sqrt{t}} but there are more than n^{2\sqrt{t}} of them, contradiction.

Finally, we show that t > 4(log n)^{2} and t < 16(log n)^{5}. Suppose the order of n is ≤ 4(log n)^{2} in (ℤ/rℤ)^{∗}. Then r | ∏_{d≤4(log n)^{2}}(n^{d} − 1) < 2^{16(log n)^{5}}. Now use the fact that the least common multiple of the first k numbers is at least 2^{k}.

It is easy to see that this algorithm has runtime (log n)^{10.5}.

A.2 Agrawal: Finding Quadratic Nonresidues

Let p − 1 = 2^{ℓ}s, s odd. To find a quadratic non-residue, compute continuously −1, (−1)^{1/2}, (−1)^{1/4}, …, (−1)^{1/2^{ℓ−1}}. One can quickly compute (−1)^{1/2} from an algorithm due to Schoof, but one gets stuck at (−1)^{1/8}.

The idea: in primality testing, we want to know if ℤ/nℤ is a field, so we embed it into (ℤ/nℤ)[X]/(X^{r} − 1); this ring has enough structure to pull out a nice algorithm. Assume that ℓ ≥ 2, and we try only to compute \sqrt{−1}. Now we embed in 𝔽_{p}[X]/(X^{2} + 1). Consider g(X) = (1 − X)^{s}. Observe that (g(X))^{2^{ℓ}} = 1 in 𝔽_{p}[X]/(X^{2} + 1), so g(X) is a 2^{ℓ}th root of unity.

Assume that ℓ = 2. In this case, g(X) is a fourth root of unity. But X is also a fourth root, so g(X) = X^{k} (mod X − ω) where ω is the ‘real’ fourth root of unity. Consider g(X) mod (X^{2} + 1): observe that g(X) ≠ X^{k} (mod X^{2} + 1) for any k. For suppose

(1 − X)^{s} ≡ X^{k} (mod X^{2} + 1);

then

(1 − 1/X)^{s} = 1/X^{k} (mod 1/X^{2} + 1),

so

(1 − X)^{s} = −(X^{s}/X^{k}) (mod X^{2} + 1),

hence −(X^{s}/X^{k}) = X^{k} (mod X^{2} + 1), a contradiction because s is odd. So compute gcd(g(X) − X^{k}, X^{2} + 1), for each k, one of them will factor X^{2} + 1.

If ℓ > 2, then you cannot argue g(X) ≡ X^{k} (mod X − ω). If ℓ > 2, then it is possible that g(X) is an eighth root or a sixteenth root or so on. Suppose that g(X) modulo X^{2} + 1 is an eighth root, for example. Then g(X^{2}) = (1 − X^{2})^{s} ≡ X^{k} (mod X − ζ) for some factor X − ζ of X^{4} + 1 and k odd. But (1 − X^{2})^{s} is even, so it cannot be an odd power, so gcd((1 − X^{2})^{s} − X^{k}, X^{4} + 1) will give either a linear factor (in which case we are done) or a product of quadratic factors (X − ζ^{2})(X + ζ^{2}) or the products similar to (X − ζ)(X − ζ^{3}) and (X − ζ)(X + ζ^{3}).

Let h(X) be a quadratic factor of X^{4} + 1. Now if (1 − X)^{s} ≢ X^{k} (mod h(X)), then

h(X) can be factored and we are done. Suppose

(1 − X)^{s} ≡ X^{k} (mod (X − ζ)(X − ζ^{3}))

and

(1 − X)^{s} ≡ X^{k′} (mod (X + ζ)(X + ζ^{3})).

If you replace X by X^{3}, then you get

(1 − X^{3})^{s} = X^{3k} (mod (X^{3} − ζ)(X^{3} − ζ^{3}))

so

(1 − X^{3})^{s} ≡ X^{3k} = (1 − X)^{3s} (mod (X − ζ)(X − ζ^{3})).

That means that 3 is introspective for (1 − X)^{s}. The same argument applies to the other congruence, so one obtains that 3 is introspective for (1 − X)^{s} mod X^{4} + 1.

Now try all over again now with X − a replacing 1 − X; the bad case will be when we have 3 is introspective for (a − X)^{s} mod X^{4} + 1 for a large number of a. Here we get stuck, but this should be impossible.

Remarks.

A. There was a solution due to Lehmer which says for any fixed ℓ that you can solve this problem? (Cohen) But that assumes the existence of a nonresidue to begin with, which is exactly our problem. (Bernstein) But also this doesn’t seem to scale well. (Cohen) There is a strategy to deal with this, and we always work modulo a degree four polynomial. (Agrawal)

B. The fact that s > 1 means that the same techniques as in the primality test do not seem to apply. Can you solve the problem if s = 3, or for other small s? (Lenstra) The case of a Fermat prime is trivial (3 is a nonresidue, and there probably aren’t any above 65537). (Lenstra, Elkies) It seems as though if s is bounded, there are only a finite number of problematic a. For example, (a − X^{3})^{s} ≡ (a − X)^{3} (mod h(X)) does not hold for ‘many’ a (Pomerance).

C. One strategy to solve this problem: translate this problem into rings and stare at it. (Lenstra) D. Is there a strategy to deal with cases beyond eighth roots (where we have the special situation

that every odd integer has square 1)? (Elkies) Yes, but we need to solve this problem first. (Agrawal)

E. How many values of a do you need? (Voloch) It seems unlikely you can generate the whole group with the (X − a)^{s} without the GRH. (Bernstein)

A.3 Bernstein: Proving Primality After Agrawal-Kayal-Saxena

The lecture notes are available on the speaker’s website: the talk (and more)^{1}, related problems^{2}, older paper on AKS^{3}, and putting AKS into context^{4}.

1http://cr.yp.to/papers.html#quartic

2http://cr.yp.to/papers.html#abccong

3http://cr.yp.to/papers.html#aks

4http://cr.yp.to/primetests.html

A.4 Edixhoven: About Point Counting over Arbitrary Finite Fields

Consider a system of equations f_{1}(x_{1}, …, x_{n}) = 0, …, f_{m}(x_{1}, …, x_{n}) = 0 given by polynomials f_{i} ∈ 𝔽_{q}[x_{1}, …, x_{n}]. This is not essentially different than the case of a single hypersurface (every variety is birational to a hypersurface, or, also, one can use the inclusionexclusion principle). We let q = p^{r}.

Question. For fixed n, is there an algorithm that computes the number of solutions in 𝔽_{q} in time polynomial in the quantities: log q (or r and log p), d = max_{i} deg f_{i}, and m?

If you fix p, and m = 1, then the answer is yes (Lauder-Wan) using p-adic methods. We discuss the case where p is not fixed. If p is not fixed, then one knows that the answer is yes for elliptic curves (Schoof) using ℓ-torsion points and curves of a given genus via the ℓ-torsion of their jacobian (Pila).

Conceptually, all methods use Lefschetz fixed points formula:

#X(𝔽_{q}) = ∑_{i=0}^{2 dim X}(−1)^{i} Tr(Frob_{q} |H_{c}^{i}(X))

where we denote H_{c}^{i}(X) cohomology with compact support. This is true for X a scheme of finite type which is separated over 𝔽_{q}. For these cohomology groups, one can take a padic approach using a de Rham-type cohomology, lifting X to a p-adic ring R and take the hypercohomology of the de Rham sequence, quite explicit and computable but the complexity is worse than linear in p. Instead, one can also use mod ℓ methods (ℓ ≠ p); here one takes the groups H_{c}^{i}(X_{\overline{𝔽_{q}},et}, 𝔽_{ℓ}) which is a lot less explicit. The H^{i} derive from injective resolutions on the etale topology. In this setup, there is the advantage that you can choose ℓ. For an elliptic curve, one has

E(\overline{𝔽_{q}})[ℓ]^{∨} = H^{1}(E_{\overline{𝔽_{q}},et}, 𝔽_{ℓ}).

What is the simplest interesting case where we want to but cannot yet compute an H^{i} with i ≥ 2? We think of surfaces, or modular forms of weight ≥ 3 (to generalize the case of elliptic curves, which correspond to eigenforms of weight 2). We assume that there is a cohomology group of dimension ≥ 2 (if it is of dimension 1, Frobenius acts as a power of the cyclotomic character).

We consider as an example the modular form Δ = q ∏_{n≥1}(1 − q^{n})^{24} = ∑_{n≥1} τ(n)q^{n} is an eigenform of weight 12, viewed as a function on the upper half-plane. Then Δ(dq/q)^{⊗6} is an SL_{2}(ℤ)-invariant on ℌ, so it descends to ℌ/SL_{2}(ℤ). The variety we work with is the ten-fold product of the universal elliptic curve E; we find that H^{11}(E^{10}) has dimension 2. For all p, and ℓ ≠ p, τ(p) mod ℓ is the trace of Frob_{p} on H^{11}(E_{\overline{𝔽_{p}},et}^{10}, 𝔽_{ℓ}), which is also the trace of Frob_{p} on H^{11}(E_{\overline{ℚ},et}^{10}, 𝔽_{ℓ}) with Gal(\overline{ℚ}/ℚ) acting on it: it is the two-dimensional Galois representation (modulo ℓ) associated to Δ. The action factors through Gal(K_{Δ,ℓ}/ℚ) acting faithfully where K_{Δ,ℓ}/ℚ is a finite extension.

Compute explicitly the extension K_{Δ,ℓ}. One gets as a byproduct a computation of the actual representation, which we cannot easily compute now. A bit of work yields that K_{Δ,ℓ} is the Galois closure of the field definition of a suitable element x ∈ J_{1}(ℓ)(\overline{ℚ})[ℓ], where J_{1}(ℓ) is the jacobian of X_{1}(ℓ), if X_{1}(ℓ)(C) = ℌ/Γ_{1}(ℓ) together with te cusps, and Γ_{1}(ℓ) is the set of

matrices (\begin{matrix}a & b \\ c & d \end{matrix}) with a ≡ 1 (mod ℓ), c ≡ 0 (mod ℓ). Still: need to compute this efficiently.

This is not so easy because the genus g of X_{1}(ℓ) is quadratic in ℓ.

We have the following strategy for finding ℚ(x) (based a suggestion of Jean-Marc Couveignes). We have a surjection

X_{1}(ℓ)(ℂ)^{g} → J_{1}(ℓ)(ℂ) = ℂ^{g}/Λ

where Λ = H_{1}(X_{1}(ℓ)(ℂ), ℤ). We have ℂ^{g}/Λ ⊃ (1/ℓ)Λ/Λ ∋ x. (For r prime, T_{r} · x = τ(r) · x.) This map on complex points is given by (Q_{1}, …, Q_{g}) ∈ X_{1}(ℓ)(ℂ) maps to the point [Q_{1} + ⋯ + Q_{g} − gP_{0}] = ∑_{i=1}^{g} ∫_{P_{0}}^{Q_{i}}(ω_{1}, …, ω_{g}) ∈ ℂ^{g}/Λ. Here, for P_{0} one can choose a ℚ-rational cusp.

Generically, there is a unique point (Q_{1}, …, Q_{g}) up to permutation which gives the point x, namely, α = ∑_{i} j(Q_{i}) ∈ ℚ(x). Now one estimates the height of α, approximates α in ℂ by lifting (numerically) the straight line path from 0 to x (possible because the map X_{1}(ℓ)^{g} → J_{1}(ℓ) is generically unramified). It will probably be a good idea to replace the divisor gP_{0} by a sum of g distinct points P_{1}, …, P_{g}, with small height, defined over a small and solvable extension of ℚ. As x and the P_{i} determine the Q_{i} (up to permutation), and as x is a torsion point (Néron-Tate height zero) one expects that the height of α is not much bigger than that of the P_{i}. So one hopes that the required number of correct digits of the approximation of α grows polynomially in ℓ. The tool to be used for estimating the height of α is Arakelov geometry. A good indication that this proposed strategy works is that the height estimate works well in the function field case (a nice application of the Grothendieck-Riemann-Roch theorem).

A.5 Gao: Factoring Polynomials under GRH

We consider the following problem: Given a prime p and f ∈ 𝔽_{p}[x], where deg f = n, f is separable, and f splits completely, find a proper factor of f (in deterministic polynomial time).

Berlekamp algorithm reduces general polynomials in 𝔽_{q}[x] (q a power of p) to polynomials of the above type. Without GRH, we are stuck already at x^{2} − a. So throughout we assume GRH.

Ronyai (1988) shows that this can be done in time (n^{n} log p)^{O(1)}, or more precisely (n^{r} log p)^{O(1)} whenever r | n, r > 1, so in particular if n is even f can be split in deterministic polynomial time. Bach, von zur Gathen and Lenstra (2001) give an algorithm with polynomial time if ϕ_{k}(p) is smooth for some k where ϕ_{k}(x) is the kth cyclotomic polynomial. Evdokimov (1994) shows for any n and p, f can be factored in time (n^{log n} log p)^{O(1)}. We discuss work in Cheng and Huang (2000), and Gao (2001) plus some unpublished results. GRH will be needed only to compute an rth nonresidue in 𝔽_{p} or in its extensions, for 1 ≤ r ≤ n.

Definition. An algebra R/𝔽_{p} is called elementary if R ≅ (𝔽_{p})^{⨁ m} for some m.

Let R be elementary over 𝔽_{p}. Then we write R = 𝔽_{p}ϵ_{1} + ⋯ + 𝔽_{p}ϵ_{m} where the ϵ_{i} are primitive idempotents, which are unique in R.

Fact. A. If f, g ∈ R[x], then gcd(f, g) can be defined properly and can be computed in deterministic

polynomial time for any elementary algebra R. B. If f ∈ R[x] is monic, separable (i.e. (f, f′) = (1)), and f splits completely, then R_{1} =

R[x]/(f(x)) is also elementary. Given a zerodivisor in R_{1}, one can compute a proper factor of f or a zerodivisor of R.

C. Given a nontrivial ring endomorphism of R_{1} over R, one can find a proper factor of f or a

zerodivisor of R. (Need GRH to get an rth nonresidue, for 1 ≤ r ≤ n, where n = deg f.) D. Given a quadratic nonresidue in 𝔽_{p}, there is a deterministic polynomial time algorithm for

computing square roots in R. More precisely we have a function σ : R → R, such that (i) σ(A) is a square root of A if A is a square in R, (ii) if A = ∑_{i=1}^{m} a_{i}ϵ_{i} ∈ R, a_{i} ∈ 𝔽_{p}, then

σ(A) = ∑_{i=1}^{m} σ(a_{i})ϵ_{i},

and (iii) for a ∈ 𝔽_{p}, σ(a^{2}) = ±a. For example, if p ≡ 3 (mod 4), then we can take σ(A) = A^{(p+1)/4}, and for a ∈ 𝔽_{p},

σ(a^{2}) = \begin{cases}a, & if a is a square, \\ −a, & otherwise. \end{cases}

Now let f ∈ 𝔽_{p}[x] be separable, so that

f = ∏_{i=1}^{n}(x − a_{i}), a_{i} ∈ 𝔽_{p}.

To factor f, define

R_{2} = 𝔽_{p}[z_{1}, z_{2}]/(f(z_{1}), f(z_{2})),

which is the tensor product of 𝔽_{p}[z]/(f(z)) with itself. Then R_{2} is an elementary algebra. In the following, we will identity z_{1} and z_{2} with their images in R_{2}. Let

ϵ_{i} = \frac{∏_{j≠i}(z_{1} − a_{j})}{∏_{j≠i}(a_{i} − a_{j})}, 1 ≤ i ≤ n,

and

η_{i} = \frac{∏_{j≠i}(z_{2} − a_{j})}{∏_{j≠i}(a_{i} − a_{j})}, 1 ≤ i ≤ n.

Then ϵ_{i}η_{j}, 1 ≤ i, j ≤ n, are all the primitive idempotents of R_{2}. They have the following properties:

∑_{i=1}^{n} ϵ_{i} = 1, ∑_{j=1}^{n} η_{j} = 1,

and

z_{1} = a_{1}ϵ_{1} + ⋯ + a_{n}ϵ_{n} = ∑_{i,j} a_{i}ϵ_{i}η_{j},
z_{2} = a_{1}η_{1} + ⋯ + a_{n}η_{n} = ∑_{i,j} a_{j}ϵ_{i}η_{j}.

Let

A = \frac{1}{2}(z_{1} + z_{2} + σ((z_{1} − z_{2})^{2}) ∈ R_{2},

which can be computed in deterministic polynomial time. Then

A = ∑_{i,j} \frac{1}{2}(a_{i} + a_{j} + σ((a_{i} − a_{j})^{2})ϵ_{i}η_{j}

where

\frac{1}{2}(a_{i} + a_{j} + σ((a_{i} − a_{j})^{2})) = \begin{cases}a_{i}, & if σ((a_{i} − a_{j})^{2}) = a_{i} − a_{j} \\ a_{j}, & if σ((a_{i} − a_{j})^{2}) = a_{j} − a_{i}. \end{cases}

Hence A encodes information about the “squareness” of the differences of the roots of f. By using characteristic polynomials and gcd technique, one can extract the factors of f. Definition. For 1 ≤ i ≤ n, define

Δ_{i} = {1 ≤ j ≤ n : j ≠ i, σ((a_{i} − a_{j})^{2}) = −(a_{i} − a_{j})}.

Theorem. We can always find a proper factor of f in 𝔽_{p}[x] except when

#Δ_{i} = (n − 1)/2, 1 ≤ i ≤ n,  (1)

and in this exception case f can be factored over 𝔽_{p}[z_{1}] as

f(x) = (x − z_{1})f_{0}f_{1}

where

f_{0} = ∑_{i=1}^{n} ∏_{j∈Δ_{i}}(x − a_{j})ϵ_{i}, f_{1} = ∑_{i=1}^{n} ∏_{j∉Δ_{i},j≠i}(x − a_{j})ϵ_{i}.

To further factor f_{0} over R_{1} = 𝔽_{p}[z_{1}]/(f(z_{1})), we compute in the ring
R_{3} = R_{1}[z_{2}, z_{3}]/(f_{0}(z_{2}), f_{0}(z_{3})),

and similarly for f_{1}. Theorem. We can always split f_{0} or f_{1} except when

#(Δ_{i} ∩ Δ_{j}) = (n − 3)/4, 1 ≤ i < j ≤ n,  (2)

and in this exception case, f_{0} is factored over R_{1}[z_{2}]/(f_{0}(z_{2})) as

f_{0}(x) = (x − z_{2})f_{00}f_{01}

where f_{00}, f_{01} ∈ R_{1}[z_{2}][x] both of degree (n − 3)/4; similarly over the ring R_{1}[z_{2}]/(f_{1}(z_{2})),

f_{1}(x) = (x − z_{2})f_{10}f_{11}. A system of subsets satisfying (1) and (2) is called an Hadamard design. When n ≡

3 mod 4 is a prime, there is always an Hadamard design.

To further split f_{00}, let R_{2} = R_{1}[z_{2}]/(f_{0}(z_{2})), and we compute in the ring

R_{4} = R_{2}[z_{3}, z_{4}]/(f_{00}(z_{3}), f_{00}(z_{4})).

Similarly for f_{01}, f_{10}, and f_{11}. Theorem. We can always split f_{00}, f_{01}, f_{10}, or f_{11} except when

#(Δ_{i} ∩ Δ_{j} ∩ Δ_{k}) = (n − 7)/8, 1 ≤ i < j < k ≤ n.  (3)

It can be proved, however, that (3) is impossible. It remains open how to explore this information to obtain a proper factor of f in 𝔽_{p}[x]!

A.6 Kedlaya: Counting Points using p-adic Cohomology

We introduce a different p-adic setup for counting points (or equivalently computing zeta functions). If X is a variety over 𝔽_{q}, we want to count points using ‘de Rham’ cohomology. We will demonstrate Monsky-Washnitzer cohomology (a kind of rigid cohomology for smooth affine varieties). We restrict to the case where X is an affine curve, since in higher dimensions other methods will be faster. Then X = Spec 𝔽_{q}[t_{1}, …, t_{n}]/(f_{1}, …, f_{m}).

Let W = W (𝔽_{q}) be the Witt vectors, and let K = W [1/p] be the fraction field of W. Define

W ⟨t_{1}, …, t_{n}⟩^{†} = {∑_{I}c_{I}t^{I} : I = (i_{1}, …, i_{n}) ∈ ℤ_{≥0}^{n}, c_{I} ∈ W,
convergent for t_{i} ∈ \overline{K}, |t_{i}| ≤ 1 + ϵ for some ϵ > 0\} .

In other words, v_{p}(c_{I}) ≥ rϵ_{I} − c for some r, c with r > 0. Modulo p, W ⟨t_{1}, …, t_{n}⟩^{†} reduces to the polynomial ring 𝔽_{q}[t_{1}, …, t_{n}], since all but finitely many coefficients are divisible by p. We define K⟨t_{1}, …, t_{n}⟩^{†} = W ⟨t_{1}, …, t_{n}⟩^{†}[1/p]. Let

A^{int} = W ⟨t̃_{1}, …, t̃_{n}⟩^{†}/(f̃_{1}, …, f̃_{n})

where f̃_{i} is a lift of f_{i}. Then

A^{int}[1/p] = K⟨t̃_{1}, …, t̃_{n}⟩^{†}/(f̃_{1}, …, f̃_{n}).

There exists a lift so that A^{int} is flat over W.

Let Ω_{A}^{1} be the A-module generated by symbols dt_{1}, …, dt_{n} modulo the submodule generated by df̃_{1}, …, df̃_{m}. Then there is a K-linear derivation d : A → Ω_{A}^{1}. Letting Ω_{A}^{i} = ⋀_{A}^{i} Ω_{A}^{i}; you get the de Rham complex

A = Ω_{A}^{0} ⟶^{d} Ω_{A}^{1} ⟶^{d} …

and you ‘define’

H_{MW}^{i} (X) = \frac{ker(Ω_{A}^{i} → Ω_{A}^{i+1})}{img(Ω_{A}^{i−1} → Ω_{A}^{i})}.

It turns out that H_{MW}^{q} (X) is independent of choices (A is unique up to noncanonical isomorphism, funny automorphisms are homotopic to the identity) and given X → Y, there is a map A_{Y} → A_{X} and the induced maps H_{MW}^{i} (Y) → H_{MW}^{i} (X) also do not depend on choices.

The spaces H^{i}(X) are finite-dimensional, but it is not obvious; it relies upon relating this cohomology to rigid cohomology for proper varieties, namely, crystalline cohomology which we know is finite-dimensional for other reasons. Moreover, they satisfy the Lefschetz trace formula: if F : X → X is the q-power Frobenius, then (Monsky)

#X(𝔽_{q^{i}}) = ∑_{j}(−1)^{j} Tr((qF^{−1})^{i}|H^{j}(X)).

The idea: try to compute H^{i}(X) and the map induced by F (find A^{int} → A^{int} lifting q-power Frobenius).

Example. Look at X = Spec 𝔽_{q}[x, y, z]/(y^{2} − f(x), yz − 1) with char 𝔽_{q} = p odd. Let deg f = 2g + 1, f monic. Lift it to A = K⟨x, y, z⟩^{†}/(y^{2} − P (x), yz − 1), where P (x) is monic, degree 2g + 1 over W. It is easy to compute that H^{0}(X) is one-dimensional. Now H^{1}(X) is generated by x^{i} dx/y for i = 0, …, 2g −1, and x^{i} dx/y^{2}, i = 0, …, 2g. Note H^{1}(X) splits under y ↦ −y into plus and minus eigenspaces.

You need to find relations in H^{1}(X) that d(x^{i}/y^{j}) = 0. (This is a special situation: all relations are ‘algebraic’.) Lift the p-power Frobenius by W → W by the Witt vector Frobenius, x ↦ x^{p}, and y ↦ y^{p}\sqrt{F (P (x))/P (X)^{p}}. Compose this map with itself n times to get a q-power Frobenius lift, and this allows us to compute the zeta function of a genus g hyperelliptic curve over 𝔽_{p^{n}} in time Õ(g^{4}n^{3}p).

A.7 Lauder: Counting Solutions to Equations in Many Variables over Finite Fields

We present an algorithm which allows us to count solutions to a homogeneous equation f(X_{1}, …, X_{n}) ∈ 𝔽_{q}[X_{1}, …, X_{n}] of degree d (for simplicity we assume d ≥ 2, n ≥ 2) with running time which does not increase exponentially in number of variables. In other words, we are interested in computing the number of projective solutions

N_{k} = #{(x_{1} : ⋯: x_{n}) ∈ ℙ_{𝔽_{q^{k}}}^{n−1} : f(x_{1}, …, x_{n}) = 0}

for every k ≥ 1. We encode these numbers in the generating function

Z(f, T) = exp(∑_{k}N_{k}T^{k}/k) ∈ ℚ[[T]]

which, by a theorem of Dwork, is in fact a rational function. We assume that f is nonsingular, i.e. f and ∂f/∂x_{i} for i = 1, …, n have no common projective solution. In this situation, we know that

Z(f, T) = \frac{P (T)^{(−1)^{n+1}}}{(1 − T)(1 − qT) … (1 − q^{n−2}T)}

where deg P = (1/d)((d − 1)^{n} + (−1)^{n}(d − 1)).

If we compute N_{k} naively for k = 1, …, deg P then we can of course recover the polynomial P (T); the time required to do this, however, requires (q^{deg P})^{n} ≈ 2^{d^{n−1} log q} evaluations of f. The input is given by \binom{d+n−1}{n−1} ≤ d^{n−1} terms of size log q, and the output size is approximately (d^{n−1} log q)^{O(1)}. We would like the running time to be polynomial in this quantity.

If n = 2, we are counting solutions of a univariate polynomial, and this can be done in time (d log q)^{O(1)}. For n = 3, we have an algorithm of Schoof-Pila for curves which has run time (log q)^{Δ} where Δ depends on d exponentially. In general, there is an algorithm (due to L. and Wan) which runs in time (pd^{n} log q)^{O(n)}. Notice the n in the exponent—we would like to lose this dependence.

The new result: If f is ‘sufficiently generic’ (we exclude a Zariski closed set which is efficiently computable), p ≠ 2, and p ∤ d, then we can find P (T) using (pd^{n} log q))^{O(1)} bit operations. As a corollary, we see that if f ∈ ℤ[X_{1}, …, X_{n}] is sufficiently generic, then there exists an algorithm which takes as input a prime p, outputs the number of solutions f mod p = 0, and has run time O(p^{2+ϵ}).

Recall that P (T) = det(I − T Frob_{q} |H^{n−2}(X)), where we write X for the projective variety defined by the equation f = 0. The action of Frob_{q} can be represented by a matrix with entries in a field of characteristic zero, and we find that

N_{k} = (−1)^{n} Tr(Frob_{q}^{k} |H^{n−2}(X)) + 1 + q^{k} + ⋯ + (q^{k})^{n−2}.

For curves, for example, the dimension is n − 2 = 1, and H^{1}(X) is a ℤ_{ℓ}-module, for ℓ ≠ p.

Instead, we work with the p-adic theory, where H^{n−2}(X) is a R-module for a ring R ⊃ ℤ_{p}. We compute instead Frob_{q} = Frob_{p}^{log_{p}(q)}, and compute the matrix of Frob_{p} |H^{n−2}(X). (Specifically, R = ℚ_{q}(π) where ℚ_{q} is the unramified extension of ℚ_{p} of degree log_{p} q and π^{p−1} = −p. Also our H^{n−2}(X) is actually the primitive part of the cohomology space.) Consider the family

f_{Y} = ∑_{i=1}^{n} a_{i}X_{i}^{d} + Y h(X_{1}, …, X_{n}),

and assume that a_{1} … a_{n} ≠ 0. Then f_{1} = f and f_{0} is a diagonal form, for which it is easy to count the number of solutions. Now Frob_{p}(Y) is a p-adic analytic function with the property that Frob_{p}(Y) evaluated at a Teichmuller lift of y^{1/p} is exactly the Frob_{p} associated to f_{y}.

We see that Frob_{p}(Y) = C(Y^{p})^{−1} Frob_{p}(0)C^{τ−1}(Y) where τ mod p : α ↦ α^{p}, and C(Y) is a matrix of power series around the origin satisfying the differential equation dC/dY = C(Y)B(Y) with initial condition C(0) = I, where B(Y) is easily computed. This gives a way to compute Frob_{p}(Y) in a radius around the origin, and we need to extend this to the closed disc of radius 1.

The entries of the matrices are p-adic holomorphic functions, so to compute these modulo a power of p we find rational functions with denominators corresponding to the values of Y where the variety becomes singular and then recover the numerator from the power series. Using overconvergence we get a bound on the degree of these rational functions. We evaluate the rational functions at Y = 1. One gets nice complexity because we work with univariate power series, with decay in the coefficients on the order of 1/p, and one needs to take the power of p approximately on the order of d^{n} log q.

In the old algorithm, we would work in H^{n−2}(X), the ring of power series in X_{1}, …, X_{n} over an R = ℚ_{p}^{(m)}(π) where ℚ_{p}^{(m)} is the unramified extension of ℚ_{p} of degree m (if q = p^{m}) and π^{p−1} = −p modulo an infinite subspace; the power series we must work with have on the order of (pd^{n} log q)^{n} terms.

Problem. Find an algorithm which counts the number of points on a curve in time (d log q)^{O(1)}.

A.8 Lenstra: Primality Testing with Pseudofields

This is joint work with Carl Pomerance.

If f, g are real-valued functions on a set X and g > 0, then we say f = Õ(g) if there exists c ∈ ℝ_{>0} such that for all x ∈ X, |f(x)| ≤ g(x) max{2, log g(x)}^{c}.

Theorem. There is a deterministic algorithm that given n ∈ ℤ, n > 1, correctly decides whether or not n is prime and that has runtime Õ((log n)^{6}).

The theorem of AKS begins (in brief) as follows. Let n ∈ ℤ_{>1} be a positive integer, r a prime number with r ∤ n, and

(X + a)^{n} ≡ X^{n} + a (mod n, X^{r} − 1)

for a small set of a, and the multiplicative order of n modulo r is at least c(log n)^{2}. Together with other conditions, we conclude n is a prime. This has runtime Õ(r^{3/2}(log n)^{3}). For r = O((log n)^{5}), we get Õ((log n)^{21/2}) with effective constant. For an ineffective constant, one can get Õ((log n)^{15/2}). It would be optimal to have Õ((log n)^{6}), which would require r = Õ((log n)^{2}) but here we run into Artin’s conjecture on primes with prescribed primitive root. To get around this, we generalize the situation slightly to give more parameters.

In fact, we replace X^{r} −1 by (X^{r} −1)/(X −1) = X^{r−1} +⋯+X +1; the proof remains essentially unchanged. Instead of considering congruences, we instead think of equalities in the ring

A = ℤ[X]/(n, X^{r−1} + ⋯ + X + 1) ⊃ ℤ/nℤ.

This is a Galois extension of ℤ/nℤ of degree r − 1. We now replace the polynomial X^{r−1} + ⋯ + X + 1 with other polynomials f(X) for which the same proof techniques apply. In this case, A is a field if and only if n is a prime number and n is a primitive root modulo r. We are led to introduce rings that ‘try very hard’ to be fields.

Definition. A pseudofield is a pair A, α where A is a ring (commutative with 1) and α ∈ A such that there exists n ∈ ℤ_{>1} and d ∈ ℤ_{>0} satisfying:

• ℤ/nℤ is a subring of A with #A ≤ n^{d}, and there exists σ ∈ Aut A with:

– σ^{d}α = α;

– for all q | d prime, σ^{d/q}(α) − α ∈ A^{∗}; and

– σα = α^{n};

• Equivalently, A ≅ (ℤ/nℤ)[X]/(f) as a ring with X ↦ α for some monic polynomial f ∈

(ℤ/nℤ)[X] of degree d satisfying:

– f(X) | f(X^{n});

– f(X) | (X^{n^{d}} − X); and

– for all primes q | d, (f, X^{n^{d/q}} − X) = (1).

Also equivalently, a pseudofield is characterized by the conditions that A ⊃ ℤ/nℤ be Galois with cyclic group generated by σ, α generates A as a ring, and σα = α^{n}.

Theorem. There is a deterministic algorithm that given n ∈ ℤ_{>1} and f ∈ (ℤ/nℤ)[X] decides if (ℤ/nℤ)[X]/(f) is a pseudofield in time

Õ((d + log n)d log n).

It is routine to verify this using the second set of conditions.

Example. A. If r is a prime with r ∤ n, then A = (ℤ/nℤ)[X]/(X^{r−1} + ⋯ + 1) is a pseudofield if and only

if the order of n modulo r is r − 1. B. If n is prime, then A, α is a pseudofield if and only if A is a field and A = 𝔽_{n}[α]. C. If A = ℤ/nℤ (so that d = 1) and α = (a mod n), then A, α is a pseudofield if and only if

a^{n} ≡ a (mod n)—in other words, n is a pseudoprime to base a.

Theorem. Let A, α be a pseudofield of characteristic n and degree d such that d > (log n/ log 2)^{2}, n has no prime factor ≤ k = ⌊\sqrt{d}(log n/ log 2)⌋, and such that

(α + a)^{n} = a^{n} + a

for a = 1, 2, …, k (mod n). Then n is a power of a prime number.

The proof uses: for each prime p | n, there exists a unique τ ∈ ⟨σ⟩ such that for all β ∈ A, τ(β) ≡ β^{p} (mod pA). This is a result coming from Galois theory for rings.

This leads to a deterministic primality test with runtime equal to the time to construct the pseudofield plus the time to check the conditions; the latter takes time Õ(d^{3/2}(log n)^{3}).

In the context of primality testing, there is a procedure which converts any (honest) method for constructing finite fields to a method for checking primality. If the algorithm on input n crashes, then n was not prime; if it returns a polynomial f, then one checks (efficiently) if this gives rise to a pseudofield, which then verifies that n is prime, and otherwise produces a proof that n is not prime.

Therefore we look for algorithms for constructing finite fields. Our construction relies on the following theorem:

Theorem (Kummer 1846). For r prime and q | (r − 1), put

f_{q,r} = ∏_{\begin{matrix}i∈𝔽_{r} \\ i^{q}=1 \end{matrix}}(X − ∑_{j^{(r−1)/q}=i} ζ_{r}^{j}) ∈ ℤ[X]

where ζ_{r} is a primitive rth root of unity in ℂ. The polynomial f is monic and irreducible of degree q. If p is prime, p ≠ r, then (f_{q,r} mod p) ∈ 𝔽_{p}[X] is irreducible if and only if the order of p^{(r−1)/q} modulo r is equal to q.

Fact. Let A_{i}, α_{i} be a pseudofield of characteristic n and degree d_{i} > 1 for i = 1, 2 such that gcd(d_{1}, d_{2}) = 1; then A_{1} ⊗_{ℤ} A_{2}, α_{1} ⊗ α_{2} is a pseudofield of characteristic n and degree d_{1}d_{2}.

Theorem. There exists an effective computable constant c such that there is a deterministic algorithm that given n ∈ ℤ_{>1} finds a finite sequence of pairs (r_{1}, q_{1}), …, (r_{k}, q_{k}) such that:

• q_{i} > 1, q_{i} pairwise coprime;

• r_{i} prime, q_{i} | (r_{i} − 1);

• The order of n^{(r_{i}−1)/q_{i}} modulo r_{i} is q_{i}; and

• d = ∏ q_{i} satisfies

(log n/ log 2)^{2} < d < c(log n/ log 2)^{2}

and max r_{i} < d. This algorithm runs in time Õ((log n)^{24/11}), with an effective constant.

A.9 Pomerance and Bleichenbacher: Constructing Finite Fields

Consider the following problem: Given a prime p and an integer d > 1, find an irreducible polynomial f ∈ 𝔽_{p}[X] of degree d. And do so in time polynomial in d and log p. There is a randomized algorithm which attacks this problem by picking a polynomial at random (approximately 1 out of every d polynomials will be irreducible), and testing each for irreducibility (which is fast), continuing this procedure until you find one, then stop. But we are interested here in a deterministic algorithm. Already for d = 2, this is a difficult problem, equivalent to finding a quadratic nonresidue modulo p.

Assuming the ERH, Adleman and Lenstra have a solution to this problem. Unconditionally, they also find an irreducible polynomial of degree d′ with d ≤ d′ < cd log p, where c is an effectively computable number. Letting d = (log n)^{2} and n = p (where you do not know a priori if n is prime), the polynomial produced has degree O(log^{3} n), and the runtime of the AKS algorithm becomes Õ((deg f)^{3/2} log^{3} n) = Õ((log n)^{15/2}). We improve this theorem to the following:

Theorem. Such a polynomial can be produced with d ≤ d′ ≤ 4d for p sufficiently large and d ≥ (log p)^{11/6+ϵ}.

The bound for the ‘sufficiently large’ part depends effectively on the choice of ϵ.

Theorem. There is an effectively computable function N_{ϵ} and a deterministic algorithm such that if ϵ > 0, n > N_{ϵ}, and D > (log n)^{11/6+ϵ}, the algorithm produces pairs (q_{1}, r_{1}), …, (q_{k}, r_{k}) such that for each i, r_{i} is prime, r_{i} < D, q_{i} | r_{i} − 1, the order of n^{(r_{i}−1)/q_{i}} modulo r_{i} is q_{i}. Further, the q_{1}, …, q_{k} are pairwise coprime, and D ≤ ∏_{i} q_{i} ≤ 4D. This algorithm runs in time Õ_{eff}(D^{12/11}).

Let η_{i} be the Gaussian period of degree q_{i} in ℚ(ζ_{r_{i}}) (the trace of ζ_{r_{i}} into the unique subfield of degree q_{i} over ℚ). The element η = η_{1} … η_{k} has degree q_{1} … q_{k} over the rationals (by coprimality). If n is prime, and if f(x) is the minimal polynomial of η then f mod n is irreducible over 𝔽_{n}. Checking if f(X) | f(X^{n}) in (ℤ/nℤ)[X] (together with some other conditions), we see that f gives rise to a pseudofield.

Let x = D^{6/11−ϵ/4}. Throughout, we assume that n is ‘sufficiently large’ with the bound being effectively computable, depending only on the choice of ϵ.

Proposition. All but O(x/ log^{3} x) primes r ≤ x have a prime q | (r−1) with q > x^{1/(log log x)^{2}} and the order of n^{(r−1)/q} modulo r is equal to q.

Therefore up to x, almost all of the primes are useful in the context of our theorem. This proposition is a natural extension of the argument in the original AKS paper, together with an added ingredient about the distribution of primes r such that r − 1 is smooth due to Pomerance and Shperlinski.

Proposition. Let Q be a set of primes q with x^{1/(log log x)^{2}} < q ≤ x^{1/2} and ∑_{q∈Q} 1/(q − 1) < (3 − ϵ)/11. Then there are > δx/ log^{2} x primes r ≤ x such that r − 1 is free of primes from Q ∪ (x^{1/2}, x).

This proposition follows from a method of Balog, together with some effective estimates on the distribution of primes in residue classes. Together, these two propositions give the corollary:

Corollary. Let Q be the set of primes q in the first proposition satisfying q ≤ \sqrt{x}. Then

∑_{q∈Q} \frac{1}{q − 1} ≥ \frac{3 − ϵ}{11}.

Proof. If this inequality did not hold, then by the first and second propositions, there must be primes r ≤ x having the properties of both propositions. By the first proposition, r − 1 has a prime factor q > x^{1/) log log x)^{2}} and the order of n^{(r−1)/q} modulo r is equal to q. By one of the properties in the second proposition, q ≤ x^{1/2}. Then q ∈ Q. This contradicts the second proposition. □

Proposition. There exists a subset of Q in the corollary with product in the interval [D, 4D].

The proof of this theorem relies upon combinatorial number theory (essentially, you can solve a bin packing problem using the primes q). It relies upon:

Theorem (Continuous Frobenius theorem). If S is an open subset of ℝ_{>0}, S is closed under addition, and 1 ∉ S, then for any t, 0 < t ≤ 1, the du/u measure of S ∩ (0, t) is ≤ t, i.e.

∫_{0}^{t} χ_{S}(u)\frac{du}{u} ≤ t

where χ_{S}(u) is the characteristic function of S.

Now a remark about effectivity. It was proven by de la Vallée Poussin in 1896 that

π(x, k, a) = #{p ≤ x : x ≡ a (mod k)} ∼ π(x)/ϕ(k)

as x → ∞. The Siegel-Walfisz theorem states that this is true for k < (log x)^{A} for any fixed A. This theorem is inherently ineffective because it depends on the existence or nonexistence of Siegel zeros. The Siegel-Walfisz theorem is ubiquitous in analytic number theory, being used in the Bombieri-Vinogradov theorem, Fouvry’s theorem, and much else. The analytic number theory we use is an effective version of the Bombieri-Vinogradov theorem that does not rely on the Siegel-Walfisz theorem, and we replace the Fouvry theorem by a (weaker) result of Deshouillers-Iwaniec.

Now we give an outline of the proof of the Frobenius theorem. First, it is sufficient to prove the case where S_{t} = S ∩ (0, t) = ⋃_{i=1}^{n}(a_{i}, b_{i}) (i.e. S_{t} contains only finitely many intervals). Second, since 1 ∉ S, for all (h_{1}, …, h_{n}) ∈ ℕ_{≥0}^{n} either ∑_{i=1}^{n} h_{i}a_{i} ≥ 1 or ∑_{i=1}^{n} h_{i}b_{i} ≤ 1 (*). Now fix b_{1}, …, b_{n} such that b_{1} > b_{2} > ⋯ > b_{n} and consider all sets ⋃_{i=1}^{n}(a_{i}, b_{i}) satisfying b_{1} ≥ a_{1} ≥ b_{2} ≥ ⋯ ≥ b_{n} ≥ a_{n} (**) as well as condition (*). Under these conditions, there exists a maximum to ∑_{i=1}^{n}(log(b_{i})−log(a_{i})). We may thus assume that S_{t} = ⋃_{i=1}^{n}(a_{i}, b_{i}) is a maximum. We show in the paper that we can assume that b_{1} > a_{1} > b_{2} > ⋯ > b_{n} > a_{n}.

Let U = {h ∈ ℕ_{≥0}^{n} : ha = 1} with a = (a_{1}, …, a_{n}). Let a_{n+1} = b_{n+1} = 0. For all h = (h_{1}, …, h_{n}) ∈ U and 1 ≤ k ≤ n,

h_{k} (∑_{i=1}^{n}(b_{i} − a_{i})h_{i}) ≤ h_{k}(b_{k} − b_{k+1}).

This is trivial if h_{k} = 0, and otherwise, ∑_{i=1}^{n} a_{i}h_{i} = 1 which implies

∑_{i=1}^{n} a_{i}h_{i} − a_{k} + a_{k+1} < 1.

and therefore by assumption (*)

∑_{i=1}^{n} b_{i}h_{i} − b_{k} + b_{k+1} ≤ 1.

Let v = (v_{1}, …, v_{n}) ∈ ℝ^{n} such that vh ≥ 0 for all h ∈ U. Then there exists ϵ > 0 such that for all 0 ≤ x ≤ ϵ,

⋃_{i=1}^{n}(a_{i} + v_{i}x, b_{i})

satisfies (*) and (**). By assumption

∑_{i=1}^{n}(log b_{i} − log(a_{i} + v_{i}x))

is maximal for x = 0, so ∑_{i=1}^{n} v_{i}/a_{i} ≥ 0. Then a theorem by Farkas (or the dual theorem of linear programming) implies that there exists p_{j} ≥ 0 such that

∑_{i=1}^{ℓ} h_{ij}p_{j} = \frac{1}{a_{i}}

where U = {h_{1}, …, h_{ℓ}} and h_{j} = (h_{1j}, …, h_{nj}). Now multiply the equation

h_{k} (∑_{i=1}^{n}(b_{i} − a_{i})h_{i}) ≤ h_{k}(b_{k} − b_{k+1}).

by a_{k}p_{j} and sum up

∑_{k=1}^{n} ∑_{j=1}^{ℓ} a_{k}p_{j}h_{kj} (∑_{i=1}^{n}(b_{i} − a_{i})h_{ij}) ≤ ∑_{k=1}^{n} ∑_{j=1}^{ℓ} a_{k}p_{j}h_{kj}(b_{k} − b_{k+1}).

After some simple arithmetic, we find that

∑_{i=1}^{n}(log b_{i} − log a_{i}) ≤ t.

A.10 Silverberg: Applications of Algebraic Tori to Crytography

In this lecture we discuss ‘torus-based cryptography’, and counterexamples to conjectures in an article entitled Looking Beyond XTR, and compare TBC with Lucas-based cryptosystems and XTR, and understand LUC, XTR, and Beyond in terms of algebraic tori. This is joint work with Karl Rubin, and inspired by XTR.

The cryptosystem XTR (due to A. Lenstra and E. Verheul) concerns the extension 𝔽_{p^{6}}/𝔽_{p^{2}}: they consider the subgroup of 𝔽_{p^{6}}^{∗} of order p^{2} − p + 1 with generator g; the public knowledge is Tr_{𝔽_{p^{6}}/𝔽_{p^{2}}}(g), what is shared is Tr_{𝔽_{p^{6}}/𝔽_{p^{2}}}(g^{ab}), where Tr(g^{a}) and Tr(g^{b}) are transmitted. In this setup, you get the security of 𝔽_{p^{n}}^{∗} while transmitting only ϕ(n) elements of 𝔽_{p}.

Let L/k be a finite cyclic extension with intermediate field F. Let g ∈ L \ F, and denote by C_{g} the Gal(L/F)-conjugacy class of g, so the characteristic polynomial of g over F is ∏_{h∈C_{g}}(X − h). For L = 𝔽_{p^{6}}, F = 𝔽_{p^{2}}, k = 𝔽_{p}, the polynomial is x^{3} − s_{1}x^{2} + s_{2}x − s_{3}, where s_{1} = Tr_{L/F} (g), s_{3} = N_{L/F} (g), and s_{2} = Tr_{L/F} (gg^{σ}), where ⟨σ⟩ = Gal(L/F). If g is in the subgroup of L^{∗} of order p^{2} − p + 1, then s_{3} = 1 and s_{2} = Tr_{L/F} (g)^{p}. Therefore knowing Tr_{L/F} (g) is equivalent to knowing all the symmetric polynomials on C_{g} which is equivalent to knowing C_{g} as a set, so you know C_{g^{a}} and this is equivalent to knowing Tr_{L/F} (g^{a}). In other words, you can exponentiate, but you cannot multiply: Tr(g) and Tr(h) do not determine Tr(gh); i.e. knowing C_{g} and C_{h} does not allow you to know C_{gh}.

Bosma-Hutton-Verheul conjecture that for all n, there exists a divisor d | n such that d | ϕ(n) and for L = 𝔽_{p^{n}} and F = 𝔽_{p^{d}}, you can recover all the coefficients s_{1}, …, s_{n/d} of the characteristic polynomial of g over F from the first ϕ(n)/d of them for all g in the subgroup of L^{∗} of order Φ_{n}(p) and not in any proper subfield.

We show that this is in fact false. In particular, when n = 30, it is false; for p = 7, d = 1, no 10 symmetric polynomials determine all of them, and no 8 determine any of the others (except the ones determined by the symmetry of the characteristic polynomial). For p = 7, d = 2, no 4 symmetric polynomials determine all of them.

Fact. The order Φ_{n}(p) subgroup of 𝔽_{p^{n}}^{∗} is

{α ∈ 𝔽_{p^{n}}^{∗} : N_{𝔽_{p^{n}}/M}(α) = 1 for all M ⊊ 𝔽_{p^{n}}}.

Let L/k be an abelian degree n extension of fields. Let

T_{L/k} = ker (Res_{L/k}(𝔾_{m}) ⟶^{⊕N_{L/M}} ⨁_{k⊂M⊊L}Res_{M/k}(𝔾_{m}));

recall that 𝔾_{m}(k) = k^{∗}, and (Res_{L/k} 𝔾_{m})(k) = L^{∗}. If L/k is not cyclic, dim(T_{L/k}) = 0. If L/k is cyclic, then T_{L/k} is an algebraic torus over k of dimension ϕ(n), i.e. T_{L/k} is isomorphic over \overline{k} to 𝔾_{m}^{ϕ(n)}. Here, T_{L/k} ≅_{L} 𝔾_{m}^{ϕ(n)}.

Assume from now on that L/k is cyclic. Then

T_{L/k}(k) = {α ∈ L^{∗} : N_{L/M}(α) = 1 for all k ⊂ M ⊊ L}.

Conjecture (Voskresenskii). T_{L/k} is rational, i.e. there exists a birational map T_{L/k} → 𝔸^{ϕ(n)}.

This is true if n = p^{a} or p^{a}q^{b} (Klyachko 1988). It is not known for n = pqr. Let us look at the case when n = 2, say, char k ≠ 2. Then L = k(\sqrt{d}), and T_{L/k} = ker(N_{L/k}) which is a conic which can be parameterized, and we obtain

ψ : ℙ^{1} ⟶^{∼} T_{L/k}
a ↦ (a + \sqrt{d})/(a − \sqrt{d})
∞ ↦ 1

We have ψ(a)ψ(b) = ψ((ab + d)/(a + b)). (This is also just Hilbert’s theorem 90.) Writing T_{n} for T_{L/k} when k = 𝔽_{q}, this induces a way to do the multiplication in T_{2} in ℙ^{1}(k).

We also give an explicit example when n = 6 for char(k) ≠ 3, [k(ζ_{9}) : k] = 6 (e.g. k = 𝔽_{q} with q ≡ 2, 5 (mod 9)). T_{L/k} is dimension 2 and contained in Res_{M/k}(T_{L/M}) = T′ ∼_{k} 𝔸^{3} where M/k is the subextension of degree 3. But T_{L/M} = ker(N_{L/M}) is dimension 1, and N_{L/F} = 1 defines a hypersurface in T′ ∼ 𝔸^{3}. Therefore T_{6} ∼ 𝔸_{2}, so we can use the multiplication in T_{6} but represent elements of T_{6} by 2 elements of 𝔽_{8}. This gives rise to the cryptosystem CEILIDH.

Open problems:

A. Improve the efficiency of multiplication and exponentiation for the system CEILIDH. B. Repeat this analysis for n = 30, i.e.

1. Find explicit birational isomorphisms between T_{30} and 𝔸^{8},

2. Find prime powers q of size 1024/30 ≈ 35 bits such that Φ_{30}(q) has a 160-bit prime factor,

3. Are there special attacks on DL in 𝔽_{q^{30}}^{∗}?

Now we look to understand LUC, XTR, and Beyond in terms of algebraic tori. For H a subgroup of Gal(L/k) = G which is a direct factor, write Σ_{H} for the group of permutations of H. Then Σ_{H} acts on

⨁_{σ∈G}𝔸^{1} ⟶^{∼}_{L} Res_{L/k} 𝔸^{1} ⊃ Res_{L/k}(𝔾_{m}).

Let

X_{F} = img (T_{L/k} → Res_{L/k}(𝔾_{m})/Σ_{Gal(L/F)}) .

For LUC and XTR, you look at

{Tr_{L/F} (α) : α ∈ T_{L/k}(k)}

which is the image of T_{L/k}(k) under T_{L/k} → X_{F} → Res_{F/k}(𝔸^{1}), where the latter map is a birational isomorphism.

\xymatrix{T_{L/k} \ar@{->>}[d] \ar[drr]^{_{Tr_{L/F}}} \\ X_{F} \ar[r]^{_{Tr_{L/F}}} & Res_{F/k}(𝔸^{1}) \ar[r]^{∼} & F}

Assume that n is squarefree. Write Gal(L/F) = H_{1} × ⋯ × H_{t} where H_{i} are cyclic of prime order. Theorem. The action of Σ_{H_{i}} on Res_{L/k}(𝔾_{m}) preserves T_{L/k} and X_{F} is birational to T_{L/k}/(Σ_{H_{1}}× ⋯ × Σ_{H_{t}}).

In XTR, we obtain X_{F} birational to T_{6}/S_{3}; in the cases n = 30 and d = 1, 2, one gets T_{30}/(S_{2} × S_{3} × S_{5}), T_{30}/(S_{3} × S_{5}), which are not groups.

We have maps L → F for every symmetric function s_{1}, …, s_{[L:F]}. We have a surjection T_{L/k} → X_{F} and an injection X_{F} ↪ F^{[L:F]} by the direct sum of these functions. A BHV conjecture implies that for the subset consisting of the first ⌈ϕ(n)/d⌉ functions (where d = [F : k]), the map remains injective. Further, a BHF conjecture implies that every n has a divisor d so that d also divides ϕ(n), and the map X_{F} → 𝔸^{ϕ(n)} (induced by the first ϕ(n)/d symmetric functions) is a birational isomorphism. This is true for (n, d) = (1, 1) (DH), (2, 1) (LUC), (6, 2) (XTR), and (ℓ, 1) and (2ℓ, 2) where ℓ is prime (see Doing more with fewer bits, by Brouwer-Pellikaan-Verheul), but: Theorem. This is false for n = 30 (d = 1, 2) if char(k) lies outside a finite set.

To prove this, we first do a computer search for 2 elements of T_{30}(𝔽_{7}) with the same image a ∈ (𝔽_{7})^{8} but different images in X_{F}. Using Hensel’s Lemma, every lift of a to ℤ_{7}^{8} has at least 2 inverse images in X_{F} (ℚ_{7}). Therefore the map is not generically one-to-one over ℚ_{7}, so it is not generically one-to-one over ℚ, hence over any field of characteristic 0. Then reduce modulo p to get it over 𝔽_{p} and therefore all fields of characteristic p (outside of a finite set).

A.11 Stein: Modular Forms Database

The lecture notes^{5} are available on the speaker’s website. The tables^{6} are also available there.

5http://modular.fas.harvard.edu/mfd/talks/mfd1/

6http://modular.fas.harvard.edu/Tables/

A.12 Voloch: Multiplicative Subgroups of a Finite Field

The lecture notes^{7} are available on the speaker’s website.

A.13 Wan: Partial Counting of Rational Points over Finite Fields

We are motivated by the following problem. Let 𝔽_{q^{d}} = 𝔽_{q}[α]/h(α), where h is irreducible of degree d > 1 over 𝔽_{q}. We look at the group

G = ⟨a − α : a ∈ 𝔽_{q}⟩ = (𝔽_{q^{d}}^{∗})^{I} ⊂ 𝔽_{q^{d}}^{∗},

where I = [𝔽_{q^{d}}^{∗} : G]. When does I = 1, for example?

Let D | (q^{d} − 1), and let

N = #{(x, y) : x − α = y^{D}, x ∈ 𝔽_{q}, y ∈ 𝔽_{q^{d}}}.

By a character sum argument counting, you can write this as

N = ∑_{\begin{matrix}ϕ:𝔽_{q^{d}}^{∗}→ℂ^{∗} \\ ϕ^{D}=1 \end{matrix}} ∑_{x∈𝔽_{q}} ϕ(x − α).

By the Riemann hypothesis (Weil), we have |N − q| ≤ (D − 1)(d − 1)\sqrt{q}. Therefore we have seen:

Proposition. Let S ⊂ 𝔽_{q}. Let G_{S} = ⟨a − α : a ∈ S⟩ = (𝔽_{q^{d}}^{∗})^{I_{S}}. Then

(#S)I_{S} ≤ N ≤ q + (I_{S} − 1)(d − 1)\sqrt{q}.

If (#S) > (d − 1)\sqrt{q}, then

I_{S} ≤ \frac{q − (d − 1)\sqrt{q}}{(#S) − (d − 1)\sqrt{q}} .

In particular, if (#S) = q, then I_{S} = 1 and G = 𝔽_{q^{d}}^{∗}.

Therefore we consider the problem: Can we compute N in time polynomial in d, D, and log q?

The general setup: Let f(x_{1}, …, x_{n}) ∈ \overline{𝔽_{q}}[x_{1}, …, x_{n}], and d_{1}, …, d_{n} ≥ 1. We want to count

N_{d_{1},...,d_{n}}(f) = #{(x_{1}, …, x_{n}) : f(x_{1}, …, x_{n}) = 0, x_{i} ∈ 𝔽_{q}^{d_{i}}}.

Can we compute N_{d_{1},...,d_{n}}(f), or at least estimate it? How does this quantity vary when the d_{i} vary?

For example, we consider the Artin-Schreier hypersurface. Let

f(x_{1}, …, x_{n}, y_{1}, …, y_{n′}) ∈ 𝔽_{q}[x_{1}, …, x_{n}, y_{1}, …, y_{n′}],

where n, n′ ≥ 1. For each d ≥ 1, we consider

N_{d}(f) = #{(x_{0}, …, x_{n}, y_{1}, …, y_{n′}) : x_{0}^{p} − x_{0} = f(x_{1}, …, x_{n}, y_{1}, …, y_{n′}),
x_{i} ∈ 𝔽_{q^{d}}, y_{j} ∈ 𝔽_{q}}.

Heuristically (for suitable f), we expect

N_{d}(f) = q^{dn+n′} + O(q^{(dn+n′)/2})

where the constant depends on p, f, and d.

7http://www.ma.utexas.edu/users/voloch/preprint.html

Theorem (Deligne). Write f = f_{m} + f_{m−1} + ⋯ + f_{0}, where f_{i} are homogeneous of degree i. Assume f_{m} defines a smooth projective hypersurface in ℙ_{𝔽_{q}}^{n+n′−1}, and that p ∤ m, d = 1. Then

|N_{1}(f) − q^{n+n′}| ≤ (p − 1)(m − 1)^{n+n′}q^{(n+n′)/2}.

What about d > 1? Definition. If d ≥ 1, we define the dth fibred sum of f to be

⨁_{y}^{d}f = f(x_{11}, …, x_{1n}, y_{1}, …, y_{n′}) + ⋯ + f(x_{d1}, …, x_{dn}, y_{1}, …, y_{n′}).

Theorem (Fu-W). Write f = f_{m} + ⋯ + f_{0}, and assume that ⨁_{y}^{d} f_{m} is smooth in ℙ_{𝔽_{q}}^{dn+n′−1} and p ∤ m. Then

|N_{d}(f) − q^{dn+n′}| ≤ (p − 1)(m − 1)^{dn+n′}q^{(dn+n′)/2}.

Example. In the case that we can write

f(x, y) = f_{1m}(x_{1}, …, x_{n}) + f_{2m}(y_{1}, …, y_{n′}) + f_{≤m−1}(x, y),

and f_{1m} is smooth in ℙ_{𝔽_{q}}^{n−1}, f_{2m} is smooth in ℙ_{𝔽_{q}}^{n′−1}. Then ⨁_{y}^{d} f_{m} is smooth in ℙ_{𝔽_{q}}^{dn+n′−1} if and only if p ∤ d.

Since the condition that the fibred sum be smooth is Zariski open, we have shown it is nonempty if p ∤ d and therefore there exist many examples of such f to which the theorem applies. Definition. Let M_{d} be the set of f over \overline{𝔽_{q}} such that ⨁_{y}^{d} f_{m} is smooth. Then M_{d} is Zariski open in the set of all f over \overline{𝔽_{q}} with deg f ≤ m. Theorem (Gao-W). M_{d} is Zariski dense if and only if p ∤ d. In fact,

⋂_{\begin{matrix}d=1 \\ p∤d \end{matrix}}^{∞}M_{d} = ⋂_{\begin{matrix}d=1 \\ p∤d \end{matrix}}^{p^{(m−1)^{n}}} M_{d}

and this intersection is Zariski open and dense. Problem. What about Kummer hypersurfaces

x_{0}^{D} = f(x_{1}, …, x_{n}, y_{1}, …, y′_{n})

where x_{i} ∈ 𝔽_{q^{d}} and y_{j} ∈ 𝔽_{q}? Remark. We expect |N_{d} − q^{dn+n′}| = O(q^{(dn+n′)/2}), but one can get the weaker estimate O(q^{dn/2+n′−1/2}) in many cases (Katz).

Now we consider partial zeta functions over 𝔽_{q}. Let f(x_{1}, …, x_{n}) ∈ 𝔽_{q}[x_{1}, …, x_{n}], d_{1}, …, d_{n} ≥ 1. Define

Z_{d_{1},...,d_{n}}(f, T) = exp (∑_{k=1}^{∞} N_{d_{1},...,d_{n},k} \frac{T^{k}}{k} )

where

N_{d_{1},...,d_{n},k} = #{(x_{1}, …, x_{n}) : f(x_{1}, …, x_{n}) = 0, x_{i} ∈ 𝔽_{q^{d_{i}k}}}.

Without loss of generality, we may assume gcd(d_{1}, …, d_{n}) = 1, since otherwise we can just enlarge the ground field 𝔽_{q}.

Proposition. A. If d_{1} | ⋯ | d_{n}, then Z_{d_{1},...,d_{n}}(f, T) ∈ ℚ(T). B. (Faltings) Z_{d_{1},...,d_{n}}(f, T) = ∏_{i=1}^{d} P_{i}(T)^{ζ_{d}^{i}}, where d = lcm(d_{1}, …, d_{n}) and ζ_{d} is a primitive dth

root of unity, P_{i}(T) ∈ \overline{ℚ}(T), and P_{i}(0) = 1.

By exponentiation to a root of unity, we mean the formal binomial expansion. From a counting point of view, this is ‘as good as rational’.

Theorem. In all cases, Z_{d_{1},...,d_{n}}(f, T) ∈ ℚ(T).

Proof. Let X^{d} = \underbrace{X × ⋯ × X}_{d}. We have a map

σ : X^{d} → X^{d}
(x^{(1)}, …, x^{(d)}) ↦ (x^{(d)}, x^{(1)}, …, x^{(d−1)})

Faltings constructs a large subvariety Y_{d_{1},...,d_{n}} ↪ X^{d} which is stable under σ. Then

N_{d_{1},...,d_{n}}(f) = #Fix(σ ∘ Frob_{q} |Y (\overline{𝔽_{q}})) = ∑(−1)^{i} Tr(σ ∘ Frob |H_{c}^{i}(\overline{Y})).

Note σ ∘ Frob_{q} = Frob_{q} ∘σ. This implies Faltings’ ‘near’ rationality as in the proposition.

Now Z_{d_{1},...,d_{n}}(f, T) ∈ 1 + T ℚ[[T]]. We refine the above argument as follows. First, for gcd(a, d) = 1, you have

N_{d_{1},...,d_{n}}(f) = # Fix(σ^{a} ∘ Frob_{q} |Y (\overline{𝔽_{q}})).

We consider Y → Y/G, where G = ⟨σ⟩ ≅ ℤ/dℤ. We have a character χ : G → ℂ^{∗}, and define the L-function

L(χ, T) = exp (∑_{k=1}^{∞} \frac{T^{k}}{k} (\frac{1}{d} ∑_{τ∈G} χ(τ^{−1})# Fix(τ ∘ Frob_{q}^{k} |Y (\overline{𝔽_{q}})))) .

By Grothendieck, L(χ, T) ∈ ℚ(ζ_{d})(T). This implies that

Z_{d_{1},...,d_{n}}(f, T)^{ϕ(d)} = ∏_{χ∈Ĝ} L(χ, T)^{∑_{gcd(a,d)=1} χ(σ)^{a}} ∈ ℚ(ζ_{d})(T)

so Z_{d_{1},...,d_{n}}(f, T) ∈ ℚ(T) (essentially by unique factorization). □

Open problem: can you bound the total degree of Z_{d_{1},...,d_{n}}(f, T)? The best bound we have is 3 · 2^{d+1}(3 + dm)^{d_{1}+···+d_{n}+1}, m = deg f. Can this be improved to O(d)^{O(1)}? Yes, if d_{1} = ⋯ = d_{r} = d and d_{r+1} = ⋯ = d_{n} = 1 (Fu-W).

Chapter B: Problems

Problem/Question 1. If

(X − 1)^{n} ≡ X^{n} − 1 (mod n, X^{r} − 1)

and gcd(r, n) = 1 does this imply that

n^{2} ≡ 1 (mod r)

when n is composite? (AKS)

Remarks.

(i) In the simplest case, r = 5 and n ≡ 2 (mod 5), what do the heuristics say? This feels like the traditional series of pseudoprime tests, and although they were first thought to be sufficient, counterexamples exist. (Bernstein) It was thought that the old pseudoprime tests 2^{n} ≡ 2 (mod n) combined with the quadratic test with least discriminant d with the Jacobi symbol (d/n) = −1 (constructing a Lucas sequence of discriminant d) would be enough to show that n is prime. There should be infinitely many composite numbers which pass both of these tests. There is no known example, and there is a $620 prize to find an example of a number that pass the various tests. (Pomerance) There are no heuristic reasons yet to believe this. (AKS)

(ii) For r ≥ 5, there are 5000 pairs (n, r) that all satisfy these conditions. (AKS) (iii) The most naive heuristic (looking at 2 as a random element modulo n) for the first claim

relies upon the fact that ∑ 1/n diverges, whereas in this case we are looking at ∑ 1/n^{r} which converges. (Lenstra) These heuristics need to take into account smoothness. (Bernstein)

(iv) Is there a reason why n^{2} ≡ 1 (mod r) comes into the play? For all counterexamples with

r ≥ 7, p | n implies p^{2} ≡ 1 (mod r). (Lenstra, AKS)

(v) In these conditions we see that r^{n} ≡ r (mod n). (Lenstra) So if p | n, the numbers p − 1, p+1, p^{2} +1 must be very smooth (for r = 5). The heuristics show that there should be ‘lots’ of primes p satisfying these three numbers; create many n from these p, and as in the case of Carmichael numbers, then perhaps for some n this should fail. (Pomerance) If p − 1 is smooth for all p | n and n is squarefree, then the multiplicative group of n has smooth order. The maximal order of any element in that group can be made small, so it would not be unusual for n^{2} ≡ 1 (mod r). Much of this can be found in Grantham’s thesis. (Pomerance)

(vi) These heuristics are compatible with the AKS primality test because there we have r growing

with n. (Bernstein) (vii) What about r ≫ (log log n)^{2}? The largest r found was 97, and for r ≥ 13 we found only

approximately 40 such elements. (AKS) (viii) Are prime powers special? (Lenstra) For r ≥ 5, all n found were squarefree. (AKS) The

search was done for n ≤ 10^{11}, r < 100.

Problem/Question 2. Consider 𝔽_{p} and d ∈ ℤ_{>0}, and S ⊂ 𝔽_{p} with #S = d. Let h(X) ∈ 𝔽_{p}[X] with h(s) ≠ 0 for all s ∈ S. Let G be the group generated by X − s for s ∈ S. In the original AKS paper, we have #G ≥ 2^{d}. There are techniques for getting #G ≥ (5.82)^{d} (using lattice point counting); there seems to be much more room for improvement (perhaps using ABC). (Bernstein, Voloch) Perhaps

(log #G)/d → ∞

as d → ∞ uniformly over h.

Remarks.

(i) It is hard to find examples with #G smaller than p^{d}. Every improvement speeds up by a constant factor the AKS by a factor related to square of the base of the improvement. (Bernstein)

(ii) Does it help to know if S is an interval? (Voloch, Lenstra) Not used thus far. (iii) For Kummer extensions, the extensions will look like multiplicative cosets of a root of unity

times a single number—can this be used? (Bernstein) (iv) Is this problem independent of h? (Cohen) For example, h(X) = X^{d}−1 with group generated

by X has small order. (Bernstein)

(v) Instead of looking at 𝔽_{p}[X]/(h), look at an elliptic curve E over 𝔽_{q} and the subgroup of E(𝔽_{q}) generated by simple x coordinates. (Elkies) Using Weil restriction of scalars, you are looking at a curve C inside of an abelian variety over 𝔽_{p} and look at the subgroup of points generated by C(𝔽_{p}). This is then amenable to class field theory techniques. (Voloch) The interesting case is the analogous case with AKS: q = p^{d} and #S = d, dim A = d.

Problem/Question 3. Find a deterministic polynomial time algorithm for recognizing perfect numbers. (Lenstra)

Given two monic polynomials f, g ∈ ℤ[X] with no common irreducible factor, and two integers n, m ∈ ℤ_{>0}, find in polynomial time all x ∈ ℤ such that f(x) | m and g(x) | n, with |x| < H(f, g, m, n) for some function H.

Remarks.

(i) The first problem would be more interesting than perfect numbers themselves. You are given the numbers m, n in binary. (Lenstra) A solution to the second problem gives a solution to the first: If x is prime and x^{k} ∥ n, and n is perfect, then 1 + x + ⋯ + x^{k} | 2n.

(ii) There is one solution for very small H which is to just try out the necessary values of x. (iii) There are some results on when m | f(x), which has typographical similarity to our problem.

(Coppersmith) (iv) If n is a perfect number, there is only one choice of x^{k} where the factor 2 is irrelevant;

therefore you are reduced to the case where m = n. (Pomerance)

(v) By Gary Miller’s thesis, if you are given a multiple of ϕ(n), you can factor n using a randomized algorithm or deterministically under the GRH. (Pomerance) You can replace ϕ(n) by σ(n). (Lenstra)

(vi) If you allow randomization, the first problem should be doable. (Lenstra) There is a paper

of Bach-Shallit. (vii) This algorithm will recognize perfect numbers but it may not recognize imperfect numbers.

(Lenstra) (viii) There is a more general notion (multiply perfect) where σ(n)/n = k has small height. Does

this affect the problem? (Elkies) No, because you try out each k one at a time, and for fixed k this is virtually identical to the original problem.

(ix) A different problem is to just consider f = g, or to look at rational functions which are

integer-valued.

(x) Are there heuristics for the number of such x which are related to heuristics for the largest prime divisor of f(x)? (Pomerance)

(xi) Look at f(x) = (x^{4} + x^{5} + ⋯ + x^{8}) | n. Choose h ∈ ℝ and g ≈ e^{\sqrt{8 log n log h}}. Then you can find the set of all x with |x| ≤ h such that gcd(f(x), n) > g. This can be done ‘reasonably fast’. (Bernstein) This is the state of the art due to LLL, but it completely fails to solve the problem.

Problem/Question 4. These questions are motivated by the questions posed by AKS concerning finding quadratic nonresidues modulo a prime p.

(a) It is known that finding a single quadratic nonresidue for a given prime is polynomially equivalent to solving all quadratic equations. How far can one do this for finding a single bit of data (or few bits of data) for higher degrees? (Elkies)

(b) We do not know yet that there is a deterministic polynomial time algorithm for finding quadratic nonresidues. Is there a subexponential algorithm?

Remarks.

(i) The best known deterministic algorithm is due to Burgess and Vinogradov which runs in time p^{1/(4\sqrt{e})}. (Pomerance) This is sheer enumeration. If you allow exponential time, is there something better than enumeration? (Bernstein)

(ii) For cubic extensions, you can use Cardano’s formula. (Gao) Is it equivalent to finding a quadratic nonresidue in the cubic extension given by a cubic nonresidue? (Elkies) If cubics includes quadratics, then you can make a quadratic extension. Then there is a trick due to Berlekamp which allows you to solve cubics in the extension by solving them in the ground field. (Lenstra)

(iii) If you know a kth nonresidue in the appropriate extension, then you can factor polynomials up to degree six (unpublished). (Gao) The Galois group is cyclic, so solvability by radicals applies.

(iv) Given a quadratic nonresidue, any even degree polynomial f with f | (X^{p} − X) can be split nontrivially deterministically in polynomial time, due to Ronyai. (Lenstra) But this does not determine all solutions. You can specify quadratic conditions that must be satisfied by the factors. (Gao) There is a certain combinatorial structure on systems of roots which must be attended to, and you run into difficulties at degree 7. Conjecturally, you should be able to go higher.

(v) If you have GRH then you can deterministically in polynomial time solve quadratic extensions. Can you solve higher degree equations? (Elkies) On the GRH, you can construct appropriate nonresidues (since you can construct finite fields). (Lenstra) You can do it for fixed degree in time n^{log n}(log p)^{O(1)} with the GRH due to Ronyai, Evdokimov. (Cheng)

Problem/Question 5. Suppose that you have a nonconstant family of elliptic curves E_{λ} over 𝔽_{p} (e.g. the Frey curves), λ ∈ ℙ^{1}(𝔽_{p}). Can you find deterministically λ such that E_{λ} and E_{λ+1} are not isogenous (i.e. #E_{λ}(𝔽_{p}) ≠ #E_{λ+1}(𝔽_{p})). (Elkies)

Remarks.

(i) You want p sufficiently large and the degree small. (Elkies) If you can do this, then you should also be able to do it for λ and 1 − λ, and then you can ‘separate them apart’ by applying Schoof’s algorithm and obtain a deterministic square root.

(ii) Over ℚ, there are only finitely many isogeny classes, so you just need to check that λ is not

a root of a finite list of polynomial equations. (Elkies) (iii) Can you deterministically find λ, μ such that E_{λ}, E_{μ} are not isogeneous? (Coppersmith)

What happens to Schoof’s algorithm if you just run it with λ a variable? (Lenstra) (iv) There are bounds p^{1/2+ϵ} on the number of isogeny classes (Hasse interval) over 𝔽_{p}.

(v) You can also ask the question for the family of all elliptic curves over 𝔽_{p}, deterministically. (Pomerance) This you can do by looking at if −1 and −2 are both squares. (Elkies)

Problem/Question 6. Let f(X, Y) ∈ 𝔽_{q}[X, Y] be irreducible. Let g(Y) = f(aY + b, Y). Count (or estimate) the number of pairs a, b over 𝔽_{q} such that g is irreducible over 𝔽_{q}. (Gao)

Remarks.

(i) Is it > 0 when q > d^{4}, where d is the total degree of f? (Gao) Or perhaps some other bound on q?

(ii) It is equivalent to count the number of reducible ones, so use the Schoof-Pila algorithm.

(Elkies) But it is slightly different because you are counting points on a surface. (iii) The polynomial f(X, Y) = X^{q} − X + Y is always divisible by Y under such a substitution.

(Lenstra) Therefore we need q > d. (iv) Do you need to assume that f is irreducible over \overline{𝔽_{q}}? (Pomerance)

(v) What does Hilbert’s irreducibility theorem say in this case? (Lenstra) (vi) Applying the Chebotarev density theorem, this number is rq^{2} + O(q^{3/2}), where r ∈ ℚ_{≥0}.

(Wan) How big is the constant? (vii) View g as a polynomial in 3 variables, Y, a, b. The surface g = 0 is a cover of the affine

plane given by the variables a, b. What is the Galois group of this cover (over 𝔽_{q}(a, b))? Is it possibly the full symmetric group? (Lenstra) Then r(#G) is equal to the number of elements in the Galois group that are a full d-cycle. Note this extension is separable whenever f is irreducible. (Edixhoven)

(viii) If r = 0 then all elements of the set are reducible, since any one irreducible element will have Frobenius which is a full d cycle. (Lenstra)

Problem/Question 7. Let m ≥ n ∈ ℤ. Prove there is a polynomial g ∈ 𝔽_{q}[x] of degree ≤ 2 log n so that x^{m} + g(x) has an irreducible factor of degree n. (Gao)

Remarks.

(i) If q is large compared to fixed m, n, this seems provable. (Gao) (ii) For q = 2, there is an application to computing discrete logs in 𝔽_{2^{n}}^{∗}. (Coppersmith) (iii) If m is the smallest power of q which is ≥ n, then α is a root of the irreducible factor, then

the order of α is at least ≥ n^{(log n)/(log log n)}, so this group has large order. (Gao) (iv) For all q, and m = n, it is proven if deg g ≤ n/2.

(v) Consider the variant where instead of restricting the degree consider restricting the number of nonzero terms of x^{m} + g(x) to a fixed number (such as 7) (Bernstein), or at least ≤ 2 log n (Pomerance).

(vi) Alternatively, find a trinomial of degree m ≤ 2n over 𝔽_{q} with a primitive irreducible factor

of degree n. (Gao) For small q this may not be possible. (vii) For fixed n, q, what is the sparsest polynomial of degree ≤ 2n with a primitive and irre-

ducible factor of degree n? (Pomerance) This should be uniform in q, surely 5 but perhaps 7. (Bernstein) Trivially, sparsity n works by taking an irreducible polynomial of degree n (excluding (n, q) = (2, 2)). (Lenstra) Sparsity (1 − ϵ)n should be possible. (Wan)

Problem/Question 8. Look at ∑ n^{ρ} over the zeros ρ of the Riemann zeta function with the imaginary part of ρ the interval [T, 2T]. This is ≈ T/(2π)Λ(n). Can you make a primality test out of this? (Conrey)

The sum ∑ n^{ρ}ζ′(ρ)/ζ′′(ρ) ≈ T/(2π) log p log q if n = pq. Can you make a factoring algorithm out of this?

Problem/Question 9. Compute the zeta function of Spec ℤ/nℤ, namely

ζ(s) = ∏_{p|n} \frac{1}{1 − p^{−s}} ,

without knowing the prime factorization of n. Computing the special value s = 1 gives you ϕ(n) which is enough to factor n. (Wan)

Replace n by a polynomial f(x) ∈ 𝔽_{p}[x], so given

ζ(s) = ∏_{g|f g monic,irreducible} \frac{1}{1 − g}

can you recover the factorization of f in 𝔽_{q}[x] in deterministic polynomial time? (Wan)

Remarks.

(i) Can you compute the latter using Drinfeld modules? (Lenstra) Take A = 𝔽_{p}[x]/(f). Define an 𝔽_{p}-linear map T : A → A where T (α) = α^{p} − xα which defines the Carlitz module, and makes A into an 𝔽_{p}[T]-module. If you write f = ∏_{g} g_{i}^{e_{i}}, and define ϕ(f) = ∏_{i} g_{i}^{e_{i}−1}(g_{i} − 1), then ϕ(f)(T) kills A. But also f ∏_{i}(g_{i} − 1) also kills A. Mimic the factorization of integers using upper bounds on ϕ(n) to factor f probabilistically using this ‘exponent’ of the multiplicative group.

Problem/Question 10. To speed up the elliptic curve factorization algorithm, pick E/ℚ with large torsion group so that its reduction modulo n is more likely to be smooth. Mazur’s results show that this torsion subgroup can be no larger than 16. There is a result of Kamienny-Mazur-Merel: there is a bound on #E(K)_{tors} in terms of [K : ℚ]. So try to find a number field K where p splits completely and such that E(K)_{tors} large. (Pomerance)

Remarks.

(i) Whatever advantage you gain might be swamped by the expense of working in the larger number field. (Pomerance)

(ii) One problem is that for any given number field, there are only finitely many curves over that

number field with a fixed torsion subgroup (since then modular curves have genus ≥ 2). (iii) If n = p^{2}q, choose a discriminant D such that D is a nonsquare modulo q, and find an elliptic

curve E/ℚ(\sqrt{D}). Then E(ℚ(\sqrt{D}))_{tors} injects into E(𝔽_{q^{2}}). (Bleichenbacher)

Problem/Question 11. Given a (random) number n of 10000 digits, it may be impossible to find 5000 digit primes p, q such that n = pq. Much easier: find some 10000 digit primes p, q such that n is the first 10000 digits of pq. Instead, find 7500 digit primes p, q such that n is the first 10000 digits of pq. (Coppersmith) Therefore, do this for 6000 digit primes. (Bernstein)

Remarks.

(i) Coppersmith’s algorithm works as follows. Pick at random p_{0} of 7500 digits. Pick q_{0} = ⌊(n/p_{0})10^{5000}⌋. Add x to p_{0} and y to q_{0} where x, y have 2500 digits a piece to fix this up. We want

(p_{0} + x)(q_{0} + y) = p_{0}q_{0} + p_{0}y + q_{0}x + xy ≈ n10^{5000}

so use lattice reduction. At the end, check to make sure p_{0} and q_{0} are prime. (ii) This has applications in cryptography. (Bernstein)

Problem/Question 12. Let p be prime, write p − 1 = 2^{ℓ}m where m is odd, and assume ℓ ≥ 3. Find in deterministic polynomial time x ∈ 𝔽_{p} such that x^{2^{ℓ−1}} + 1 is not a 2^{ℓ−1}th power. (Kedlaya)

Remarks.

(i) This should be a sufficient condition for the deterministic nonresidue algorithm of Agrawal to work.

Problem/Question 13.

(a) Do the p-adic point counting methods of Lauder which allow you to go from one curve from another in a family apply to p-adic methods without the linear factor? (Edixhoven)

(b) Do Fesenko’s methods for proving good properties of Hasse-Weil L-functions of curves over number fields provide anything useful for computations? (Edixhoven)

Remarks.

(i) Does Riemann-Roch provide anything useful? (Apparently not; involves linear algebra over matrices of size the number of points.) (Wan)

Problem/Question 14. Pila’s method for computing roots of unity is exponential in g. Is there any reason it can’t be made linear? (Elkies)

Remarks.

(i) Huang has a randomized algorithm (depends on factoring polynomials) with exponent g^{O(1)}. (Lauder) They avoid using a full projective model. (Pila)

(ii) For any prime ℓ, you work in a group of size ℓ^{2g}, so shouldn’t be much worse. See also Edixhoven’s talk. The calculation there (on modular curves) can also be done for Drinfeld modular curves. (Elkies) Is there an analogue of the point-counting problem for Drinfeld modules? (Kedlaya)

(iii) Has anyone tried doing Schoof-Pila in genus 2? (Kedlaya) Gaudry and Schost have applied AGM. (Couveignes) They also did small torsion. (Edixhoven)

Problem/Question 15. Given a variety over a finite field, can you verify that a given function is its zeta function (i.e., is the question in NP)? (Lenstra, Edixhoven)

Remarks.

(i) Yes (for g fixed), because you can verify the orders of the Jacobian over the first g extension fields. (Elkies)

Problem/Question 16. How can you compute with points as in Edixhoven’s talk? In that application, you can avoid writing down explicit ℓ-torsion points (only the fields of definition), but can you write them down for other transformation? (Edixhoven)

Remarks.

(i) Can one work out instances of the passage from H^{1} to H^{2}? E.g., K3 surface of Néron-Severi rank 19 (the rank 20 case is standard)? (Elkies)

(ii) More comments on ℓ-adic computation of zeta functions? (Pila)

Problem/Question 17.

(a) Can deformation theory be applied ℓ-adically? (Various)

(b) Under what circumstances do Betti numbers stay the same under reduction modulo p? (Various)

(c) Is finding the genus of a plane curve polynomial time (in the degree)? (Wan)

Problem/Question 18. Can you compute roots modulo p of a fixed polynomial (à la Schoof-Pila) in polynomial time, like x^{3} − 2? (Schoof)

Remarks.

(i) A problem is realizing a given polynomial as the characteristic polynomial of an endomorphism, if its roots do not lie in a CM field. Does it help to consider modular forms? (Pila)

B.1 Remarks on Agrawal’s Conjecture

These notes concern Agrawal’s conjecture, the first problem in the problem session:

Conjecture. Let n and r be two coprime positive integers. If

(X − 1)^{n} ≡ X^{n} − 1 (mod n, X^{r} − 1)

then either n is prime or

n^{2} ≡ 1 (mod r).

(If Agrawal’s conjecture were true, this would improve the polynomial time complexity of the AKS primality testing algorithm from Õ((log n)^{7.5}) to Õ((log n)^{3}).)

The contents are due to Lenstra and Pomerance and suggest strongly that this conjecture is false.

Proposition (Lenstra). Let p_{1}, …, p_{k} be k pairwise distinct prime integers, and let n = p_{1} … p_{k}. Suppose that:

(i) k ≡ 1 (mod 4); (ii) p_{i} ≡ 3 (mod 80) for all i; (iii) (p_{i} − 1) | (n − 1) for all i; and (iv) (p_{i} + 1) | (n + 1) for all i.

Then

(X − 1)^{n} ≡ X^{n} − 1 (mod n, X^{5} − 1)

and n^{2} ≢ 1 (mod 5).

Remark. This result is also true for k ≡ 3 (mod 4).

Proof. By assumption we get n = 3^{k} ≡ 3 (mod 80) because 3^{4} ≡ 1 (mod 80). So n ≡ 3 (mod 5) and then n^{2} ≢ 1 (mod 5).

We also have the following identity:

(X − 1, X^{4} + X^{3} + X^{2} + X + 1, n) = (1)

in the polynomial ring ℤ[X]. Hence, in order to prove the identity

(X − 1)^{n} ≡ X^{n} − 1 (mod n, X^{5} − 1)

it suffices to prove that

(X − 1)^{n} ≡ X^{n} − 1 (mod n, X^{4} + ⋯ + X + 1).

The Chinese remainder theorem gives the following isomorphism:

ℤ[X]/(n, X^{4} + ⋯ + X + 1) ≅ ∏_{i=1}^{k} 𝔽_{p_{i}}[X]/(X^{4} + ⋯ + X + 1).

Each ring factor R_{i} = 𝔽_{p_{i}}[X]/(X^{4} + ⋯ + X + 1) is actually a field since each prime p_{i} is prime to 5 and the 5th cyclotomic polynomial is irreducible in 𝔽_{p}[X] so that R_{i} is nothing but the splitting field of 𝔽_{p_{i}}[ζ_{5}] for a primitive 5th root of unity ζ_{5}.

It therefore suffices to prove that each prime p_{i} = p satisfies

(ζ_{5} − 1)^{n} = ζ_{5}^{n} − 1

in the field 𝔽_{p}[ζ_{5}]. We see from (ii) that

(ζ_{5} − 1)^{p^{2}} = ζ_{5}^{p^{2}} − 1 = ζ_{5}^{−1} − 1

(since p ≡ 3 (mod 5), we have p^{2} ≡ −1 (mod 5)). Thus

(ζ_{5} − 1)^{p^{2}} = −ζ_{5}^{−1}(ζ_{5} − 1).

Hence the order of (ζ_{5} − 1) in 𝔽_{p}[ζ_{5}] divides 10(p^{2} − 1).

It remains to check the residue class of n modulo 10(p^{2} − 1); more precisely, it suffices to show that

n ≡ p (mod 10(p^{2} − 1)).

We can factor 10(p^{2} − 1) into 4 pairwise coprime factors:

10(p^{2} − 1) = 5(2^{4}) (\frac{p − 1}{2}) (\frac{p + 1}{4})

so it suffices to verify this modulo each factor. Since n, p ≡ 3 (mod 80) by assumption, the first follows. Assumption (iii) implies that

n ≡ 1 (mod (p − 1)/2)

and so

n = p (mod (p − 1)/2)

since p ≡ 1 (mod (p − 1)/2), and

n ≡ p (mod (p + 1)/4)

similarly. This completes the proof. □

By this proposition, we have a heuristic which suggests the existence of many counterexamples to the Agrawal conjecture. This argument taken from analytic number theory is very similar to the one already used by Pomerance to find counterexamples to the Baillie-PSW primality testing algorithm which can be found at http://www.pseudoprime.com/dopo.pdf.

Fix some arbitrarily large integer m and let T be very large. Let P = P_{m}(T) denote the set of primes p in the interval [T, T^{m}] such that:

A. p ≡ 3 (mod 80); B. (p − 1)/2 is squarefree and divisible only by primes q ≤ T with q ≡ 3 (mod 4); C. (p + 1)/4 is squarefree and divisible only by primes r ≤ T with r ≡ 1 (mod 4).

Both smoothness conditions (2) and (3) are rather restrictive: heuristically, the cardinality of the set P is asymptotically (T → ∞)

#P ∼ c_{m} \frac{T^{m}}{(log T^{m})^{2}}

for some positive constant c_{m} that depends on the choice of m. In particular, we can take a sufficiently large integer T such that

#P > \frac{T^{m}}{(log T^{m})^{3}}

which we assume from now on.

Also choose an odd integer k ≡ 1 (mod 4) such that k < T^{2}/(log T^{m}). We consider the squarefree numbers n that run over products of k distinct primes of the set P. Obviously such an integer n satisfies n < e^{T^{2}}. The number of choices for n is exactly given by the binomial coefficient \binom{#P}{k}, and we get the lower bound:

\binom{#P}{k} ≥ (\frac{T^{m}}{(log T^{m})^{3}(T^{2}/ log T^{m})})^{(T^{2}/ log T^{m})−4}
> (T^{m−3})^{(T^{2}/ log T^{m})−4} = e^{(1−3/m)T^{2}−4(m−3) log T}
> e^{1−(4/m)T^{2}}.

for large T and fixed m.

Let Q denote the product of primes q ≤ T with q ≡ 3 (mod 4), and let R denote the product of primes r ≤ T with r ≡ 1 (mod 4). Then Q and R are coprime and asymptotically the product QR equals e^{(1+o(1))T} as T → ∞, so that QR < e^{2T} for some large T. Thus, the number of choices for the numbers n that satisfy in addition n ≡ 1 (mod Q) and n ≡ −1 (mod R) should be asymptotically

e^{(1−4/m)T^{2}}e^{−2T} > e^{T^{2}(1−5/m)}.

But any such n is a counterexample to Agrawal’s conjecture by Lenstra’s proposition. We see therefore that for fixed m and for all large T, there should be at least e^{T^{2}(1−5/m)} counterexamples to Agrawal’s conjecture below e^{T^{2}}. That is, if we let x = e^{T^{2}}, this argument implies that the number of counterexamples ≤ x is expected to be ≫ x^{1−ϵ} for any ϵ > 0.