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

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 the most widely used algorithm to solve these equations. We revisit two algorithms to solve two-variable linear Diophantine equations. We write the iterative version of one of the revisited algorithms. For another, we do a fine-grained analysis of the number of recursive calls and arrive at a periodic function that represents the number of recursive calls. We find the period and use it to derive an accurate closed-form expression for the average number of recursive calls incurred by that algorithm. We find multiple loose upper bounds on the average number of recursive calls in different cases based on whether a solution exists or not. We find that for a fixed value of $a,b$ and a varying $c$, such that the equation $ax+by=c$ (where $a > b$) is solvable, we can find the solution in $O\left(\frac{\log b}{gcd(a,b)}\right)$ average number of recursions or steps. We computationally evaluate this bound as well as one more upper bound and compare them with the average number of recursive calls in Extended Euclid's algorithm on a number of random $512$-bit inputs. We observe that the average number of iterations in the analyzed algorithm decreases with an increase in $gcd(a,b)$. We propose an iterative version of the algorithm. We implement this algorithm and find that the average number of iterations by our algorithm is less than that of two existing algorithms.