Computing the modular inverses is as simple as computing the GCDs (Q2469471)

The authors propose a new algorithm being a variation of the Euclidean Algorithm (EA), used to calculate the greatest common divisors (GCDs) of two integers and inverses for polynomials. They prove some essential features of their new version of EA and show usefulness of their proposal in cryptographic systems. The authors claim that their version (Variation on Euclidean Algorithm -- VEA), which uses only simple modulo operators, can be in some cases, simpler and faster, as compared to the Extended Euclidean Algorithm (EEA). VEA can be used to compute GCDs and modular inverses. It turns out that the new variant modifies the initial values and the termination condition of the EEA, leaving the computing of modular inverses as simple as computing the GCDs. At the same time, the authors, also point out some drawbacks of their proposal, especially longer input streams, that must be twice the size in the bit length as inputs of the EEA, leading to some limits of possible VEA applications.