Test de primalidade: Diferenzas entre revisións
Contido eliminado Contido engadido
mSen resumo de edición |
m Arranxiños |
||
Liña 4:
{{revisión|data=abril de 2016}}
[[Ficheiro:Mersene39.png|miniatura|O 39.º [[número primo de Mersenne]] era o maior coñecido até a data de creación deste artigo.]]
A cuestión da determinación de se un [[número]] n dado é [[Número primo|primo]] é coñecida como o problema da primalidade. Un '''test de primalidade''' (ou '''recoñecemento da primalidade''') é un [[algoritmo]] que, dado un número de entrada ''n'', non consegue verificar a [[hipótese]] dun [[teorema]] cuxa conclusión é que ''n'' é [[Número composto|composto]].
Isto é,
== Introdución ==
Liña 12:
Por outra banda, algunhas aplicacións das matemáticas que utilizan o problema da factorización precisan dunha serie de números primos moi grandes escollidos de forma aleatoria. O algoritmo para obter un número primo aleatorio moi grande sería algo así:
'''algoritmo''' baseado no [[postulado de Bertrand]] é
'''entrada:''' Un número natural ''n''
'''saída:''' ''P'', o primo aleatorio buscado
<math>P \gets </math>Número aleatorio do intervalo <math>[n,2n]</math>
'''mentres''' <math>P \,\!</math>non primo
<math>P \gets P+1</math>
'''se''' <math>(P = 2n)\,\!</math>'''entón''' <math>P \gets n</math>
'''retorna''' ''<math>P \,\!</math>''
O tempo de finalización deste algoritmo non é determinado, pero existe unha alta probabilidade de que finalice en tempo polinómico a condición de que haxa suficientes números primos e estes estean distribuídos de forma máis ou menos uniforme. Afortunadamente para as aplicacións que precisan números primos aleatorios, isto é así. Vexamos por que.
O primeiro que podemos establecer é que o cardinal do conxunto de primos no conxunto dos [[Número natural|números naturais]] <math>\mathbb{N}</math>
Claro que, se 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 [[Teorema dos números primos|teorema de Hadamard]] ([[1896]]) que establece que a cardinalidade 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.
Do visto até aquí podemos co''n''cluír que o algoritmo anterior pode obter unha resposta en tempo
En calquera caso, unha modificación moi frecuente para facer o algoritmo determinista é partir dunha semente aleatoria e logo facer unha procura secuencial da cota inferior do conxunto de
== De Euclides a Lucas ==
Antes de entrar a tratar as técnicas modernas que se aplican ao problema da primalidade non está de máis facer un breve repaso á historia do problema e ás solucións achegadas ao longo dos séculos.
Os problemas da factorización dun número dado e a determinación de números primos son moi antigos. Os rexistros históricos sobre o estudo de números primos remónt[[Século -III|a]]<nowiki/>nse a [[Euclides]] ([[Século -III|século III]] a. C.
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.
▲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 [[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).
Hoxe en día, este algoritmo ten un valor máis histórico que práctico. Funciona ben, pero é moi ineficiente.
Liña 38 ⟶ 46:
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 infinita) de números primos.
O problema, máis concreto, de determinar se un número n dado é primo pode derivarse do anterior, simplemente simúlase a criba para n-1 e compróbase se
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 se un número n dado é primo consistente en comprobar que ningún outro número primo inferior á raíz cadrada de n divide 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 [[sucesión de Fibonacci]].
Liña 46 ⟶ 54:
Un [[número perfecto]] é aquel que é igual á suma dos seus divisores propios. Por exemplo 6 é perfecto, xa que a suma dos seus divisores (1+2+3) é igual ao mesmo. O sete primeiros números perfectos son 6, 28, 496, 8128, 33550336, 8589869056 e 137438691328.
Cataldi determinou que se
En realidade Mersenne cometeu algúns erros xa que M_p non é primo para p = 67 nin 257 e se o é para p = 61, 89 e 107; no entanto o seu traballo sobre estes números quedou reflectido no feito de que levan o seu nome.
Liña 66 ⟶ 74:
</blockquote>Isto é, u''n'' test de primalidade só conxectura que “ante a falta de certificación sobre a hipótese de que n é composto podemos ter certa confianza en que se trata dun número primo”. Esta definición supón un grao menor de confianza que o que se denomina proba de primalidade (ou test verdadeiro de primalidade) que ofrece unha seguridade matemática respecto diso.<blockquote style=" width:90%; padding: 0.8em; border: 1px solid #880000; background-color: #FFFFFF;">
: '''Definición''': Un algoritmo de proba de primalidade (ou test verdadeiro de primalidade) é un algoritmo determinista que, dado un número de entrada n, verifica a hipótese dun teorema cuxa conclusión é que n é primo. Unha proba de primalidade é a verificación computacional de devandito teorema.
Liña 94 ⟶ 101:
Os tests probabilísticos están baseados na idea de relaxar a corrección da proba para conseguir un comportamento de resposta [[Tempo 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.
O primeiro exemplo de test probabilístico que veremos é o [[Test de primalidade de Fermat|test de Fermat.]] Devandito test está baseado no PTF. O algoritmo baseado neste test aplícase elixindo varios enteiros aleatorios
Como vimos na sección anterior, o test de Fermat adoece dun coñecido problema: os [[números de Carmichael]]. Os números de Carmichael pasan a condición de Fermat para todos os posibles valores de ; isto implica que se 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.
Liña 105 ⟶ 112:
Tamén se está avanzando neste campo utilizando outras formas máis sinxelas de traballo con grupos matemáticos en lugar da aritmética modular dos grupos de Galois.
Neste sentido están a facerse avances no traballo con curvas elípticas módulo n. Unha curva elíptica é unha función que se define da seguinte forma:<center><math>E(a,b): \quad y^2 = x^3+ax+b \quad / \quad 4a^3+27b^2 \neq 0</math></center>En curvas deste tipo estiveron traballando desde [[1986]] Goldwasser, Kilian e Atkin. Este último definiu o método ECPP ou [[proba de primalidade por curva elíptica]] (Elliptic Curve Primality Proving), que ten diversas
Moitas das probas e tests de primalidade que vimos até agora resólvense en tempo polinomial.
Liña 116 ⟶ 123:
O recente descubrimento dun algoritmo determinista de tempo polinomial que non se basea en ningunha conxectura non probada debe ser considerado un fito importante. Concretamente en agosto do ano [[2002]] tres académicos da Universidade de Kanpur (Agrawal, Kayal e Saxena) presentaron un algoritmo determinista de clase P para a determinación da primalidade dun número.<ref>Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin: "PRIMES is in P".</ref> A clave do algoritmo é unha versión simplificada do PTF, isto é a condición:<center><math>(x-a)^p \equiv (x^p-a) \pmod{x^r-1,\;p}</math></center>Os autores arranxáronllas para formular o seguinte algoritmo, que se probou pode executarse nun tempo de complexidade máxima de .<math>\mathcal{O}((\log \, n)^{\frac{21}{2}} f(\log \; \log \, n))</math>
Os autores demostraron ademais que, se determinados números primos (chamados [[Número primo de Sophie Germain|números primos de Sophie Germain]]) teñen a distribución
</ref><math>\mathcal{O}((\log \, n)^{6+\epsilon})</math>
En realidade este descubrimento non ten implicacións prácticas na computación moderna. O certo é que as partes constantes da complexidade do algoritmo son moito máis custosas que nos actuais algoritmos probabilísticos. É de esperar que no futuro próximo
== Notas ==
| |||