GCD-free algorithms for computing modular inverses.

DOI10.1007/978-3-540-45238-6_20MaRDI QIDQ5187959zbMATH OpenOpenAlexFDO

Authors Marc Joye, Pascal Paillier

Publication date 9 March 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-45238-6_20

zbMATH Keywords

efficient implementationsembedded softwareGCD algorithmsmodular inversesprime numbersRSA key generation

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Cryptography (94A60)

Recommendations

• New algorithm for classical modular inverse
• Computing the modular inverses is as simple as computing the GCDs
• Application of Euclid's algorithm to the computation of the inverse in modulo arithmetics
• The Montgomery inverse and its applications
• An efficient modulo p multiplication algorithm with moderate factors of p+1 and p-1

Cited in

(7)

• Application of Euclid's algorithm to the computation of the inverse in modulo arithmetics
• An algorithm for numerically inverting the modular \(j\)-function
• Computing the modular inverses is as simple as computing the GCDs
• A general method to decompose modular multiplicative inverse operators over group of units
• New algorithm for classical modular inverse
• The Euclidean algorithm as a sequence of modular inverse switching formulas
• Improvements to RSA key generation and CRT on embedded devices

This page was built for publication: GCD-free algorithms for computing modular inverses.

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