An average case efficient algorithm for solving two-variable linear Diophantine equations

Mayank Deora, Pinakpani Pal

Solving two-variable linear Diophantine equations has applications in many cryptographic protocols such as RSA and Elliptic curve cryptography. The Extended Euclid's algorithm is a…