Speeding up the computations on an elliptic curve using addition-subtraction chains

DOI10.1051/ita/1990240605311zbMath0724.11068OpenAlexW1584722274MaRDI QIDQ5202278

J. Olivos, François Morain

Publication date: 1990

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92374

zbMATH Keywords

algorithmsfactorizationexponentiationprimality testingaddition-subtraction chainsAtkin's testcomputations on elliptic curves

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Radix representation; digital problems (11A63) Factorization (11Y05) Primality (11Y11)

Related Items (31)

Fast cryptography in genus 2 ⋮ Stern polynomials ⋮ Elliptic curve scalar multiplication algorithm using complementary recoding ⋮ On binary signed digit representations of integers ⋮ Speeding up the computations of elliptic curves cryptoschemes ⋮ Extending the signed non-zero bit and sign-aligned columns methods to general bases for use in cryptography ⋮ Speeding up the Elliptic Curve Scalar Multiplication Using Non Adjacent Form ⋮ Fast elliptic scalar multiplication using new double-base chain and point halving ⋮ Distribution results for low-weight binary representations for pairs of integers ⋮ Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated ⋮ On-line evaluation of powers using Euclid's algorithm ⋮ Redundant \(\tau \)-adic expansions. II: Non-optimality and chaotic behaviour ⋮ Balanced non-adjacent forms ⋮ On the construction of short addition-subtraction chains and their applications ⋮ Fast Point Multiplication on Elliptic Curves without Precomputation ⋮ Invariant measures, matching and the frequency of 0 for signed binary expansions ⋮ Automatic average-case analysis of algorithms ⋮ Elliptic Curves and Primality Proving ⋮ IMPROVEMENT OF THE LOWER BOUND FOR THE COMPLEXITY OF EXPONENTIATION ⋮ The Hamming weight of the non-adjacent-form under various input statistics ⋮ Binary signed-digit integers and the Stern diatomic sequence ⋮ Symmetric digit sets for elliptic curve scalar multiplication without precomputation ⋮ On the minimal Hamming weight of a multi-base representation ⋮ On the low Hamming weight discrete logarithm problem for nonadjacent representations ⋮ On Bellman's and Knuth's problems and their generalizations ⋮ Unbalanced digit sets and the closest choice strategy for minimal weight integer representations ⋮ Efficient scalar multiplication for elliptic curves over binary fields ⋮ Signed bits and fast exponentiation ⋮ Matching for random systems with an application to minimal weight expansions ⋮ Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms ⋮ Efficient algorithms for speeding up the computations of elliptic curve cryptosystems

Uses Software

• Maple

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring integers with elliptic curves
• The arithmetic of elliptic curves
• A lower bound for the length of addition chains
• Sequences of numbers generated by addition in formal groups and new primality and factorization tests
• Factorizations of 𝑏ⁿ±1, 𝑏=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers
• Modular Multiplication Without Trial Division
• Effect of Improved Multiplication Efficiency on Exponentiation Algorithms Derived from Addition Chains
• Implementation of a new primality test
• Elliptic Curve Cryptosystems
• On vectorial addition chains
• The Optimal Algorithm to Evaluate x n Using Elementary Multiplication Methods
• A method for obtaining digital signatures and public-key cryptosystems
• Addition chains using continued fractions
• Diophantine Equations with Special Reference To Elliptic Curves
• Remarks on number theory III. On addition chains

This page was built for publication: Speeding up the computations on an elliptic curve using addition-subtraction chains