Hay una solución matemática que encuentra ayb incluso para valores grandes de c. Desafortunadamente, no es tan simple. Estoy tratando de dar una breve explicación del algoritmo. Espero que no sea demasiado confuso.
Dado que se da c y que busca para a y b, que básicamente quiere resolver diophantine ecuaciones de la forma
n=x^2+y^2,
donde se da n. No ayuda mucho que n = c * c sea un cuadrado y, por lo tanto, estoy describiendo una solución para cualquier n. Si n fuera un número primo, entonces podría usar Fermat's theorem, para decidir si su ecuación es solvente y usarla, ya que Moron señaló el algoritmo Hermite-Serret para encontrar las soluciones, si las hubiera. Para resolver el caso donde n no es primo, es una buena idea usar Gaussian integers. (Los enteros gaussianos son solo números complejos con coeficientes integrales). En particular, se observa que la norma de x + yi es
N(x+yi) = x^2+y^2.
Por lo tanto uno tiene que encontrar los enteros de Gauss x + yi cuya norma es n. Dado que la norma es multiplicativa, es suficiente resolver esta ecuación para los factores de ny luego multiplicar los enteros gaussianos de las ecuaciones indivi-duales. Déjeme dar un ejemplo. Queremos resolver
65 = x^2 + y^2.
Esto es equivalente a encontrar x, y de tal manera que
N(x+yi) = 65
lo largo de los enteros de Gauss. Factorizamos 65 = 5 * 13, luego usamos Fermat para notar que ambos 5 y 13 se pueden representar como suma de dos cuadrados. Por último, nos encontramos ya sea mediante el uso de la fuerza bruta de mediante el algoritmo de Hermite-Serret
N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13
Nota, He dejado de lado los números enteros Gaussion 2-i, -2 + i, etc con coeficientes negativos. Esas son, por supuesto, soluciones también.
Por lo tanto ahora podemos multiplicar estas soluciones en conjunto para obtener
65 = 5 * 13 = N (2 + i) * N (2 + 3i) = N ((2 + i) * (2 + 3i)) = N (1 + 8i)
y
65 = 5 * 13 = N (2 + i) * N (3 + 2i) = N ((2 + i) * (3 + 2i)) = N (4 + 7i).
Por lo tanto, se obtiene las dos soluciones
1*1 + 8*8 = 65
4*4 + 7*7 = 65
las otras combinaciones, por ejemplo, con coeficientes negativos deben ser revisados también. No dan nuevas soluciones que no sean permutaciones y signos modificados.
Para calcular todas las soluciones también se podría agregar que no es necesario calcular c * c. Encontrar los factores de c es todo lo que es necesario. Además, como a y b son ambos menores que c, no sucederá que los productos de números enteros gaussianos no sean representables con coeficientes enteros de 64 bits. Por lo tanto, si uno es cuidadoso, el entero de 64 bits es suficiente precisión para resolver el problema. Por supuesto, siempre es más fácil usar un lenguaje como Python que no tiene este tipo de problemas de desbordamiento.
Solo para agregar a esto: Para calcular los factores gaussianos de números primos de la forma 4n + 1, use el algoritmo Hermite-Serret. Los primos de la forma 4n + 3 son primos gaussianos, por lo que ya no es necesario factorizarlos. –
Sí, de hecho. Muchas gracias. He agregado el algoritmo Hermite-Serret a mi respuesta. – Accipitridae