Algoritmo de comprobación más eficaz para la ecuación de Pell

Question

¿Cuál es la forma más eficiente desde el punto de vista computacional para comprobar, dado $x,y,D$ que satisfagan la ecuación de Pell (positiva o negativa) ( $x^2-Dy^2=1$ )? (Obviamente la pregunta se refiere a valores muy grandes de $x,y,D$ .)

Sé (creo) que tendrá que ser la comprobación de mod $p$ pero no puedo encontrar el equilibrio adecuado entre el tiempo de cálculo requerido para la factorización $x,y$ o $D$ y cálculos de fuerza bruta.

Actualización: Lo que dije sobre el mod $p$ tenía que ver con el hecho de que pensaba que con Pell especialmente podría haber alguna forma computacionalmente eficiente de obtener un conjunto distinguido de primos (y entonces la cuestión era cómo equilibrar mejor el "hallazgo" con la modulación) - pero como indica Carnahan el caso podría no ser más especial que el de evaluar cualquier binomio. Creo que lo que dice Carnahan lo cubre bastante, aunque me interesaría saber cómo se obtienen esos límites en el número de operaciones. Además, ¿realmente se deduce que no hay una forma más eficiente de evaluar un posible triple "cercano" (es decir, uno que haya pasado una prueba de mod-pequeño-primo o log) que utilizar algoritmos de multiplicación? ¿Es eso evidente?

Answer 1

En base a los comentarios, parece que no es una pregunta específica de la ecuación de Pell, y que sólo quieres evaluar una única binomial con entradas grandes lo más rápido posible.

Si compruebas la ecuación directamente utilizando algoritmos de multiplicación rápida (p. ej, Schönhage-Strassen ), se puede esperar que el cálculo requiera alrededor de $(\log z )\cdot (\log \log z)$ operaciones, donde $z = \max \{ x, y, D \}$ .

Si quiere encontrar rápidamente una respuesta negativa, puede comprobar los tamaños relativos y los dígitos iniciales, y luego intentar la reducción en módulo de enteros pequeños. Si empiezas con una respuesta negativa al azar, puedes esperar que se elimine después de, como mucho, unas pocas divisiones (es decir, alrededor de $\log z$ operaciones).

Para encontrar una respuesta positiva utilizando la aritmética modular, se puede utilizar el Teorema del resto chino . Para demostrar que la identidad es válida, basta con comprobarla en el módulo $n$ , para $n$ que se extiende sobre una colección de enteros positivos cuyo mínimo común denominador es mayor que $x^2$ y $Dy^2$ . Es común comprobar el módulo de una gran colección de primos pequeños, y esto requerirá alrededor de $\log z$ primos y $(\log z)^2$ operaciones. Otra opción natural con un ordenador binario son los números de Fermat, de la forma $2^{2^n}+1$ Ya que la división con el resto se puede optimizar, esto acaba pareciéndose mucho al cálculo directo.

En resumen, la ventaja de comprobar el módulo de primos pequeños es que permite eliminar rápidamente las respuestas negativas, y la desventaja es que (si no me equivoco) es aproximadamente cuadráticamente más lento que el cálculo directo cuando se tiene una respuesta positiva. Puedes elegir tu método dependiendo del tipo de cálculo que planees hacer.

Answer 2

Vea mi respuesta en:

Límite superior de la longitud del período de la representación de la fracción continua de la raíz cuadrada de un número muy compuesto

En lugar de utilizar fracciones continuas para resolver la ecuación de Pell en primer lugar, necesitando así números reales de alta precisión repetidamente, y necesitando un medio para comprobar la solución al final, uno puede hacer todo el proceso en formas cuadráticas binarias "reducidas".

La información adicional utilizada, sobre la respuesta anterior publicada, es que las pequeñas matrices de 2 por 2 (en la respuesta las llamo $R$ ) muestran cómo actualizar su $(x,y)$ par. Al final del "ciclo", se ha vuelto a la forma reducida $(1, 2 a_0, a_0^2 - n).$ El producto de todos los $R$ matrices para dar un automorfo de esa forma, en particular la columna de la izquierda son las primeras $(x,y)$ tal que $x^2 + 2 a_0 x y + (a_0^2 - n) y^2 = 1.$ Todo lo que necesitas ahora es retirarte, $( x + a_0 y)^2 - n y^2 = 1.$ Aquí $a_0^2 < n < (a_0 + 1)^2.$

Aquí hay una muestra de mi ordenador de casa. Estoy asumiendo que tienes aritmética de enteros de precisión arbitraria, yo no.

Mi propio programa no es exactamente lo que he descrito, doy un automorfo separado para el formulario original de Pell $x^2 - n y^2$ Si quieres el programa en C++, házmelo saber.

Como puedes ver, la entrada superior derecha del automorfo Pell está sobredimensionada para C++, tuve que rellenar a mano 61 * 226153980 y otros valores.

phoebus:~/Cplusplus> ./Pell
Input n for Pell
61

0  form   1 14 -12   delta  -1
1  form   -12 10 3   delta  4
2  form   3 14 -4   delta  -3
3  form   -4 10 9   delta  1
4  form   9 8 -5   delta  -2
5  form   -5 12 5   delta  2
6  form   5 8 -9   delta  -1
7  form   -9 10 4   delta  3
8  form   4 14 -3   delta  -4
9  form   -3 10 12   delta  1
10  form   12 14 -1   delta  -14
11  form   -1 14 12   delta  1
12  form   12 10 -3   delta  -4
13  form   -3 14 4   delta  3
14  form   4 10 -9   delta  -1
15  form   -9 8 5   delta  2
16  form   5 12 -5   delta  -2
17  form   -5 8 9   delta  1
18  form   9 10 -4   delta  -3
19  form   -4 14 3   delta  4
20  form   3 10 -12   delta  -1
21  form   -12 14 1   delta  14
22  form   1 14 -12

 disc   244

Automorph, written on right of Gram matrix:
 -183241189   -2713847760
 -226153980   -3349396909 

 Pell automorph
-1766319049  -13795392780
 -226153980   -1766319049

Pell unit
1766319049^2 - 61 * 226153980^2 = 1

=========================================
phoebus:~/Cplusplus>

Answer 3

Seguramente depende de la situación. Si está convencido de que efectivamente $x^2-Dy^2=1$ pero tiene que aportar una prueba, y no tiene ningún conocimiento especial sobre $x,y,D$ entonces no estoy seguro de que algo sea más rápido que un cálculo directo. Puedes comprobar $\mod m$ para varios $m$ . No hay necesidad de $m$ para ser primo. Si los números se proporcionan en decimal entonces sería fácil de comprobar $\mod 10^k+1$ o $10^k-1.$ Si conoce la solución básica $x_0^2-Dy_0^2=1$ entonces podrías averiguar la potencia correcta $t$ , si es que hay alguno con $(x_0+\sqrt{D}y_0)^t=x+\sqrt{D}y$ y hacer una potencia efectiva al cuadrado para ver si funciona. Se podría elegir una base $b$ y y comprobar $\mod b^i$ para $i=1,2,3,\cdots$ hasta $b^i$ es lo suficientemente grande. En caso de que no sea cierto, podría descubrirlo rápidamente. Si es cierto, puede que no sea más rápido que el cálculo directo.