Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p

DOI10.2307/2007968zbMath0579.14025OpenAlexW4242424230MaRDI QIDQ3701545

René Schoof

Publication date: 1985

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2007968

zbMATH Keywords

algorithmfinite fieldspolynomialsfactorizationtheoryFrobeniussquare rootfieldcomputational numbernumber of points on elliptic curves over finite

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special algebraic curves and curves of low genus (14H45) Elliptic curves (14H52) Polynomials over finite fields (11T06) Finite ground fields in algebraic geometry (14G15) Software, source code, etc. for problems pertaining to algebraic geometry (14-04) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items (only showing first 100 items - show all)

Taking cube roots in \(\mathbb Z_{m}\) ⋮ Fast cryptography in genus 2 ⋮ Using partial smoothness of 𝑝-1 for factoring polynomials modulo 𝑝 ⋮ On division polynomial PIT and supersingularity ⋮ Primality of the number of points on an elliptic curve over a finite field ⋮ Nonlinearities in elliptic curve authentication ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ Generating random factored Gaussian integers, easily ⋮ Diffie-Hellman Oracles ⋮ Algorithms for Black-Box Fields and their Application to Cryptography ⋮ The existence of infinitely many supersingular primes for every elliptic curve over \(\mathbb Q\). ⋮ Factoring polynomials and primitive elements for special primes ⋮ Finding elliptic curves with a subgroup of prescribed size ⋮ The \(\mathbb Q\)-curve construction for endomorphism-accelerated elliptic curves ⋮ A review on the isomorphism classes of hyperelliptic curves of genus 2 over finite fields admitting a Weierstrass point ⋮ Rigid cohomology and \(p\)-adic point counting ⋮ Computing zeta functions of arithmetic schemes ⋮ Explicit bounds of polynomial coefficients and counting points on Picard curves over finite fields ⋮ Zeta functions, one-way functions, and pseudorandom number generators. ⋮ Plectic \(p\)-adic invariants ⋮ Counting points on elliptic curves over finite fields ⋮ Computing the number of points on an elliptic curve over a finite field: algorithmic aspects ⋮ Computational Number Theory and Cryptography ⋮ A quasi quadratic time algorithm for hyperelliptic curve point counting ⋮ Modular composition modulo triangular sets and applications ⋮ The number of irreducible polynomials over finite fields with vanishing trace and reciprocal trace ⋮ Improved complexity bounds for counting points on hyperelliptic curves ⋮ Analysis of the fault attack ECDLP over prime field ⋮ Division polynomials on the Hessian model of elliptic curves ⋮ Isogeny formulas for Jacobi intersection and twisted Hessian curves ⋮ Efficient computation of Cantor's division polynomials of hyperelliptic curves over finite fields ⋮ Elliptic curve cryptography: the serpentine course of a paradigm shift ⋮ Super-Golden-Gates for \(PU(2)\) ⋮ Two kinds of division polynomials for twisted Edwards curves ⋮ A simple point counting algorithm for Hessian elliptic curves in characteristic three ⋮ Interpolation of the Double Discrete Logarithm ⋮ Factoring polynomials modulo special primes ⋮ Frobenius elements in Galois representations with \(\mathrm{SL}_{n}\) image ⋮ ``Chinese & Match, an alternative to Atkin's ``Match and Sort method used in the SEA algorithm ⋮ On splitting sets in block designs and finding roots of polynomials ⋮ Constructing Isogenies on Extended Jacobi Quartic Curves ⋮ Counting points on hyperelliptic curves in average polynomial time ⋮ Fault-based attack on Montgomery's ladder algorithm ⋮ Injective encodings to binary ordinary elliptic curves ⋮ Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields ⋮ Sato-Tate distributions ⋮ Cycles in the Supersingular ℓ-Isogeny Graph and Corresponding Endomorphisms ⋮ Fast computation of special resultants ⋮ Elliptic curve implementation of zero-knowledge blobs ⋮ Computing rational cohomology and Hecke eigenvalues for Bianchi groups ⋮ Elliptic Curves and Primality Proving ⋮ Counting curves and their projections ⋮ On the independence of Heegner points associated to distinct quadratic imaginary fields ⋮ On taking square roots without quadratic nonresidues over finite fields ⋮ Efficient randomized generation of optimal algorithms for multiplication in certain finite fields ⋮ Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes ⋮ Computing in degree \(2^k\)-extensions of finite fields of odd characteristic ⋮ On the existence and non-existence of elliptic pseudoprimes ⋮ Elliptic Gauss sums and applications to point counting ⋮ Efficient CM-constructions of elliptic curves over finite fields ⋮ On the representation of the number of integral points of an elliptic curve modulo a prime number ⋮ An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields ⋮ \(p\)-adic properties of division polynomials and elliptic divisibility sequences ⋮ Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? ⋮ A generic approach to searching for Jacobians ⋮ Realistic analysis of some randomized algorithms ⋮ One-way permutations on elliptic curves ⋮ A new generalization of the KMOV cryptosystem ⋮ Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves ⋮ Recovering Fourier coefficients of some functions and factorization of integer numbers ⋮ Some remarks on primality proving and elliptic curves ⋮ Quantum algorithms for algebraic problems ⋮ On the discrete logarithm problem in class groups of curves ⋮ Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus ⋮ Deterministic Encoding into Twisted Edwards Curves ⋮ Reprint of: Endomorphism rings of reductions of Drinfeld modules ⋮ Endomorphism rings of reductions of Drinfeld modules ⋮ Modular Polynomials for Genus 2 ⋮ Sequences of numbers generated by addition in formal groups and new primality and factorization tests ⋮ Cryptographic Pairings Based on Elliptic Nets ⋮ Deterministic irreducibility testing of polynomials over large finite fields ⋮ Papers from the conference 21st Journées Arithmétiques held at the Università Lateranense, Rome, July 12--16, 2001 ⋮ Computing zeta functions of Artin-Schreier curves over finite fields. II ⋮ Point counting on reductions of CM elliptic curves ⋮ Uniform encodings to elliptic curves and indistinguishable point representation ⋮ Trading GRH for algebra: Algorithms for factoring polynomials and related structures ⋮ Recent developments in primality proving ⋮ Counting points on hyperelliptic curves of genus 2 with real models ⋮ The Pohlig-Hellman method generalized for group structure computation ⋮ A Recursive Method for Computing Zeta Functions of Varieties ⋮ Some computational problems of cryptographic significance concerning elliptic curves over rings ⋮ Computing zeta functions of algebraic curves using Harvey's trace formula ⋮ Counting points on smooth plane quartics ⋮ Pseudorandom vector generation using elliptic curves and applications to Wiener processes ⋮ Constructive and destructive facets of Weil descent on elliptic curves ⋮ Elliptic curve cryptosystems and their implementation ⋮ An algorithm to compute the number of points on elliptic curves of \(j\)-invariant 0 or 1728 over a finite field ⋮ Computations of Galois representations associated to modular forms of level one ⋮ Fast computation of canonical lifts of elliptic curves and its application to point counting. ⋮ Rational isogenies from irrational endomorphisms

This page was built for publication: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p