Существует математическое решение, которое быстро находит a и b даже при больших значениях c.
К сожалению, не все так просто. Я пытаюсь дать краткое объяснение алгоритма. Надеюсь, это не слишком запутанно.
Так как дано c, и вы ищете a и b, вы в основном хотите решить диофантов
уравнения вида
n=x^2+y^2,
где n задано. Не сильно помогает то, что n = c * c - квадрат, и поэтому я описываю решение для любого n. Если бы n было простым числом, то вы могли бы использовать
Теорема Ферма , чтобы решить, разрешимо ли ваше уравнение, и использовать, как указал Морон, алгоритм Эрмита-Серре, чтобы найти решения, если таковые имеются.
Чтобы решить случай, когда n не простое, полезно использовать
Гауссовы целые числа . (Гауссовы целые числа - это просто комплексные числа с целыми коэффициентами). В частности, отмечается, что норма для x + yi равна
N(x+yi) = x^2+y^2.
Следовательно, нужно найти гауссовы целые числа x + yi, норма которых равна n.
Поскольку норма является мультипликативной, достаточно решить это уравнение для факторов n, а затем умножить гауссовы целые числа индивидуальных уравнений.
Позвольте мне привести пример. Мы хотим решить
65 = x^2 + y^2.
Это эквивалентно нахождению x, y такого, что
N(x+yi) = 65
над гауссовыми целыми числами. Фактор 65 = 5 * 13, затем мы используем Ферма, чтобы отметить, что оба
5 и 13 могут быть представлены как сумма двух квадратов. Наконец, мы находим либо с помощью грубой силы с помощью алгоритма Эрмита-Серре
N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13
Обратите внимание, я не учел целые числа Гаусса 2-i, -2 + i и т. Д. С отрицательными коэффициентами.
Это, конечно, тоже решения.
Следовательно, теперь мы можем умножить эти решения вместе, чтобы получить
65 = 5 * 13 = N (2 + i) * N (2 + 3i) = N ((2 + i) * (2 + 3i)) = N (1 + 8i)
и
65 = 5 * 13 = N (2 + i) * N (3 + 2i) = N ((2 + i) * (3 + 2i)) = N (4 + 7i).
Следовательно, каждый получает два решения
1*1 + 8*8 = 65
4*4 + 7*7 = 65
Другие комбинации, например с отрицательными коэффициентами тоже нужно проверять.
Они не дают новых решений, кроме перестановок и измененных знаков.
Чтобы вычислить все решения, можно также добавить, что нет необходимости когда-либо вычислять c * c.
Найти факторы с - это все, что необходимо. Кроме того, поскольку a и b оба меньше, чем c, не произойдет, что произведения целых гауссовских чисел не будут представлены с 64-битными целочисленными коэффициентами. Следовательно, если соблюдать осторожность, 64-разрядного целого числа достаточно, чтобы решить проблему. Конечно, всегда проще использовать такой язык, как Python, который не имеет таких проблем переполнения.