Efficient Approaches to Solving Quadratic Diophantine Equations and their Time Complexity - Tamang, Bal Bahadur; Singh, Ajaya (Journal of Nepal Mathematical Society, 2024)
In this paper, we present an efficient approach to solving quadratic Diophantine equations and analyze their time complexity. We propose a deterministic polynomial-time algorithm that provides an upper bound on the elementary operations required to solve such equations. We also present a non-deterministic polynomial-time algorithm for the construction of quadratic non-resiude modulo d, which is a more efficient alternative to the deterministic approach.