[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Indianos solucionam problema matemáticomilenar
Ja vi este e outros textos semelhantes na net, mas cuidado com alguns
erros de traducao ou comentarios errados.
Este eh um dos mais grotescos:
> O sistema de
> encriptação usado para proteger transações pela Internet conta com o fato de
> ser extremamente difícil descobrir os fatores de grandes números primos.
Fatorar numeros primos eh muito facil... ;-))
Varios dos artigos que li, principalmente aqueles provenientes de meios
de comunicacao comuns(populares como revistas e jornais) falam que os
criptossistemas como o RSA estao ameacados. Isto nao eh verdade! Pelo
contrario, muitos desses criptossistemas precisam testar a primalidade
de numeros para a construcao de chaves (ex. RSA) mas acabam se
utilizando de algoritmos probabilisticos. O problema no qual a
dificuldade eh utilizada como base para a contrucao de criptossistemas
eh o problema da FATORACAO, para o qual ainda nao existe resposta
eficiente. O temor de alguns pesquisadores (e que em alguns artigos que
li foi traduzido de forma errada) eh que se possa utilizar tecnicas
semelhantes aas dos indianos para resolver o problema da fatoracao de
forma eficiente.
Abracos,
Rodrigo
Alexandre Botelho MAGALHÂES de Oliveira wrote:
>
> Eu li a pouco na net esse artigo a respeito de testes de primalidade.
>
> Indianos solucionam problema matemático milenar
>
> Nicola Dixon
> Da New Scientist
>
> Três cientistas da computação chocaram a comunidade de matemáticos ao
> encontrar a solução para um problema que dura séculos: como dizer se um
> número é primo. A prova é impressionante em sua simplicidade, e fez os
> matemáticos se perguntarem o que mais eles podem ter deixado passar.
>
> Os números primos, que são divisíveis apenas por si mesmos e 1, são blocos
> de construção fundamentais da matemática e fascinam estudiosos desde os
> tempos antigos. Em 240 a.C., o matemático grego Eratóstenes apresentou a
> primeira forma à prova de falhas para saber se um número era primo. Mas o
> tempo que o método exige cresce exponencialmente com o tamanho do número, de
> forma que para números muito longos é necessário mais tempo que a idade do
> Universo para solucionar o problema. Desde então os matemáticos têm tentado
> encontrar um algoritmo de tempo polinomial, capaz de fornecer uma resposta
> em uma quantidade de tempo razoável.
>
> A busca se intensificou ao longo das últimas poucas décadas, desde que os
> números primos se tornaram vitais para a criptografia. O sistema de
> encriptação usado para proteger transações pela Internet conta com o fato de
> ser extremamente difícil descobrir os fatores de grandes números primos. Os
> algoritmos usados atualmente para ajudar a encontrar estes fatores são
> rápidos, mas eles apenas fornecem a probabilidade de um número ser primo ou
> não. Apesar da probabilidade ser muito alta, estes algoritmos não
> representam uma prova.
>
> Agora Manindra Agrawal e seus alunos ainda não formados, Neeraj Kayal e
> Nitin Saxtena, foram bem-sucedidos onde as melhores mentes da matemática
> fracassaram. O trio, do Departamento de Ciência da Computação e Engenharia
> do Instituto Indiano de Tecnologia em Kanpur, desenvolveram um algoritmo que
> dá uma resposta definitiva para o problema em tempo razoável.
>
> O sucesso deles está na nova abordagem que adotaram para o problema. Em vez
> de fazer a grande pergunta, "este é um número primo?", eles geraram uma
> série de perguntas menores ou "igualdades" do número que está sendo testado.
> "Se as igualdades se sustentarem, o número é primo, se alguma delas não se
> sustentar, então o número não é primo", explica Agrawal.
>
> Até o momento milhares de matemáticos verificaram as provas postadas
> atualmente no site do instituto na Internet. "Todos os que me mandaram
> e-mails apreciaram o algoritmo e disseram que ele está correto", diz Agrawal
> para a New Scientist.
>
> Especialistas suspeitavam que um algoritmo de tempo polinomial fosse
> possível. Mas não previam a simplicidade da solução em 13 linhas que Agrawal
> e seus colegas apresentaram. "É uma bela solução e estou muito feliz por
> eles, mas estou um pouco embaraçado por não ter visto isto eu mesmo", diz o
> especialista em números primos Carl Pomerance, dos Laboratórios Bell da
> Lucent, em Nova Jersey. "A solução deles é simples. Isto não quer dizer que
> seja trivial; o que eles fizeram foi muito inteligente", acrescenta.
>
> O avanço teórico é significativo por si só, mas Ian Stewart da Universidade
> de Warwick disse que o método também deverá ajudar os matemáticos a
> solucionarem outros problemas, nos quais chegaram a um beco sem saída usando
> outras técnicas.
>
> A segurança na Internet ainda não está sob ameaça. "A solução provavelmente
> terá um impacto muito pequeno, pois ela não oferece nenhuma vantagem real
> sobre os algoritmos probabilísticos já usados no setor", afirma Ben Hadley
> da nCipher, uma empresa de segurança por criptografia baseada em Cambridge.
> Mas Pomerance acredita que a existência da prova deixará os criptologistas
> preocupados. "Se há um teste simples para saber se um número é primo, também
> pode haver uma forma simples de determinar os fatores primos que estamos
> atualmente investigando", disse ele.
>
> Esta é a verdadeira importância do trabalho do trio. O fato de estudantes
> não formados, trabalhando em seu projeto de fim de ano, poderem solucionar
> um enigma tão antigo levanta a possibilidade de que outras soluções simples
> para grandes problemas matemáticos podem ter sido ignoradas. "É um lembrete
> de como podemos ignorar as coisas simples", disse Pomerance.
>
> Tradução: George El Khouri Andolfato
>
> Comente esta notícia: UOL Inovação - Computação
>
> -----Mensagem Original-----
> De: "Fernando Henrique Ferraz P. da Rosa" <mentus@gmx.de>
> Para: <obm-l@mat.puc-rio.br>
> Enviada em: terça-feira, 27 de agosto de 2002 19:38
> Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l]
> 1 é primo?
>
> Humm. também queria ler a respeito disso mas não achei *NADA* nos arquivos
> da lista.. somente uma única mensagem... essa aqui:
> [obm-l] Re: [obm-l] Indianos criam fórmula infalível para achar número
> primo, ghaeser
> url: http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200208/msg00115.html
>
> At 17:56 8/27/2002 -0300, you wrote:
>
> >Voce esta falando do algoritmo para testar a primalidade de um numero??
> >
> >Se for, eh so olhar os arquivos da lista...
> >Ele ja foi bem discutido por aqui.
>
> "... a perfect formulation of a problem is already half
> its solution."
> David Hilbert.
> -
> []'s
> Fernando Henrique Ferraz Pereira da Rosa
> USP, IME, Estatística
> http://www.linux.ime.usp.br/~feferraz
>
> ----------------------------------------------------------------------------
> ----
>
> >
> > ---
> > Outgoing mail is certified Virus Free.
> > Checked by AVG anti-virus system (http://www.grisoft.com).
> > Version: 6.0.384 / Virus Database: 216 - Release Date: 8/21/2002
> >
>
> =========================================================================
> 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
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================
=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================