La prueba de primalidad puede no ser una “teoría científica” per se, pero es un problema MUY IMPORTANTE y significativo que domina muchas teorías científicas y criptografía . Casi todos los algoritmos de prueba de primalidad propuestos hasta la fecha (excepto probablemente uno) son incondicionalmente no deterministas (probabilísticos).
Prueba de primalidad de Miller-Rabin
Esta prueba de primalidad de un número entero se basa en un modelo probabilístico. Su versión original, debido a Gary L. Miller, es determinista, pero el determinismo se basa en la hipótesis generalizada de Riemann no probada. Michael O. Rabin lo modificó para obtener un algoritmo probabilístico incondicional.
Es, con mucho, la prueba de primalidad más utilizada en competiciones de codificación y tareas de programación, debido a su buen tiempo de ejecución y facilidad de codificación. De hecho, antes de que se propusiera la prueba de primalidad AKS en 2002, todas las soluciones al problema de la prueba de primalidad eran incondicionalmente no deterministas (probabilísticas) o deterministas suponiendo alguna hipótesis o conjetura no probada (pero ampliamente aceptada).
- En la investigación ecológica, ¿qué fuentes cuentan como citables?
- ¿Qué es lo último en tecnología de nanotubos de carbono?
- ¿Cómo se interpreta el valor p y el estadístico t para determinar si una cifra es significativa?
- ¿Qué rama del ejército / gobierno de EE. UU. Realiza la investigación científica más secreta?
- ¿Por qué la química orgánica es tan competitiva a nivel de investigación universitaria?
Citando Wikipedia
AKS es el primer algoritmo de prueba de primalidad que es simultáneamente general , polinomial , determinista e incondicional . Los algoritmos anteriores se habían desarrollado durante siglos, pero lograron tres de estas propiedades como máximo, pero no las cuatro.
