Sí. La originalidad es una pregunta mucho más fácil que la factorización, dado el conocimiento actual.
Factorizar números de 200 dígitos no es imposible hoy en día, pero es bastante desalentador incluso con el software más avanzado. Realizar pruebas de primalidad de números de 200 dígitos es extremadamente fácil: menos de 1 segundo para un software decente. Probar números primos de 1000 dígitos no es un desafío en absoluto con un buen software, pero factorizar números generales de 1000 dígitos no es factible incluso en el futuro cercano.
Las pruebas de composición como las pruebas de Fermat, Euler, Miller-Rabin, Frobenius, etc. (y combinaciones como la prueba BPSW) se han utilizado durante bastante tiempo y son polinomiales en el tamaño de entrada, son simples y muy rápidas. Se basan en señalar que existen ecuaciones modulares que son verdaderas para todos los números primos, pero falsas para muchos compuestos. Si bien dan los resultados “compuesto” y “probablemente primo”, podemos hacer que la parte “probablemente” sea extremadamente improbable, lo suficientemente bueno para cualquier persona que no sean matemáticos. BPSW todavía no tiene un contraejemplo conocido 36 años después de que comenzó a usarse, por ejemplo. Utilizando datos empíricos y pruebas exhaustivas, también es posible hacer algunos de estos deterministas por debajo de un tamaño determinado (por ejemplo, se ha demostrado que BPSW no tiene contraejemplos para ningún número de 64 bits, que es enorme o pequeño dependiendo de sus pasatiempos).
- ¿Qué preguntas debe hacer a los usuarios sobre una aplicación móvil en el lanzamiento para obtener los mejores y más útiles comentarios?
- ¿Cuál es el proceso para obtener una pasarela de pago para una aplicación móvil en India?
- ¿Qué SDK de análisis de datos y comportamiento de aplicaciones recomienda para el desarrollo de iOS?
- ¿Qué país de habla inglesa es el mejor para lanzar una aplicación beta móvil y por qué?
- ¿Cuáles son las versiones de Python y cuál es la más fácil de aprender? ¿Y cuál es el mejor para el desarrollo de aplicaciones de Android?
En 1975, Brillhart, Lehmer y Selfridge publicaron un artículo que recopilaba resultados anteriores y mostraba muchos métodos nuevos para probar la primalidad basados en factorizaciones parciales de N-1 y / o N + 1. Es decir, si pudiéramos encontrar suficientes factores de N-1, no completos, pero solo hasta la raíz cúbica, sería suficiente. Ahora, esto no escala ya que todavía depende de la factorización, pero (1) N-1 o N + 1 pueden ser fáciles de factorizar, y (2) solo lo necesitamos factorizado parcialmente. Si bien este método obviamente usa la factorización, los siguientes tres no.
La prueba de primalidad APR-CL (llamada así por sus autores originales y de mejora) comenzó a usarse en los años 80 y todavía se usa. No es el tiempo polinómico en la entrada, pero sí lo es: el exponente se basa en log (log (log (n))), que es esencialmente una pequeña constante para cualquier tamaño n que estaríamos utilizando. Todavía se usa hoy, especialmente en Pari / GP, pero también en un par de proyectos de código abierto.
ECPP (Elliptic Curve Primality Proving) se publicó a principios de la década de 1990 y sigue siendo el método más utilizado para grandes aportes generales en la actualidad. Las pruebas de primalidad de números de 10,000 dígitos usando Primo (una implementación gratuita de última generación) no es inusual, y los resultados más grandes son más de 30,000 dígitos. Es el tiempo polinómico esperado . Es decir, la aleatoriedad está involucrada, y no podemos dar una garantía matemática de que terminará en el tiempo esperado. En la práctica lo hace de manera confiable. Tenga en cuenta que la aleatoriedad aquí no tiene nada que ver con la respuesta: las dos únicas respuestas son “definitivamente compuesto” y “definitivamente primo, y aquí hay un certificado”. El certificado le permite a un tercero usar varios programas para verificar la originalidad revisando todas las matemáticas utilizadas. Ese proceso es determinista, polinómico y muy rápido.
AKS es un algoritmo determinista de tiempo polinómico para la primalidad. Se resolvió la cuestión de si la primalidad estaba en P, y por lo tanto se demostró que era “fácil”. En la práctica, nadie usa AKS porque los dos métodos anteriores son mucho, mucho, mucho más rápidos.
