El algoritmo de Bach [1] es un algoritmo de tiempo polinomial probabilístico para generar números aleatorios junto con sus factorizaciones , que lleva el nombre de su descubridor, Eric Bach . Es interesante porque no se conoce ningún algoritmo que factorice números de manera eficiente, por lo que el método sencillo, es decir, generar un número aleatorio y luego factorizarlo, no es práctico.
El algoritmo realiza, en expectativa, pruebas de primalidad O (log n) .
Un algoritmo más simple, pero menos eficiente (que realiza, con expectativa, pruebas de primordialidad), se debe a Adam Kalai . [2]
Descripción general
El algoritmo de Bach produce un número uniformemente al azar en el rango (para una entrada dada ), junto con su factorización. Lo hace eligiendo un número primo y un exponente tal que , según una determinada distribución. Luego, el algoritmo genera de forma recursiva un número en el rango , dónde , junto con la factorización de . Luego establecey agrega a la factorización de para producir la factorización de . Esto dacon distribución logarítmica sobre el rango deseado; A continuación, se utiliza el muestreo de rechazo para obtener una distribución uniforme.
Referencias
- ^ Bach, Eric (1988), "Cómo generar números aleatorios factorizados", SIAM Journal on Computing , 17 (2): 179-193, doi : 10.1137 / 0217012 , MR 0935336
- ^ Kalai, Adam (2003), "Generación fácil de números factorizados aleatorios", Journal of Cryptology , 16 (4): 287–289, doi : 10.1007 / s00145-003-0051-5 , MR 2002046
Otras lecturas
- Bach, Eric . Métodos analíticos en el análisis y diseño de algoritmos teóricos de números , MIT Press, 1984. Capítulo 2, "Generación de factorizaciones aleatorias", parte del cual está disponible en línea aquí .