Cobertura mínima de bases para la prueba cuadrática de residuos de la cuadratura

11

Desafío

Encuentre la cubierta de bases más pequeña (p. Ej., Módulos) cuyos conjuntos de residuos cuadráticos se pueden probar mediante la búsqueda en la tabla para determinar definitivamente si un entero no negativo n es un cuadrado perfecto. Todas las bases deben ser menores o iguales a la raíz cuadrada del valor máximo de n .

La respuesta con el conjunto más pequeño de bases para una categoría dada de n gana el desafío. (Esto significa que potencialmente puede haber más de un ganador). Las categorías de n son:

         Category       Maximum allowed n    Maximum allowed modulus/base
    -------------    --------------------    ----------------------------
     8-bit values                     255                              15
    16-bit values                   65535                             255
    32-bit values              4294967295                           65535
    64-bit values    18446744073709551615                      4294967295

En el caso de un empate con dos conjuntos que tengan la misma cardinalidad, el empate irá al conjunto que tenga la mayor capacidad de detectar no cuadrados anteriormente en la secuencia.

En el caso de que no se encuentren cubiertas completas (lo cual es muy probable para las categorías de 32 bits y 64 bits), el ganador será el conjunto de bases que descarta estadísticamente o de forma comprobable el mayor porcentaje de no cuadrados (sin incorrectamente informar cuadrados como no cuadrados). Vea a continuación una discusión sobre portadas incompletas.

Antecedentes

En muchas aplicaciones de teoría de números, surge la pregunta de si algún número n es un cuadrado perfecto (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, etc.). Una forma de probar si n es cuadrado es probar si floor (√n) ² = n, es decir, si la raíz cuadrada redondeada hacia abajo de n , cuando está al cuadrado, devuelve n . Por ejemplo, floor (√123) ² = 11² = 121, que no es 123, entonces 123 no es cuadrado; pero piso (√121) ² = 11² = 121, entonces 121 es cuadrado. Este método funciona bien para números pequeños, especialmente cuando hay disponible una operación de raíz cuadrada de hardware. Pero para grandes números (cientos o miles de bits) puede ser muy lento.

Otra forma de probar la cuadratura es descartar no cuadrados utilizando tablas de residuos cuadráticos. Por ejemplo, todos los cuadrados en la base 10 deben tener un dígito final (un lugar) que sea 0, 1, 4, 5, 6 o 9. Estos valores forman el conjunto de residuos cuadráticos para la base 10. Entonces, si una base -10 número termina en 0, 1, 4, 5, 6 o 9, sabe que puede ser cuadrado, y se requerirá un examen más detallado. Pero si una base-10 termina en números 2, 3, 7, u 8, entonces puede estar seguro de que es no cuadrado.

Así que echemos un vistazo a otra base. Todos los cuadrados en la base 8 deben terminar en 0, 1 o 4, lo que convenientemente es solo 3 de 8 posibilidades, lo que significa un 37.5% de posibilidades de que un número aleatorio sea posiblemente cuadrado, o 62.5% de posibilidades de que un número aleatorio definitivamente no sea cuadrado. Esas son probabilidades mucho mejores que las que da la base 10. (Y tenga en cuenta que una operación de módulo de base 8 es simplemente una operación lógica y, en oposición al módulo de base 10, que es una división por 10 con el resto).

¿Hay incluso mejores bases? Bueno, sí, en realidad. Base 120 tiene 18 posibilidades (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100 y 105), lo que representa solo un 15% posibilidad de ser posiblemente cuadrada. Y la base 240 es mejor aún, con solo 24 posibilidades, lo que representa solo un 10% de posibilidades de ser cuadrado.

Pero ninguna base individual por sí sola puede determinar definitivamente la cuadratura (a menos que sea mayor que el número máximo que se está probando, lo cual es eminentemente poco práctico). Una sola base solo puede descartar la cuadratura; no puede verificar de manera concluyente la cuadratura. Solo un conjunto cuidadosamente seleccionado de bases, trabajando juntas, puede verificar de manera concluyente la cuadratura en un rango de enteros.

Entonces, la pregunta es: ¿qué conjunto de bases forma una cobertura mínima que, en conjunto, permite la deducción definitiva de la cuadratura o no cuadratura?

Ejemplo de una cobertura correcta pero no mínima

La cubierta de 16 bases {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} es suficiente para determinar definitivamente la cuadratura o no cuadratura de todos los valores de 16 bits de 0 a 65535. Pero no es una cobertura mínima , porque existe al menos una cubierta de 15 bases que también es fácilmente detectable. De hecho, es probable que existan cubiertas mucho más pequeñas, tal vez con tan solo 6 o 7 bases.

Pero a modo de ilustración, echemos un vistazo a la prueba de un valor de muestra de n con este conjunto de cubiertas de 16 bases. Estos son los conjuntos de residuos cuadráticos para el conjunto de bases anterior:

Base m   Quadratic residue table specific to base m
------   ----------------------------------------------------
   3     {0,1}
   4     {0,1}
   5     {0,1,4}
   7     {0,1,2,4}
   8     {0,1,4}
   9     {0,1,4,7}
  11     {0,1,3,4,5,9}
  13     {0,1,3,4,9,10,12}
  16     {0,1,4,9}
  17     {0,1,2,4,8,9,13,15,16}
  19     {0,1,4,5,6,7,9,11,16,17}
  23     {0,1,2,3,4,6,8,9,12,13,16,18}
  25     {0,1,4,6,9,11,14,16,19,21,24}
  29     {0,1,4,5,6,7,9,13,16,20,22,23,24,25,28}
  31     {0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28}
  37     {0,1,3,4,7,9,10,11,12,16,21,25,26,27,28,30,33,34,36}

Ahora probemos el número n = 50401 usando este conjunto de bases, convirtiéndolo en cada base. (Esta no es la forma más eficiente de examinar los residuos, pero es suficiente para fines explicativos). Es el lugar del 1 que nos interesa aquí (marcado entre paréntesis a continuación):

 Base                               "Digits" in base m
   m          m^9   m^8   m^7   m^6   m^5   m^4   m^3   m^2   m^1  ( m^0 )
 ----      -----------------------------------------------------------------
   3           2     1     2     0     0     1     0     2     0   (  1 ) ✓
   4                       3     0     1     0     3     2     0   (  1 ) ✓
   5                             3     1     0     3     1     0   (  1 ) ✓
   7                                   2     6     6     6     4   (  1 ) ✓
   8                                   1     4     2     3     4   (  1 ) ✓
   9                                         7     6     1     2   (  1 ) ✓
  11                                         3     4     9     5   ( 10 )
  13                                         1     9    12     3   (  0 ) ✓
  16                                              12     4    14   (  1 ) ✓
  17                                              10     4     6   ( 13 ) ✓
  19                                               7     6    11   ( 13 )
  23                                               4     3     6   (  8 ) ✓
  25                                               3     5    16   (  1 ) ✓
  29                                               2     1    26   ( 28 ) ✓
  31                                               1    21    13   ( 26 )
  37                                                    36    30   (  7 ) ✓

Entonces podemos ver que en 13 de estas bases, el residuo coincide con un residuo cuadrático conocido (llame a esto un "hit" en la tabla), y en 3 de estas bases, el residuo no coincide con un residuo cuadrático conocido (llame a esto un "perder"). Todo lo que se necesita es 1 error para saber que un número no es cuadrado, por lo que podríamos detenernos en 11, pero con fines ilustrativos, hemos examinado las 16 bases aquí.

Ejemplo de una portada incompleta

Técnicamente, una cubierta incompleta no es una cubierta, pero eso no viene al caso. El conjunto de bases {7, 8, 11, 15} cubre casi todos los valores de 8 bits de n de 0 a 255 correctamente, pero no del todo. En particular, identifica incorrectamente 60 y 240 como cuadrados (estos son falsos positivos), pero identifica correctamente todos los cuadrados reales (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 y 225) y no hace otros falsos positivos. Entonces, este es un conjunto de 4 que casi tiene éxito como solución, pero finalmente falla, porque una cubierta incompleta no es una solución válida.

Para 8-bit n , el conjunto de bases {7, 8, 11, 15} es uno de dos conjuntos de 4 bases que producen dos errores, y hay conjuntos siete de 4 bases que sólo producen un error. No existen conjuntos de 4 bases que formen una cobertura completa y precisa de valores de 8 bits. ¿Puedes encontrar un conjunto de 5 bases que no produzcan errores y cubran todos los valores de 8 bits correctamente? ¿O necesitas 6 o más? (Sé la respuesta para n de 8 bits , pero no la voy a revelar. No sé la respuesta para 16, 32 o 64 bits, y creo que incluso el 16- El caso de bits es imposible de resolver mediante la búsqueda de fuerza bruta. Resolver los casos de 32 bits y 64 bits ciertamente requerirá técnicas de búsqueda genéticas, heurísticas u otras.

Un comentario sobre números criptográficamente grandes

Más allá de los números de 64 bits, en los cientos o miles de dígitos binarios, aquí es donde una verificación rápida de la cuadratura es realmente útil, incluso si la cubierta está incompleta (lo que sin duda será para números realmente grandes). ¿Cómo podría ser útil una prueba como esta, incluso si no es lo suficientemente decisiva? Bueno, imagine que tuvo una prueba extremadamente rápida para la cuadratura que funcionó correctamente el 99.9% del tiempo y dio falsos negativos el 0.1% restante del tiempo y nunca dio falsos positivos. Con tal prueba, podría determinar la no cuadratura de un número casi al instante, y luego, en los casos excepcionales de indecisión, podría recurrir a un método más lento para resolver lo desconocido de una manera diferente. Esto te ahorraría bastante tiempo.

Por ejemplo, el conjunto {8, 11, 13, 15} es correcto el 99.61% del tiempo para valores de 8 bits de n de 0 a 255, es correcto el 95.98% del tiempo para valores de 16 bits de n de 0 a 65535, y es correcto el 95.62% del tiempo para valores de n de 24 bits de 0 a 16777215. A medida que n va al infinito, el porcentaje de corrección para este conjunto de bases disminuye, pero se acerca asintóticamente y nunca cae por debajo del 95.5944% exactitud.

Por lo tanto, incluso este conjunto muy pequeño de 4 bases pequeñas es útil para identificar casi de inmediato alrededor de 22 de los 23 números arbitrariamente grandes como no cuadrados, lo que evita la necesidad de una mayor inspección de esos números por métodos más lentos. Entonces, los métodos más lentos solo deben aplicarse en el pequeño porcentaje de casos que esta prueba rápida no puede descartar.

Es interesante observar que algunas bases de 16 bits logran más del 95% por sí solas. De hecho, cada una de las bases a continuación puede eliminar mejor que el 97% de todos los números hasta el infinito como no cuadrados. El conjunto de residuos cuadráticos para cada una de estas bases se puede representar como una matriz de bits empaquetados utilizando solo 8192 bytes.

Aquí están las 10 bases simples más poderosas de menos de 2 ^ 16

 Rank   Base    Prime factorization       Weeds out
 ----   ------------------------------    ---------
  1.    65520 = 2^4 x 3^2 x 5 x 7 x 13      97.95%
  2.    55440 = 2^4 x 3^2 x 5 x 7 x 11      97.92%
  3.    50400 = 2^5 x 3^2 x 5^2 x 7         97.56%
  4.    52416 = 2^6 x 3^2 x 7 x 13          97.44%
  5.    61200 = 2^4 x 3^2 x 5^2 x 17        97.41%
  6.    44352 = 2^6 x 3^2 x 7 x 11          97.40%
  7.    63360 = 2^7 x 3^2 x 5 x 11          97.39%
  8.    60480 = 2^6 x 3^3 x 5 x 7           97.38%
  9.    63840 = 2^5 x 3 x 5 x 7 x 19        97.37%
 10.    54720 = 2^6 x 3^2 x 5 x 19          97.37%

¿Ves algo interesante que todas estas bases tengan en común? No hay razón para pensar que podrían ser útiles en combinación (tal vez lo sean, tal vez no lo sean), pero aquí hay algunas buenas pistas sobre qué bases pueden ser más influyentes para las categorías más grandes de números.

Desafío secundario: una de las bases más influyentes (si no la más) hasta 2 ^ 28 es 245044800, que solo puede eliminar correctamente el 99.67% de los no cuadrados, o alrededor de 306 de 307 números aleatorios arrojados. ¿Puedes encontrar la base única más influyente de menos de 2 ^ 32?

Relacionado

Hay algunas ideas muy buenas en las siguientes preguntas que están estrechamente relacionadas, así como varios trucos de microoptimización para acelerar ciertas operaciones. Aunque las preguntas vinculadas no se proponen específicamente para encontrar el conjunto de bases más sólido, la idea de bases sólidas es implícitamente central en algunas de las técnicas de optimización utilizadas allí.

Todd Lehman
fuente
¿Cómo determinará el desempate antes de probar cada número en el rango dado y contar cuántas verificaciones se realizaron en total?
Martin Ender
Veré la cardinalidad de los conjuntos de residuos cuadráticos para cada base. Por ejemplo, 4 es una mejor base que 3, porque solo la mitad de los valores del módulo 4 son residuos cuadráticos, mientras que dos tercios de los valores del módulo 3 son residuos cuadráticos. Por lo tanto, 4 tiene una mayor capacidad para eliminar números antes. La peor base es 2, porque no puede descartar ningún número, y la mejor base menor que 256 es 240, que es capaz de descartar el 90% de los números. Puede que tenga que hacer un muestreo de Monte Carlo para bases realmente grandes.
Todd Lehman
Sí, eso tiene sentido. ¿Pero decidirá el empate solo por la primera base cuya probabilidad difiere, o cómo calculará la eficiencia de todo el conjunto en función de las probabilidades? También estoy pensando que las probabilidades ya no son independientes una vez que haya verificado otras bases.
Martin Ender
2
En el caso de n espacios grandes , creo que tendré que decidir el empate en función de la eficiencia global estimada, calculada multiplicando las probabilidades predichas por cada conjunto de residuos. Por ejemplo, las bases {8,11,13,15} tienen probabilidades de 0.375, 0.545455, 0.538462 y 0.4, respectivamente, que se multiplican por 0.044056. Restando de 1, esto da 0.955944, lo que concuerda muy de cerca con el resultado de conteo exhaustivo de 95.62% medido sobre todo n en [0,2 ^ 24-1].
Todd Lehman

Respuestas:

7

Mathematica

Realmente no sé mucho sobre teoría de números (desafortunadamente), así que este es un enfoque bastante ingenuo. Estoy usando un algoritmo codicioso que siempre agrega la base que tiene más errores para los números restantes.

bits = 8
Timing[
 maxN = 2^bits - 1;
 maxBase = 2^(bits/2) - 1;
 bases = {
     #,
     Union[Mod[Range[0, Floor[#/2]]^2, #]]
     } & /@ Range[3, maxBase];
 bases = SortBy[bases, Length@#[[2]]/#[[1]] &];
 numbers = {};
 For[i = 0, i <= Quotient[maxN, bases[[1, 1]]], ++i,
  AppendTo[numbers, # + i*bases[[1, 1]]] & /@ bases[[1, 2]]
  ];
 While[numbers[[-1]] > maxN, numbers = Most@numbers];
 numbers = Rest@numbers;
 i = 0;
 cover = {bases[[1, 1]]};
 lcm = cover[[-1]];
 Print@cover[[1]];
 While[Length@numbers > maxBase,
  ++i;
  bases = DeleteCases[bases, {b_, r_} /; b\[Divides]lcm];
  (*bases=SortBy[bases,(Print[{#,c=Count[numbers,n_/;MemberQ[#[[2]],
  Mod[n,#[[1]]]]]}];c)&];*)
  bases = SortBy[
    bases,
    (
      n = Cases[numbers, n_ /; n < LCM[#[[1]], lcm]];
      Count[n, n_ /; MemberQ[#[[2]], Mod[n, #[[1]]]]]/Length@n
      ) &
    ];
  {base, residues} = bases[[1]];
  numbers = Cases[numbers, n_ /; MemberQ[residues, Mod[n, base]]];
  AppendTo[cover, base];
  lcm = LCM[lcm, base];
  Print@base
  ];
 cover
 ]

Resuelve 8 bits en poco tiempo con las siguientes 6 bases:

{12, 13, 7, 11, 5, 8}

16 bits toma 6s y da como resultado la siguiente cubierta de 6 bases:

{240, 247, 253, 119, 225, 37}

Para los casos más grandes, este enfoque obviamente se queda sin memoria.

Para ir más allá de 16 bits, necesitaré encontrar una manera de verificar que una cubierta esté completa sin tener que mantener una lista de todos los números hasta N max (o ir y aprender sobre la teoría de números).

Editar: Tiempo de ejecución reducido para 16 bits de 66 a 8 s al rellenar previamente la lista de números con solo aquellos que no están descartados por la base más efectiva. Esto también debería mejorar significativamente la huella de la memoria.

Editar: agregué dos optimizaciones menores para reducir el espacio de búsqueda. No es una de las categorías oficiales, pero con eso encontré una cubierta de 8 bases para 24 bits en 9.3 horas:

{4032, 3575, 4087, 3977, 437, 899, 1961, 799}

En cuanto a las optimizaciones, ahora estoy omitiendo todas las bases que dividen el LCM de las bases que ya están en la cubierta, y cuando pruebo la eficiencia de una base, solo lo pruebo contra los números hasta el LCM de esa nueva base y todas las bases que ya tener.

Martin Ender
fuente
1
@ToddLehman No sé si viste mi primera solución antes de editarla con la codiciosa. (Echa un vistazo al historial de edición si no lo hiciste). Allí solo estaba escogiendo bases por su proporción general de aciertos / errores hasta que tuve una cobertura completa. Eso produjo 8 bases para 8 bits y 29 bases para 16 bits. : D
Martin Ender
1
@ToddLehman ¡Gracias por las pruebas! :) Me pregunto qué podrían hacer las personas con conocimientos reales de teoría de números. Tengo un par de ideas para acelerarlo, así que podría ir a 24 bits, pero creo que necesito concentrarme en conseguir mi próximo desafío en la pista.
Martin Ender
1
@ToddLehman Hay una cubierta de 24 bits para ti. Ya me preguntaba si podría hacer uso de los factores primos, pero aún no he encontrado la heurística decente. Todo lo que puedo hacer es mejorar el orden en que se prueban las bases, pero aún no estoy seguro de cuándo podría abortar eso.
Martin Ender
1
@ToddLehman No es necesario que me etiquetes en mis propias publicaciones, ya que de todos modos recibiré una notificación. Es por eso que SE deshabilita el autocompletado hasta que haya comentarios de múltiples usuarios, donde podría tener sentido abordar el OP específicamente.
Martin Ender
1
Acabo de encontrar una cubierta de 9 bases para 28 bits: {15840, 15827, 16211, 12549, 14911, 15111, 9869, 14647, 16043}. El tiempo de ejecución fue de 36.5 minutos, usando un programa C optimizado para evaluar la aptitud usando operaciones bit a bit con algoritmo codicioso. Este conjunto de 9 bases es una cubierta perfecta para números de menos de 2²⁸, y tiene una precisión del 99.999983% para números en el rango de 2⁶⁴.
Todd Lehman