Finding elliptic curves with a subgroup of prescribed size

DOI10.1142/S1793042117500099zbMATH Open1377.11074arXiv1403.7887MaRDI QIDQ3179510FDOQ3179510

Authors: Andrew V. Sutherland, Igor E. Shparlinski 

Publication date: 21 December 2016

Published in: International Journal of Number Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1403.7887

Recommendations

• Constructing elliptic curves of prime order
• Finding the group structure of elliptic curves over finite fields
• Algorithmic Number Theory
• An algorithmic construction of finite elliptic curves of order divisible by a large prime
• Points on elliptic curves over finite fields

zbMATH Keywords

elliptic curvesdivisibilitysmooth numbersprime quadratic residues

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Factoring integers with elliptic curves
• Short sums of certain arithmetic functions
• The distribution of integers with a divisor in a given interval
• Topics in multiplicative number theory
• The Arithmetic of Elliptic Curves
• A Brun-Titschmarsh theorem for multiplicative functions.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Abelian varieties over finite fields
• PRIMES is in P
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mathematics of public key cryptography.
• Bicovering arcs and small complete caps from elliptic curves
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• On the deterministic complexity of factoring polynomials over finite fields
• Modern computer algebra
• On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
• Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
• On primes in arithmetic progressions
• A note on elliptic curves over finite fields
• The distribution of quadratic residues and non‐residues
• Computing Hilbert class polynomials with the Chinese remainder theorem
• On the distribution of Atkin and Elkies primes
• A Hyperelliptic Smoothness Test, II
• A hyperelliptic smoothness test. I
• Discrete logarithm problems with auxiliary inputs
• A Note on Elliptic Curves Over Finite Fields
• A Rigorous Time Bound for Factoring Integers
• Value sets of Dickson polynomials over finite fields
• Title not available (Why is that?)
• On Certain Character Sums
• Class invariants by the CRT method
• Accelerating the CM method
• Computing Igusa class polynomials
• On the characterization of minimal value set polynomials
• Discrete logarithms, Diffie-Hellman, and reductions
• The complexity of class polynomial computation via floating point approximations
• A Group Action on $${\mathbb Z}_p^{\times }$$ and the Generalized DLP with Auxiliary Inputs
• A new approach to the discrete logarithm problem with auxiliary inputs
• Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs
• Choosing the correct elliptic curve in the CM method
• Efficient CM-constructions of elliptic curves over finite fields
• Multiple Discrete Logarithm Problems with Auxiliary Inputs
• Quadratic non-residues in short intervals

Cited In (3)

• Determining the $2$-Sylow subgroup of an elliptic curve over a finite field
• Title not available (Why is that?)
• 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)