# Problems

Problem/Question 1. If

and does this imply that

when is composite? (AKS)

Remarks.

1. In the simplest case, and , 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 combined with the quadratic test with least discriminant with the Jacobi symbol (constructing a Lucas sequence of discriminant ) would be enough to show that 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 , there are 5000 pairs that all satisfy these conditions. (AKS)

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

4. Is there a reason why comes into the play? For all counterexamples with , implies . (Lenstra, AKS)

5. In these conditions we see that . (Lenstra) So if , the numbers , , must be very smooth (for ). The heuristics show that there should be lots' of primes satisfying these three numbers; create many from these , and as in the case of Carmichael numbers, then perhaps for some this should fail. (Pomerance) If is smooth for all and is squarefree, then the multiplicative group of has smooth order. The maximal order of any element in that group can be made small, so it would not be unusual for . 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 growing with . (Bernstein)

7. What about ? The largest found was , and for we found only approximately such elements. (AKS)

8. Are prime powers special? (Lenstra) For , all found were squarefree. (AKS) The search was done for , .

Problem/Question 2. Consider and , and with . Let with for all . Let be the group generated by for . In the original AKS paper, we have . There are techniques for getting (using lattice point counting); there seems to be much more room for improvement (perhaps using ABC). (Bernstein, Voloch) Perhaps

as uniformly over .

Remarks.

1. It is hard to find examples with smaller than . 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 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 ? (Cohen) For example, with group generated by has small order. (Bernstein)

5. Instead of looking at , look at an elliptic curve over and the subgroup of generated by simple coordinates. (Elkies) Using Weil restriction of scalars, you are looking at a curve inside of an abelian variety over and look at the subgroup of points generated by . This is then amenable to class field theory techniques. (Voloch) The interesting case is the analogous case with AKS: and , .

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

Given two monic polynomials with no common irreducible factor, and two integers , find in polynomial time all such that and , with for some function .

Remarks.

1. The first problem would be more interesting than perfect numbers themselves. You are given the numbers in binary. (Lenstra) A solution to the second problem gives a solution to the first: If is prime and , and is perfect, then .
2. There is one solution for very small which is to just try out the necessary values of .
3. There are some results on when , which has typographical similarity to our problem. (Coppersmith)
4. If is a perfect number, there is only one choice of where the factor is irrelevant; therefore you are reduced to the case where . (Pomerance)
5. By Gary Miller's thesis, if you are given a multiple of , you can factor using a randomized algorithm or deterministically under the GRH. (Pomerance) You can replace by . (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 has small height. Does this affect the problem? (Elkies) No, because you try out each one at a time, and for fixed this is virtually identical to the original problem.
9. A different problem is to just consider , or to look at rational functions which are integer-valued.
10. Are there heuristics for the number of such which are related to heuristics for the largest prime divisor of ? (Pomerance)
11. Look at . Choose and . Then you can find the set of all with such that . 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 .

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 . (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 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 with 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 . 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 with the GRH due to Ronyai, Evdokimov. (Cheng)

Problem/Question 5. Suppose that you have a nonconstant family of elliptic curves over (e.g. the Frey curves), . Can you find deterministically such that and are not isogenous (i.e. ). (Elkies)

Remarks.

1. You want sufficiently large and the degree small. (Elkies) If you can do this, then you should also be able to do it for and , and then you can separate them apart' by applying Schoof's algorithm and obtain a deterministic square root.
2. 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)
3. Can you deterministically find such that are not isogeneous? (Coppersmith) What happens to Schoof's algorithm if you just run it with a variable? (Lenstra)
4. There are bounds on the number of isogeny classes (Hasse interval) over .
5. You can also ask the question for the family of all elliptic curves over , deterministically. (Pomerance) This you can do by looking at if and are both squares. (Elkies)

Problem/Question 6. Let be irreducible. Let . Count (or estimate) the number of pairs over such that is irreducible over . (Gao)

Remarks.

1. Is it when , where is the total degree of ? (Gao) Or perhaps some other bound on ?
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 is always divisible by under such a substitution. (Lenstra) Therefore we need .
4. Do you need to assume that is irreducible over ? (Pomerance)
5. What does Hilbert's irreducibility theorem say in this case? (Lenstra)
6. Applying the Chebotarev density theorem, this number is , where . (Wan) How big is the constant?
7. View as a polynomial in 3 variables, . The surface is a cover of the affine plane given by the variables . What is the Galois group of this cover (over )? Is it possibly the full symmetric group? (Lenstra) Then is equal to the number of elements in the Galois group that are a full -cycle. Note this extension is separable whenever is irreducible. (Edixhoven)
8. If then all elements of the set are reducible, since any one irreducible element will have Frobenius which is a full cycle. (Lenstra)

Problem/Question 7. Let . Prove there is a polynomial of degree so that has an irreducible factor of degree . (Gao)

Remarks.

1. If is large compared to fixed , this seems provable. (Gao)
2. For , there is an application to computing discrete logs in . (Coppersmith)
3. If is the smallest power of which is , then is a root of the irreducible factor, then the order of is at least , so this group has large order. (Gao)
4. For all , and , it is proven if .
5. Consider the variant where instead of restricting the degree consider restricting the number of nonzero terms of to a fixed number (such as 7) (Bernstein), or at least (Pomerance).
6. Alternatively, find a trinomial of degree over with a primitive irreducible factor of degree . (Gao) For small this may not be possible.
7. For fixed , what is the sparsest polynomial of degree with a primitive and irreducible factor of degree ? (Pomerance) This should be uniform in , surely but perhaps . (Bernstein) Trivially, sparsity works by taking an irreducible polynomial of degree (excluding ). (Lenstra) Sparsity should be possible. (Wan)

Problem/Question 8. Look at over the zeros of the Riemann zeta function with the imaginary part of the interval . This is . Can you make a primality test out of this? (Conrey)

The sum if . Can you make a factoring algorithm out of this?

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

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

Replace by a polynomial , so given

can you recover the factorization of in in deterministic polynomial time? (Wan)

Remarks.

1. Can you compute the latter using Drinfeld modules? (Lenstra) Take . Define an -linear map where which defines the Carlitz module, and makes into an -module. If you write , and define , then kills . But also also kills . Mimic the factorization of integers using upper bounds on to factor probabilistically using this exponent' of the multiplicative group.

Problem/Question 10. To speed up the elliptic curve factorization algorithm, pick with large torsion group so that its reduction modulo is more likely to be smooth. Mazur's results show that this torsion subgroup can be no larger than . There is a result of Kamienny-Mazur-Merel: there is a bound on in terms of . So try to find a number field where splits completely and such that 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 ).
3. If , choose a discriminant such that is a nonsquare modulo , and find an elliptic curve . Then injects into . (Bleichenbacher)

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

Remarks.

1. Coppersmith's algorithm works as follows. Pick at random of 7500 digits. Pick . Add to and to where have 2500 digits a piece to fix this up. We want

so use lattice reduction. At the end, check to make sure and are prime.
2. This has applications in cryptography. (Bernstein)

Problem/Question 12. Let be prime, write where is odd, and assume . Find in deterministic polynomial time such that is not a 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 -adic point counting methods of Lauder which allow you to go from one curve from another in a family apply to -adic methods without the linear factor? (Edixhoven)
2. Do Fesenko's methods for proving good properties of Hasse-Weil -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 . Is there any reason it can't be made linear? (Elkies)

Remarks.

1. Huang has a randomized algorithm (depends on factoring polynomials) with exponent . (Lauder) They avoid using a full projective model. (Pila)
2. For any prime , you work in a group of size , 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 fixed), because you can verify the orders of the Jacobian over the first 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.

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

Problem/Question 17.

1. Can deformation theory be applied -adically? (Various)
2. Under what circumstances do Betti numbers stay the same under reduction modulo ? (Various)
3. Is finding the genus of a plane curve polynomial time (in the degree)? (Wan)

Problem/Question 18. Can you compute roots modulo of a fixed polynomial (à la Schoof-Pila) in polynomial time, like ? (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.