Finding elliptic curves with a subgroup of prescribed size
From MaRDI portal
(Redirected from Publication:3179510)
Abstract: Assuming the Generalized Riemann Hypothesis, we design a deterministic algorithm that, given a prime p and positive integer m=o(sqrt(p)/(log p)^4), outputs an elliptic curve E over the finite field F_p for which the cardinality of E(F_p) is divisible by m. The running time of the algorithm is mp^(1/2+o(1)), and this leads to more efficient constructions of rational functions over F_p whose image is small relative to p. We also give an unconditional version of the algorithm that works for almost all primes p, and give a probabilistic algorithm with subexponential time complexity.
Recommendations
Cites work
- scientific article; zbMATH DE number 989379 (Why is no real title available?)
- scientific article; zbMATH DE number 4077312 (Why is no real title available?)
- scientific article; zbMATH DE number 3995866 (Why is no real title available?)
- scientific article; zbMATH DE number 2121181 (Why is no real title available?)
- scientific article; zbMATH DE number 6164023 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- scientific article; zbMATH DE number 3099304 (Why is no real title available?)
- A Brun-Titschmarsh theorem for multiplicative functions.
- A Hyperelliptic Smoothness Test, II
- A Note on Elliptic Curves Over Finite Fields
- A Rigorous Time Bound for Factoring Integers
- A group action on \({\mathbb Z}_p^{\times}\) and the generalized DLP with auxiliary inputs
- A hyperelliptic smoothness test. I
- A new approach to the discrete logarithm problem with auxiliary inputs
- A note on elliptic curves over finite fields
- Abelian varieties over finite fields
- Accelerating the CM method
- Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs
- Bicovering arcs and small complete caps from elliptic curves
- Choosing the correct elliptic curve in the CM method
- Class invariants by the CRT method
- Computing Hilbert class polynomials with the Chinese remainder theorem
- Computing Igusa class polynomials
- Discrete logarithm problems with auxiliary inputs
- Discrete logarithms, Diffie-Hellman, and reductions
- Efficient CM-constructions of elliptic curves over finite fields
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Factoring integers with elliptic curves
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- Mathematics of public key cryptography.
- Modern computer algebra
- Multiple Discrete Logarithm Problems with Auxiliary Inputs
- On Certain Character Sums
- On primes in arithmetic progressions
- On the characterization of minimal value set polynomials
- On the deterministic complexity of factoring polynomials over finite fields
- On the distribution of Atkin and Elkies primes
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
- PRIMES is in P
- Quadratic non-residues in short intervals
- Short sums of certain arithmetic functions
- The Arithmetic of Elliptic Curves
- The complexity of class polynomial computation via floating point approximations
- The distribution of integers with a divisor in a given interval
- The distribution of quadratic residues and non‐residues
- Topics in multiplicative number theory
- Value sets of Dickson polynomials over finite fields
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
Cited in
(4)- Determining the $2$-Sylow subgroup of an elliptic curve over a finite field
- scientific article; zbMATH DE number 799785 (Why is no real title available?)
- An algorithmic construction of finite elliptic curves of order divisible by a large prime
- A low-memory algorithm for finding short product representations in finite groups.
This page was built for publication: Finding elliptic curves with a subgroup of prescribed size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179510)
