Я только что перенес алгоритм с www.numbertheory.org для выполнения этого из PHP в Python, используя SymPy (произвольная точность) или Numpy (быстрее, но страдает от целочисленного переполнения), который вы можете найти здесь https://github.com/tclose/Diophantine. Это достаточно быстро в зависимости от размера вашей системы.
Я бы порекомендовал использовать ветку SymPy, несмотря на то, что она немного медленная.Если производительность является проблемой, вы, вероятно, могли бы ускорить ее, используя интерпретатор PyPy, как написано на чистом python.