La prueba cuadrática de Frobenius ( QFT ) es una prueba de primalidad probabilística para probar si un número es un número primo probable . Lleva el nombre de Ferdinand Georg Frobenius . La prueba utiliza los conceptos de polinomios cuadráticos y el automorfismo de Frobenius . No debe confundirse con la prueba de Frobenius más general que utiliza un polinomio cuadrático: la QFT restringe los polinomios permitidos en función de la entrada y también tiene otras condiciones que deben cumplirse. Un compuesto que pasa esta prueba es un pseudoprime de Frobenius , pero lo contrario no es necesariamente cierto.
Concepto
El objetivo declarado de Grantham al desarrollar el algoritmo era proporcionar una prueba de que los primos siempre pasarían y los compuestos pasarían con una probabilidad de menos de 1/7710. [1] : 33
Más tarde, Damgård y Frandsen ampliaron la prueba a una prueba llamada prueba cuadrática extendida de Frobenius (EQFT). [2]
Algoritmo
Sea n un entero positivo tal que n sea impar, y , dónde denota el símbolo de Jacobi . Colocar. Entonces, un QFT en n con parámetros ( b , c ) funciona de la siguiente manera:
- (1) Pruebe si uno de los primos es menor o igual al menor de los dos valores y divide n . Si es así, deténgase ya que n es compuesto.
- (2) Pruebe si . Si es así, deténgase ya que n es compuesto.
- (3) Calcular . Si luego deténgase ya que n es compuesto.
- (4) Calcular . Si luego deténgase ya que n es compuesto.
- (5) Deja con s impar. Si , y para todos , luego deténgase ya que n es compuesto.
Si el QFT no se detiene en los pasos (1) - (5), entonces n es un número primo probable.
(La notación significa que , donde H y K son polinomios).
Ver también
Referencias
- ^ Grantham, J. (1998). "Una prueba principal probable con alta confianza". Revista de teoría de números . 72 (1): 32–47. CiteSeerX 10.1.1.56.8827 . doi : 10.1006 / jnth.1998.2247 .
- ^ Damgård, Ivan Bjerre ; Frandsen, Gudmund Skovbjerg (2003). Una prueba de primalidad de Frobenius cuadrática extendida con estimaciones de error promedio y en el peor de los casos (PDF) . Apuntes de conferencias en informática . Fundamentos de la teoría de la computación. 2751 . Springer Berlín Heidelberg. págs. 118-131. doi : 10.1007 / 978-3-540-45077-1_12 . ISBN 978-3-540-45077-1. ISSN 1611-3349 .