On division polynomial PIT and supersingularity

DOI10.1007/S00200-018-0349-ZzbMATH Open1443.11117arXiv1801.02664OpenAlexW2962707242MaRDI QIDQ1623917FDOQ1623917

Authors: Javad Doliskani 

Publication date: 15 November 2018

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Abstract: For an elliptic curve $E$ over a finite field $F_q$, where $q$ is a prime power, we propose new algorithms for testing the supersingularity of $E$. Our algorithms are based on the Polynomial Identity Testing (PIT) problem for the $p$-th division polynomial of $E$. In particular, an efficient algorithm using points of high order on $E$ is given.

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

Recommendations

• Identifying supersingular elliptic curves
• On the \(p\)-th division polynomial
• A primality test algorithm using supersingular elliptic curves
• Improved supersingularity testing of elliptic curves using Legendre form
• Division polynomials of elliptic curves over finite fields

zbMATH Keywords

elliptic curvesdivision polynomialspolynomial identity testing

Mathematics Subject Classification ID

Cryptography (94A60) Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50) Elliptic curves (14H52)

Cites Work

• Elements of large order on varieties over prime finite fields
• Elements of high order on finite fields from elliptic curves
• The Arithmetic of Elliptic Curves
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Title not available (Why is that?)
• On the order of points on curves over finite fields
• Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
• Elliptic curves. Number theory and cryptography
• Cryptographic hash functions from expander graphs
• Modern computer algebra
• On Artin's conjecture.
• A generalisation of Artin's conjecture for primitive roots
• Fast construction of irreducible polynomials over finite fields
• Title not available (Why is that?)
• Identifying supersingular elliptic curves
• Progress on polynomial identity testing
• Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
• Constructing supersingular elliptic curves
• Isogeny-based quantum-resistant undeniable signatures

Cited In (5)

• Identifying supersingular elliptic curves
• Improved supersingularity testing of elliptic curves using Legendre form
• On the \(p\)-th division polynomial
• Division polynomials on the Hessian model of elliptic curves
• Effective pairings in isogeny-based cryptography

Uses Software

• NTL
• PARI/GP
• SageMath

This page was built for publication: On division polynomial PIT and supersingularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1623917)