Calculation of Bezout’s coefficients for the k-ary algorithm of finding GCD
| Autor: | B. G. Mubarakov, Kamal Al-Anni Maad, Sh. T. Ishmukhametov |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Binary GCD algorithm Mathematics::Commutative Algebra Modular arithmetic Mathematics::General Mathematics General Mathematics Mathematics::Rings and Algebras 010102 general mathematics 02 engineering and technology 01 natural sciences Lehmer's GCD algorithm Computer Science::Robotics Euclidean algorithm Number theory 0202 electrical engineering electronic engineering information engineering Greatest common divisor Multiplicative inverse Computer Science::Symbolic Computation 020201 artificial intelligence & image processing 0101 mathematics Linear combination Algorithm Mathematics |
| Zdroj: | Russian Mathematics. 61:26-33 |
| ISSN: | 1934-810X 1066-369X |
| DOI: | 10.3103/s1066369x17110044 |
| Popis: | Bezout’s equation is a representation of the greatest common divisor d of integers A and B as a linear combination Ax + By = d, where x and y are integers called Bezout’s coefficients. The task of finding Bezout’s coefficients has numerous applications in the number theory and cryptography, for example, for calculation of multiplicative inverse elements in modular arithmetic. Usually Bezout’s coefficients are caclulated using the extended version of the classical Euclidian algorithm. We elaborate a new algorithm for calculating Bezout’s coefficients based on the k-ary GCD algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink