Test de Pocklington

Test de Pocklington

El test de Pocklington es un test de primalidad para cierto conjunto de números inventado por Henry Cabourn Pocklington en 1914.[1]

Sea N = fr + 1 donde 0 < r < f+2 y se conocen todos los factores primos de f. El teorema sostiene que N es un número primo si por cada divisor primo p de f, existe un número entero xp tal que:

x_p^{N-1} \mod N\,=\,\mathrm{mcd}(x_p^{(N-1)/p}-1, N)\,=\,1 (1)

Si x_p^{N-1} \mod N\,\neq\,1 entonces N no pasa el test de primalidad que sugiere el pequeño teorema de Fermat y por lo tanto el número es compuesto. En caso contrario, si además \mathrm{mcd}(x_p^{(N-1)/p}-1, N)\,=\,N el test no puede determinar si el número es primo o compuesto y entonces hay que utilizar otro valor para xp.

Cuando se factoriza N-1 es posible que quede un factor muy grande (mayor que la raíz cuadrada de N) y no pueda utilizarse este teorema. Si se demuestra fácilmente que dicho factor es compuesto usando el Teorema de Fermat por ejemplo, el teorema de Pocklington no se puede utilizar, en caso contrario se puede intentar usar el teorema de Pocklington sobre ese factor intentando factorizar el número inmediatamente anterior. Si se demuestra que es primo, se conocen todos los factores primos de N-1, por lo que se puede utilizar el teorema sobre el número inicial.

Ejemplo

En el siguiente ejemplo suponemos que sólo se usará el método de división por tentativa hasta el divisor 10000.

N = 1020+1663 = 100000000000000001663

N-1 = 2 × 17 × 1289 × 2179 × 4513 × 232030781

No se puede determinar si el número r = 232030781 es primo o compuesto realizando divisiones sucesivas hasta 10000, ya que r supera al cuadrado de este número. Sin embargo, como el producto de los otros factores primos es mayor que r, se puede aplicar el teorema.

Eligiendo xp = 5 se cumple la fórmula (1) para los valores de p igual a 2, 17, 1289, 2179 y 4513, por lo que el número N es primo. En este caso se usó el mismo número x para todos los factores primos, pero esto no es necesario.

Referencias

  1. ↑ Knuth, Donald (1998). The Art of Computing Programming vol 2, 3ra edición. Addison Wesley Longman. ISBN 0-201-89684-2. 

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • Henry Cabourn Pocklington — (January 28, 1870 May 15, 1952)ref|1 was an English physicist and mathematician. His primary profession was as a schoolmaster, but he has made important contributions to number theory with the discovery of Pocklington s primality test in 1914.… …   Wikipedia

  • Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version …   Wikipedia

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Edmonton Oilers — 2011–12 Edmonton Oilers season Conference West …   Wikipedia

  • Wayne Gretzky — Infobox Ice Hockey Player image size = 240px position = Centre played for = WHA Indianapolis Racers Edmonton Oilers NHL Edmonton Oilers Los Angeles Kings St. Louis Blues New York Rangers shot = Left height ft = 6 height in = 0 weight lb = 185… …   Wikipedia

  • Beverley — infobox UK place country = England official name = Beverley static static image caption = Beverley Minster static image 2 = static image 2 caption = Arms of Beverley Town Council latitude = 53.845 longitude = 0.427 population = 29,110 (2001… …   Wikipedia

  • Sediment Profile Imagery — (SPI) is an underwater technique for photographing the interface between the seabed and the overlying water. The technique is used to measure or estimate biological, chemical, and physical processes occurring in the first few centimetres of… …   Wikipedia

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”