Extended Euclidean algorithm and CRT algorithm

DOI10.2478/V10037-012-0020-2MaRDI QIDQ2852154zbMATH OpenOpenAlexFDO

Authors Hiroyuki Okazaki, Yosiki Aoki, Yasunari Shidama

Publication date 8 October 2013

Published in Formalized Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2478/v10037-012-0020-2

Mathematics Subject Classification ID

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Computational number theory (11Y99)

Recommendations

• Basic algorithms in number theory
• Maximum number of steps taken by modular exponentiation and Euclidean algorithm
• On the complexity of the extended Euclidean algorithm (extended abstract)
• Acceleration of Euclidean Algorithm and Rational Number Reconstruction
• Euclid's algorithm, Guass' elimination and Buchberger's algorithm

Cites work

• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• Semantics of MML query -- ordering

Cited in

(5)

• Maximum number of steps taken by modular exponentiation and Euclidean algorithm
• New binary Euclidean algorithms
• Extended Euclid's Algorithm via Backward Recurrence Relations
• The extended Euclidean algorithm provides optimal Bézout numbers
• Verified program extraction in number theory: the fundamental theorem of arithmetic and relatives

Describes a project that uses

Uses Software

• NZMATH

This page was built for publication: Extended Euclidean algorithm and CRT algorithm

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