Problems

Problem/Question 1. If

$$(X-1)^n \equiv X^n - 1 \pmod{n,X^r-1}$$

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

$$n^2 \equiv 1 \pmod{r}$$

when $n$ is composite? (AKS)

Remarks.

1. In the simplest case, $r=5$ and $n \equiv 2 \pmod{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 \equiv 2 \pmod{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)

2. For $r \geq 5$, there are 5000 pairs $(n,r)$ that all satisfy these conditions. (AKS)

3. The most naive heuristic (looking at $2$ as a random element modulo $n$) for the first claim relies upon the fact that $\sum 1/n$ diverges, whereas in this case we are looking at $\sum 1/n^r$ which converges. (Lenstra) These heuristics need to take into account smoothness. (Bernstein)

4. Is there a reason why $n^2 \equiv 1 \pmod{r}$ comes into the play? For all counterexamples with $r \geq 7$, $p \mid n$ implies $p^2 \equiv 1 \pmod{r}$. (Lenstra, AKS)

5. In these conditions we see that $r^n \equiv r \pmod{n}$. (Lenstra) So if $p \mid 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 \mid 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 \equiv 1 \pmod{r}$. Much of this can be found in Grantham's thesis. (Pomerance)

6. These heuristics are compatible with the AKS primality test because there we have $r$ growing with $n$. (Bernstein)

7. What about $r \gg (\log \log n)^2$? The largest $r$ found was $97$, and for $r \geq 13$ we found only approximately $40$ such elements. (AKS)

8. Are prime powers special? (Lenstra) For $r \geq 5$, all $n$ found were squarefree. (AKS) The search was done for $n \leq 10^{11}$, $r < 100$.

Problem/Question 2. Consider $\mathbb{F}_p$ and $d \in \mathbb{Z}_{>0}$, and $S \subset \mathbb{F}_p$ with $\char93 S =d$. Let $h(X) \in \mathbb{F}_p[X]$ with $h(s) \neq 0$ for all $s \in S$. Let $G$ be the group generated by $X-s$ for $s \in S$. In the original AKS paper, we have $\char93 G \geq 2^d$. There are techniques for getting $\char93 G \geq (5.82)^d$ (using lattice point counting); there seems to be much more room for improvement (perhaps using ABC). (Bernstein, Voloch) Perhaps

$$(\log \char93 G)/d \to \infty$$

as $d \to \infty$ uniformly over $h$.

Remarks.

1. It is hard to find examples with $\char93 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)

2. Does it help to know if $S$ is an interval? (Voloch, Lenstra) Not used thus far.

3. For Kummer extensions, the extensions will look like multiplicative cosets of a root of unity times a single number--can this be used? (Bernstein)

4. Is this problem independent of $h$? (Cohen) For example, $h(X)=X^d-1$ with group generated by $X$ has small order. (Bernstein)

5. Instead of looking at $\mathbb{F}_p[X]/(h)$, look at an elliptic curve $E$ over $\mathbb{F}_q$ and the subgroup of $E(\mathbb{F}_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 $\mathbb{F}_p$ and look at the subgroup of points generated by $C(\mathbb{F}_p)$. This is then amenable to class field theory techniques. (Voloch) The interesting case is the analogous case with AKS: $q=p^d$ and $\char93 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 \in \mathbb{Z}[X]$ with no common irreducible factor, and two integers $n,m \in \mathbb{Z}_{>0}$, find in polynomial time all $x \in \mathbb{Z}$ such that $f(x) \mid m$ and $g(x) \mid n$, with $\vert x\vert<H(f,g,m,n)$ for some function $H$.

Remarks.

1. 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 \parallel n$, and $n$ is perfect, then $1+x+\dots+x^k \mid 2n$.
2. There is one solution for very small $H$ which is to just try out the necessary values of $x$.
3. There are some results on when $m \mid f(x)$, which has typographical similarity to our problem. (Coppersmith)
4. 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)
5. By Gary Miller's thesis, if you are given a multiple of $\phi(n)$, you can factor $n$ using a randomized algorithm or deterministically under the GRH. (Pomerance) You can replace $\phi(n)$ by $\sigma(n)$. (Lenstra)
6. If you allow randomization, the first problem should be doable. (Lenstra) There is a paper of Bach-Shallit.
7. This algorithm will recognize perfect numbers but it may not recognize imperfect numbers. (Lenstra)
8. There is a more general notion (multiply perfect) where $\sigma(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.
9. A different problem is to just consider $f=g$, or to look at rational functions which are integer-valued.
10. Are there heuristics for the number of such $x$ which are related to heuristics for the largest prime divisor of $f(x)$? (Pomerance)
11. Look at $f(x)=(x^4+x^5+\dots+x^8) \mid n$. Choose $h \in \mathbb{R}$ and $g \approx e^{\sqrt{8\log n \log h}}$. Then you can find the set of all $x$ with $\vert x\vert \leq 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$.

1. 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)

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

Remarks.

1. 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)

2. 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)

3. If you know a $k$th 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.

4. Given a quadratic nonresidue, any even degree polynomial $f$ with $f \mid (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.

5. 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_\lambda$ over $\mathbb{F}_p$ (e.g. the Frey curves), $\lambda \in \mathbb{P}^1(\mathbb{F}_p)$. Can you find deterministically $\lambda$ such that $E_\lambda$ and $E_{\lambda+1}$ are not isogenous (i.e. $\char93 E_\lambda(\mathbb{F}_p) \neq \char93 E_{\lambda+1}(\mathbb{F}_p)$). (Elkies)

Remarks.

1. 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 $\lambda$ and $1-\lambda$, and then you can `separate them apart' by applying Schoof's algorithm and obtain a deterministic square root.
2. Over $\mathbb{Q}$, there are only finitely many isogeny classes, so you just need to check that $\lambda$ is not a root of a finite list of polynomial equations. (Elkies)
3. Can you deterministically find $\lambda,\mu$ such that $E_\lambda,E_\mu$ are not isogeneous? (Coppersmith) What happens to Schoof's algorithm if you just run it with $\lambda$ a variable? (Lenstra)
4. There are bounds $p^{1/2+\epsilon}$ on the number of isogeny classes (Hasse interval) over $\mathbb{F}_p$.
5. You can also ask the question for the family of all elliptic curves over $\mathbb{F}_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) \in \mathbb{F}_q[X,Y]$ be irreducible. Let $g(Y)=f(aY+b,Y)$. Count (or estimate) the number of pairs $a,b$ over $\mathbb{F}_q$ such that $g$ is irreducible over $\mathbb{F}_q$. (Gao)

Remarks.

1. Is it $>0$ when $q>d^4$, where $d$ is the total degree of $f$? (Gao) Or perhaps some other bound on $q$?
2. 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.
3. The polynomial $f(X,Y)=X^q-X+Y$ is always divisible by $Y$ under such a substitution. (Lenstra) Therefore we need $q>d$.
4. Do you need to assume that $f$ is irreducible over $\overline{\mathbb{F}_q}$? (Pomerance)
5. What does Hilbert's irreducibility theorem say in this case? (Lenstra)
6. Applying the Chebotarev density theorem, this number is $rq^2+O(q^{3/2})$, where $r \in \mathbb{Q}_{\geq 0}$. (Wan) How big is the constant?
7. 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 $\mathbb{F}_q(a,b)$)? Is it possibly the full symmetric group? (Lenstra) Then $r(\char93 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)
8. 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 \geq n \in \mathbb{Z}$. Prove there is a polynomial $g \in \mathbb{F}_q[x]$ of degree $\leq 2\log n$ so that $x^m+g(x)$ has an irreducible factor of degree $n$. (Gao)

Remarks.

1. If $q$ is large compared to fixed $m,n$, this seems provable. (Gao)
2. For $q=2$, there is an application to computing discrete logs in $\mathbb{F}_{2^n}^*$. (Coppersmith)
3. If $m$ is the smallest power of $q$ which is $\geq n$, then $\alpha$ is a root of the irreducible factor, then the order of $\alpha$ is at least $\geq n^{(\log n)/(\log \log n)}$, so this group has large order. (Gao)
4. For all $q$, and $m=n$, it is proven if $\deg g \leq n/2$.
5. 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 $\leq 2\log n$ (Pomerance).
6. Alternatively, find a trinomial of degree $m \leq 2n$ over $\mathbb{F}_q$ with a primitive irreducible factor of degree $n$. (Gao) For small $q$ this may not be possible.
7. For fixed $n,q$, what is the sparsest polynomial of degree $\leq 2n$ with a primitive and irreducible 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-\epsilon)n$ should be possible. (Wan)

Problem/Question 8. Look at $\sum n^\rho$ over the zeros $\rho$ of the Riemann zeta function with the imaginary part of $\rho$ the interval $[T,2T]$. This is $\approx T/(2\pi) \Lambda(n)$. Can you make a primality test out of this? (Conrey)

The sum $\sum n^\rho \zeta'(\rho)/\zeta''(\rho) \approx T/(2\pi)\log p \log q$ if $n=pq$. Can you make a factoring algorithm out of this?

Problem/Question 9. Compute the zeta function of ${\mathrm{Spec}}\mathbb{Z}/n\mathbb{Z}$, namely

$$\zeta(s)=\prod_{p\mid n} \frac{1}{1-p^{-s}},$$

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

Replace $n$ by a polynomial $f(x) \in \mathbb{F}_p[x]$, so given

$$\zeta(s)=\prod_{\substack{g \mid f \text{$g$ monic,irreducible}}} \frac{1}{1-g}$$

can you recover the factorization of $f$ in $\mathbb{F}_q[x]$ in deterministic polynomial time? (Wan)

Remarks.

1. Can you compute the latter using Drinfeld modules? (Lenstra) Take $A=\mathbb{F}_p[x]/(f)$. Define an $\mathbb{F}_p$-linear map $T:A \to A$ where $T(\alpha)=\alpha^p-x\alpha$ which defines the Carlitz module, and makes $A$ into an $\mathbb{F}_p[T]$-module. If you write $f=\prod_g g_i^{e_i}$, and define $\phi(f)=\prod_i g_i^{e_i-1}(g_i-1)$, then $\phi(f)(T)$ kills $A$. But also $f\prod_i (g_i-1)$ also kills $A$. Mimic the factorization of integers using upper bounds on $\phi(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/\mathbb{Q}$ 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 $\char93 E(K)_{\textup{tors}}$ in terms of $[K:\mathbb{Q}]$. So try to find a number field $K$ where $p$ splits completely and such that $E(K)_{\textup{tors}}$ large. (Pomerance)

Remarks.

1. Whatever advantage you gain might be swamped by the expense of working in the larger number field. (Pomerance)
2. 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 $\geq 2$).
3. If $n=p^2q$, choose a discriminant $D$ such that $D$ is a nonsquare modulo $q$, and find an elliptic curve $E/\mathbb{Q}(\sqrt{D})$. Then $E(\mathbb{Q}(\sqrt{D}))_{\textup{tors}}$ injects into $E(\mathbb{F}_{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.

1. Coppersmith's algorithm works as follows. Pick at random $p_0$ of 7500 digits. Pick $q_0=\lfloor (n/p_0)10^{5000} \rfloor$. 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_0q_0+p_0y+q_0x+xy \approx n10^{5000}$$
   so use lattice reduction. At the end, check to make sure $p_0$ and $q_0$ are prime.
2. This has applications in cryptography. (Bernstein)

Problem/Question 12. Let $p$ be prime, write $p-1=2^\ell m$ where $m$ is odd, and assume $\ell \geq 3$. Find in deterministic polynomial time $x \in \mathbb{F}_p$ such that $x^{2^{\ell-1}}+1$ is not a $2^{\ell-1}$th power. (Kedlaya)

Remarks.

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

Problem/Question 13.

1. 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)
2. 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.

1. 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.

1. Huang has a randomized algorithm (depends on factoring polynomials) with exponent $g^{O(1)}$. (Lauder) They avoid using a full projective model. (Pila)
2. For any prime $\ell$, you work in a group of size $\ell^{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)
3. 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.

1. 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 $\ell$-torsion points (only the fields of definition), but can you write them down for other transformation? (Edixhoven)

Remarks.

1. 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)
2. More comments on $\ell$-adic computation of zeta functions? (Pila)

Problem/Question 17.

1. Can deformation theory be applied $\ell$-adically? (Various)
2. Under what circumstances do Betti numbers stay the same under reduction modulo $p$? (Various)
3. 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.

1. 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)

Back to the main index for Future directions in algorithmic number theory.