Test de primalidade: Diferenzas entre revisións

[[Ficheiro:Mersene39.png|miniatura|O 39º [[:es:Número_primo_de_Mersenne|número primo de Mersenne]] era o maior coñecido até a data de creación deste artigo.]]

Os problemas que implican ás matemáticas discretas están entre os máis difíciles das matemáticas. Concretamente o da factorización é un problema para o que aínda non se atopou unha solución que se poida acoutar en [[:es:Tiempo_polinómico|tempo polinomicopolinómico]]<ref>Papadimitriou, Christos H.: ''Computational Complexity''. </ref>

O primeiro que podemos establecer é que o cardinal do conxunto de primos no conxunto dos [[Número natural|números naturais]] é [[:es:Infinitud_de_los_números_primosInfinitude dos números primos|infinito]] (isto é, que hai infinitos números primos).<math>\mathbb{N}</math> O [[:es:Teorema_de_Dirichlet|teorema de Dirichlet]] ([[1837]]) di que si mcd(a, ''n'') = 1 entón hai infinitos curmáns [[Congruencia (álxebra)|congruentes]] coa módulo n. ''N''outras palabras (e utilizando un corolario de Dirichlet), os números primos están uniformemente distribuídos nas clases congruentes coa [[:es:Función_φ_de_Euler|función φ de Euler]] en para calquera valor de n.<math>\mathbb{N}_n^*</math>

Claro que, si os números primos están uniformemente distribuídos, pero hai un número pequeno deles, a procura podería ser imposible na práctica. Para resolver este segundo problema podemos acudir ao [[:es:Teorema_de_los_números_primosTeorema dos números primos|teorema de Hadamard]] ([[1896]]) que establece que a cardinalidad do conxunto de números primos no intervalo [2..n] é asintótico a .<math> n /{\log \, n}</math> Este número tende a infinito moi suavemente, o que implica que aínda para valores grandes de n existe unha probabilidade suficientemente alta de dar cun número primo de forma aleatoria.

Con todo, o primeiro procedemento matemático coñecido concernente estes números remóntase a [[Eratóstenes]] ([[Século -II|século II]] a. C.) e é a coñecida [[:es:Criba_de_Eratóstenes|criba de Eratóstenes]], que aínda se estuda nos centros de educación primaria. O método é sinxelo: para obter os números primos menores que un dado, primeiro colocamos os números de 1 a n nunha lista e empezamos tachando todas as posicións pares. Logo, sobre a lista que queda tachamos todos os que son múltiplo de tres (o seguinte número da lista despois do 2). Logo sobre os que quedan todos os que son múltiplos de cinco (o seguinte número da lista despois do 3).

A mellora máis obvia atén á forma na que o algoritmo termina (curiosamente Eratóstenes non tivo en conta este feito e foi o matemático árabe [[:es:Al-Marrakushi_ibn_AlMarrakushi ibn Al-Banna|ibn ao-Banna]] quen a propuxo séculos despois): é suficiente con iterar até os divisores primos de n menores que <math>\sqrt{n}</math>.

Outro problema da criba é que non responde o problema da simple determinación de primalidade dun número dado, senón que ofrece unha lista (potencialmente [[:es:Infinitud_de_los_números_primos|infinita]]) de números primos.

Como moitas outras achegas matemáticas, o problema da primalidade chegou á Europa moderna a través dos árabes, pero non foi até moitos séculos despois que apareceron os primeiros rexistros escritos sobre a primalidade e a súa solución. Estes corresponden ao matemático italiano [[Leonardo Fibonacci|Leonardo de Pisa]] (Fibonacci) quen presentou un algoritmo moi simple para determinar si un número n dado é primo consistente en comprobar que ningún outro número primo inferior á raíz cadrada de n divíde a <math>n</math>. Este algoritmo ten a característica de ser determinista (sempre obtén unha solución) aínda que tremendamente ineficiente. En realidade, Fibonacci é máis coñecido pola sucesión que leva o seu nome e que tamén ten o seu papel no problema que nos ocupa. Logo veremos algo máis sobre a famosa [[:es:Sucesión_de_Fibonacci|sucesión de Fibonacci]].

O primeiro en utilizar relacións observadas entre os números para determinar a primalidade foi o boloñés [[:es:Pietro_Antonio_Cataldi|Pietro Antonio Cataldi]] co seu traballo sobre os números perfectos.

Fermat buscaba números n>1 que lle axudasen a comprobar a primalidade dos [[:es:Número_de_MersenneNúmero de Mersenne|números de Mersenne.]]Na súa procura viu que o teorema antes exposto era útil para detectar posibles primos q tales que <math>q | 2^{37}-1</math> .Fermat tamé''n'' suxeriu que os números denominados números de Fermat debían ser primos e comprobouno para todos os n menores que 4. Non puido demostralo para 5 e hoxe sábese que iso é composto, como o son todos os restantes até n=24 (e posiblemente todos os demais, aínda que este último extremo é aínda unha conxectura).

Houbo outros matemáticos tamén moi eminentes que traballaron no campo da factorización de números, por exemplo [[:es:Adrien-Marie_LegendreMarie Legendre|Legendre]] e [[Carl Friedrich Gauss|Gauss]], e que tamén fixeron algunhas contribucións ao problema da primalidade; pero o último dos matemáticos clásicos do que falaremos que obtivo notables resultados sobre a cuestión foi o francés [[:es:François_Éduard_Anatole_Lucas|François Éduard Anatole Lucas.]]. Lucas traballou sobre os [[:es:Número_de_Fibonacci|números de Fibonacci]] e de Mersenne, obtivo resultados sobre a divisibilidad dos primeiros e determinou unha proba de primalidade para os números de Mersenne (que aplicou á comprobación de primalidade de M127) que veremos a continuación.

Nos apartados anteriores falouse de dous problemas relacionados (factorización e primalidade) que dalgunha maneira son complementarios. Con todo, as dúas cuestións son de natureza moi distinta. Para convencer a alguén de que un número foi factorizado é suficiente con mostrar os factores e o resultado queda claro. Con todo convencer a esa mesma persoa de que un número dado é primo pode ser moito máis difícil. Como o matemático parisiense do [[século XIX]] [[:es:Fortuné_Landry|Fortuné Landry]] sinalou, a menos que a outra parte coñeza os métodos de comprobación da primalidade e realice por si mesma os cálculos, a sinxela resposta “é primo” é só cuestión de fe. Un test (ou recoñeceme''n''to) de primalidade é un algoritmo que, dado un número de entrada n, non consegue verificar a hipótese dun teorema cuxa conclusión é que n é composto.

Para empezar, o exemplo clásico de test verdadeiro de primalidade: o [[:es:Test_de_Lucas-Lehmer|Test de Lucas-Lehmer.]] A proba LL aplícase aos números de Mersenne (a entrada é o índice p do número de Mersenne do que se quere comprobar a primalidade). A definición do algoritmo é a seguinte:

A última proba neste apartado débese a Pepin (1877). O [[:es:Test_de_Pépin|teorema de PepinPépin]] enúnciase como segue:

''A'' constante 3 en realidade pódese substituír por calquera enteiro positivo para o que un operador chamado [[:es:Símbolo_de_Jacobi|símbolo de Jacobi]] sexa igual a–1. Isto inclúe aos valores 3, 5 e 10.

Os tests probabilísticos están baseados na idea de relaxar a corrección da proba para conseguir un comportamento de resposta [[:es:Tiempo_polinómicoTempo polinómico|polinomial ou subpolinomial.]] Baséanse ben no uso PTF (que acabamos de comentar), ben no uso do que se coñecen como verificadores e falsadores de Euler.

Como vimos na sección anterior, o test de Fermat adoece dun coñecido problema: os [[:es:Números_de_Carmichael|números de Carmichael.]]. Os números de Carmichael pasan a condición de Fermat para todos os posibles valores de ; isto implica que si o noso candidato a número primo fose un número de Carmichael, non importa cantas veces pasemos o test de Fermat, o resultado sempre sería negativo e en consecuencia o resultado do test sería un falso primo positivo.<math>a</math> Con todo, os números de Carmichael son relativamente escasos (hai 105.212 deles menores de ) polo que a probabilidade de elixir algún deles é realmente baixa.<math>10^{15}</math> O test de Fermat é de amplo uso no campo da criptografía.

Outro test moi coñecido e utilizado en criptografía é o [[:es:Test_de_Solovay-Strassen|test de Solovay-Strassen]] (SS). Este test está baseado ''n''o [[:es:Criterio_de_Euler|criterio de Euler]].

Os autores demostraron ademais que, si determinados números primos (chamados [[Número primo de Sophie Germain|números primos de Sophie Germain]]) teñen a distribución conxeturada polo matemático austriaco [[:es:Emil_Artin|Emil Artin]], o expoñente 21/2 que aparece na expresión de complexidade pode reducirse a 15/2. O que implica que o tempo estimado de execución sería equivalente ao dalgunha proba de primalidade das vistas anteriormente (concretamente a proba ECPP). E no artigo publicado polos mesmos, tamén mencionaban unha versión do algoritmo AKS presentada por H.W. Lenstra e C. Pomerance que se executa en tempo de forma incondicional.<ref>H. W. Lenstra jr. and Carl Pomerance: "Primality testing with Gaussian periods".<br>

* Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford: ''Introduction to Algorithms.'' Sección 31.8: "Primality testing", pp.887–896. MIT Press & McGraw-Hill, 2a edición, [[2001|2001.]] ([[:es:Special:BookSources/0262032937|ISBN 0-262-03293-7]].)

* Knuth, Donald. ''The Art of Computer Programming'', Volume 2: ''Seminumerical Algorithms.'' Páxinas 391–396 de sección 4.5.4. Addison-Wesley, 3a edición, 1997. ([[:es:Special:BookSources/0201896842|ISBN 0-201-89684-2]].)

* Williams, H.C.: ''Édouard Lucas and Primality Testing.'' John Wiley & Sons, 1998. ([[:es:Special:BookSources/0471148520|ISBN 0-471-14852-0]].)