[obm-l] Mais sobre Primos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Soh pra complementar:

Procurar primos eh uma coisa que, a principio, qualquer um pode fazer. Por
exemplo tem um projeto chamado GIMPS - "Great Internet Mersenne Prime
Search" que conta com a participacao de centenas (milhares?) de pessoas em
todo mundo e cujo objetivo eh achar primos de Mersenne (aqueles da forma 2^p
- 1, onde p eh primo). Pra quem estiver interessado, o site eh esse aqui:

http://www.mersenne.org/prime.htm

Alias, um exercicio simples eh provar que se 2^n - 1 eh primo, entao n eh
primo e tambem dar um exemplo de que a reciproca nao vale (ou seja, exibir
um numero composto da forma 2^p - 1, com p primo) - alias, uma prova
matematicamente inaceitavel disso mas que talvez fosse aceita num tribunal
seria justamente a existencia do GIMPS.

****

Ano passado tres matematicos indianos descobriram um algoritmo que testa se
um dado numero eh primo em tempo polinomial (bem informalmente, isso quer
dizer que, se implementado num computador, o algoritmo dah a resposta em
pouco tempo). O artigo deles a respeito (relativamente curto, mas
sofisticado) estah aqui:

http://www.cse.iitk.ac.in/news/primality.html

****

Testar se um dado numero eh primo eh uma coisa. Fatorar um numero
sabidamente composto eh outra bem mais dificil. Ha quem diga que um
algoritmo que faz isso de forma eficiente jah existe, mas estah guardado
atras de sete chaves pela NSA ("National Security Agency" dos EUA) e por
outras agencias de inteligencia.

Se voce tentar descobrir por que uma agencia de inteligencia iria querer
censurar certos resultados de pesquisas em teoria dos numeros, voce vai ver
que matematica pura tem aplicacoes bem praticas...

No mais, se voce quiser fatorar e faturar, de uma olhada aqui:

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html


Um abraco,
Claudio. 


on 05.12.03 12:02, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

> On Fri, Dec 05, 2003 at 11:49:21AM -0200, Luis Lopes wrote:
>> Sauda,c~oes,
>> 
>> Quando foi descoberto e qual é
>> o último primo que NÃO é de Mersenne?
> 
> Eu suponho que você queira dizer o maior primo conhecido que não é Mersenne:
> 
> 1372930^131072+1, com 804474 algarismos, descoberto em 2003.
> 
> É um Fermat generalizado.
> 
>> Os primos de Fermat 2^n + 1 (note que n
>> tem que ser uma potência de 2) também
>> são procurados?
> 
> Não se conhece nenhum (além dos que Fermat conhecia).
> 
> Há um monte de listas de primos em
> http://www.utm.edu/research/primes/lists/
> 


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================