Mathematics Problem Archive

Let $n$ be a positive integer. For almost all $n$-tuples $(x_1,\ldots,x_n)$, there are positive constants $c$ and $D_0$ (depending on $n$, $x_1,\ldots...

Let $(n_i)_{i\ge 0}$ be an increasing sequence of positive integers. Assume there is a prime number $p$ such that the power series $$ \sum_{i\ge 0}z^{...

Given an elliptic curve $E/\mathbb{F}_q$ and $P\in E(\mathbb{F}_q)$, characterize maps or isogenies $\psi:E\to E'$ for which $\psi(P)$ can be evaluate...

Find bilinear structures that are useful for cryptographic constructions....

Find orders $\mathcal{O}$ whose Picard groups contain $\mathbb{Z}/\ell$, admit compact element representations, and allow group composition in $O(\log...

Make the proposed realization of existing finite-field discrete-logarithm systems inside class groups explicit for practical systems....

Determine whether Weil descent compromises the security of the proposed class-group realization of finite-field discrete-logarithm systems....

Develop a fast algorithm to compute the Tate–Lichtenbaum pairing $T_n$....

Turn $H^2(G_K,K_s^*)$ into an explicitly computational group....

Explicitly describe the cocycle $c_u$, equivalently fast-compute invariants of local algebras split by the generalized-dihedral extensions specified i...

Explicitly construct global algebras or Brauer classes with prescribed local data, especially when the local splitting fields are dihedral....

Adapt Schoof's method to compute zeta functions of curves without unfavorable dependence on the genus....

Is computation of a curve's zeta function polynomial simultaneously in the genus $g$ and in $\log q$?...

Determine whether natural de Rham cup-product pairings can be used to improve zeta-function computations....

Remove the imaginary-hyperelliptic and $p\ne2$ restrictions from the complexity bound stated in the slides....

Test and analyze whether deleting extra points and fixing the lift $x\mapsto x^p$ improves Frobenius lifts for nondegenerate curves....

Develop the higher-dimensional analogue of the nondegenerate-curve Frobenius-lift method....

Find useful deformations of nondegenerate curves together with easy starting matrices for Frobenius computation....

Work out effective zeta-function computations for nondegenerate surfaces in toric threefolds....

Factor $N=p^rq^s$ with $r\approx s$ using fewer known bits of the factors than existing methods require....

Factor $N=pqr$ from fewer known bits of its prime factors....

Develop methods to factor an integer when the known bits of its factors are nonconsecutive....

Reduce the number of guesses required by lattice attacks for factoring with partially known bits....

Extract useful information from incorrect guesses in factoring attacks based on partially known bits....

Efficiently solve for, or characterize all relevant roots of, $x^2-1$ modulo a composite integer $N$ in the setting of the slides....

Improve the running time of Coppersmith-type methods for finding small modular or integer roots....

Understand and control how the shape of a polynomial affects Coppersmith-type small-root algorithms....

Give conditions or constructions that ensure algebraic independence in multivariate elimination for small-root attacks....

Find an optimal collection of polynomials for multivariate lattice-based small-root attacks....

Determine whether the lattice dimension in the stated small-root constructions can be reduced....

Resolve the zero-constant-term case in the Newton-polytope formulation of multivariate small-root methods....

Construct additional cryptographic primitives whose security follows from the hardness of finding small roots....

Analyze how effective rotation-augmented lattice reduction is on cyclic or NTRU lattices....

Speed up rotation-augmented reduction algorithms for cyclic or NTRU lattices....

For large $N$, efficiently find the required short five-term geometric progressions modulo $N$ that avoid first- and second-order recurrence, thereby ...

Study the distribution of group structures $E(\mathbb{F}_q)$ as elliptic curves $E/\mathbb{F}_q$ vary; in particular, determine the correct nonuniform...

Is the exponent $e_q(E)$ of $E(\mathbb{F}_q)$ typically close to $q$?...

How often is the group of a random elliptic curve over $\mathbb{F}_q$ cyclic?...

Characterize the typical arithmetic structure of $\#E(\mathbb{F}_q)$ for elliptic curves over finite fields....

Prove that there are sufficiently many prime-order elliptic curves over every finite field $\mathbb{F}_q$....

For a fixed $E/\mathbb{F}_q$, prove that $\#E(\mathbb{F}_{q^n})/\#E(\mathbb{F}_q)$ is prime for infinitely many $n$....

For a torsion-free elliptic curve $E/\mathbb{Q}$, prove that $\#E(\mathbb{F}_p)$ is prime for infinitely many primes $p$....

Prove that sufficiently many elliptic curves $E/\mathbb{F}_p$ have smooth group order $\#E(\mathbb{F}_p)$....

Quantify elliptic curves over finite fields whose group order has a large prime divisor....

Prove the conjecture that the EC-LCG, EC-PG, and EC-NRG sequences defined in the slides are very well distributed....

Given integers $n$ and a prime power $q$, construct, when possible, an elliptic curve $E/\mathbb{F}_q$ with $\#E(\mathbb{F}_q)=n$....

Given $n$, efficiently choose a prime power $q$ and construct an elliptic curve $E/\mathbb{F}_q$ with $\#E(\mathbb{F}_q)=n$....

Given the Weil polynomial of an abelian-threefold isogeny class over a finite field, determine whether the class contains a Jacobian....

Decide whether a given principally polarized abelian threefold over a field $k$ is the Jacobian of a curve over $k$....

Give an effective input representation for a principally polarized abelian threefold suitable for deciding whether it is a Jacobian....