Anúncio de emprego no Google

[Swanhild]

Bem, eles esperam que esse resultado aí ainda lance alguma luz sobre como resolver o problema da fatoração depressa, ou mostrar que o problema é intratável do ponto de vista da complexidade computacional (não sei se provar que ele é NP completo seria o caso, acho que é alguma outra classe de complexidade que estaria envolvida aí). Por isso que esse resultado foi tão badalado quando saiu. Agora, como ele ajuda eu já não sei. Não estudei o problema da fatoração ou Teoria dos Números o bastante para dizer. Sei que ele certamente ajuda a resolver o problema do outdoor.

 

[Deriel]

Bem, eles esperam que esse resultado aí ainda lance alguma luz sobre como resolver o problema da fatoração depressa, ou mostrar que o problema é intratável do ponto de vista da complexidade computacional (não sei se provar que ele é NP completo seria o caso, acho que é alguma outra classe de complexidade que estaria envolvida aí). Por isso que esse resultado foi tão badalado quando saiu. Agora, como ele ajuda eu já não sei. Não estudei o problema da fatoração ou Teoria dos Números o bastante para dizer. Sei que ele certamente ajuda a resolver o problema do outdoor.

 

[dermeister]

A tempo: Quando o Google resolveu abrir seu capital na Nasdaq, a oferta inicial foi de exatos US $2,718,281,828 [1]. Tem alguém lá que *realmente* gosta da constante de Euler.

Detalhes: http://news.bbc.co.uk/nolpda/ukfs_news/hi/newsid_3673000/3673157.stm

[1] Sim, são e * 10^9 dólares!

 

[Swanhild]

Sim, sim, os Indianos. Mas concorda comigo que, sabendo que um número é primo, a fatoração de uma chave RSA torna-se bem mais simples? Por isso que eu afirmei que a idéia vale, mas a aplicação não é tão geral/prática assim

Bem, eles esperam que esse resultado aí ainda lance alguma luz sobre como resolver o problema da fatoração depressa, ou mostrar que o problema é intratável do ponto de vista da complexidade computacional (não sei se provar que ele é NP completo seria o caso, acho que é alguma outra classe de complexidade que estaria envolvida aí). Por isso que esse resultado foi tão badalado quando saiu. Agora, como ele ajuda eu já não sei. Não estudei o problema da fatoração ou Teoria dos Números o bastante para dizer. Sei que ele certamente ajuda a resolver o problema do outdoor.

Bom, explicando melhor, como eu já tinha dito, mesmo antes desse resultado dos Indianos, já existiam algoritmos que funcionavam bem na prática para determinar se um número é ou não primo. De fato, uma pesquisa rápida na Internet me informou que alguns desses algoritmos funcionam mais rápido na prática do que o dos Indianos, apesar de não serem polinomiais determinísticos. E nem por isso o problema da fatoração se tornou fácil a ponto de o RSA deixar de ser usado. Alguns desses algoritmos existem há mais de dez anos.

Agora, o que me parece do material que eu consultei é que a relação entre os dois problemas, o dos primos e o da fatoração, é menos trivial do que pode parecer à primeira vista. Como eu nunca estudei esses problemas a fundo (criptografia e Teoria dos Números não são minha área ), não posso dar mais esclarecimentos a respeito.

Lower-quality “industrial-grade primes ”with 512 binary digits can be produced in a fraction of a second using the Miller-Rabin test on an off-the-shelf 2GHz PC.If required,their primality can actually be proved in a couple of seconds with the ECPP-method of Atkin-Morain based on elliptic curves. The running-time complexity of this probabilistic algorithm is,to be sure,a “cloudy issue ”(Carl Pomerance),but heuristic considerations suggest that the likely value lies right around ˜O (log 6n ).

On the other hand,because of the high cost of the polynomial congruence in the third step of the AKS-algorithm, the constant in the conjectured ˜O (log 6n ) running-time bound is so large that the algorithm is estimated to take a couple of days on a 512-bit prime number,although Dan Bernstein, Hendrik Lenstra,Felipe Voloch,Bjorn Poonen,and Jeff Vaaler have already improved this constant by a factor of at least 2.10^6 relative to the original formulation of the algorithm —the status as of January 25,2003 [...].

Thus a factor of about 10^5 is missing to reach a competitive level.The ECPP-method too started with a completely impractical but groundbreaking new idea of Goldwasser and Kilian.Since the method that Agrawal,Kayal,and Saxena have now produced is so unexpectedly new and brilliant,we may confidently anticipate improved capabilities after further maturation of the algorithm.

In the August 9 arts section,under the heading “Polynomial gods:Resourceful Indians and their prime numbers ”,the Frankfurter Allgemeine Zeitung had a cryptic text that first made a connection between Indian mathematics and the Indian pantheon and then let four such deities hold a short discussion of the new result:

“What is it good for?”expostulated Agni, and Lakshmi retorted:“For hacking! One needs prime numbers for encoding data for electronic transmission — there are various so-called cryptographic algorithms like RSA and the Data Encryption Standard DES;the keys are numbers with prime factorizations, and if that can now be easily done in a time that is polynomial in the input data …” “But it is already well known, for example by the Miller-Rabin test,that if one iterates enough times,one can find a primality test with as large a probability as desired of being correct even for the biggest numbers,”contradicted Rudra.“And the encoding prime factorization has nothing to do with the test of whether a number is prime, which is a completely different problem; for security people what the guys have done is worthless.”At dawn,the hostess Ushas finally found the magic words of reconciliation:“Let us simply take pleasure in an elegant result that the West also admires and in the continuing inspiration of our great mathematical tradition!"

Fonte: Notices of the American Mathematical Society

 

[Anna Cwen]

qdo eu fiz inciação científica em matemática ( é, há malucos pra tudo!!) meu professor me deu uma noção dessas coisas, como funciona o RSA e tudo - para quem não sabe, se tiver alguem realmente acompanhando essa discussão além destes poucos gatos pingados , o RSA é algo do tipo vc escolhe um numero primo, "desmonta" ele e utiliza estas partes para criptografar sua mensagem; depois vc manda essa mensagem criptografada e um dos pedaços desmontados p/ a outra pessoa, q já sabe quais numeros (dentre uma lista) vc usa e com esse pedaço pode saber como decodificar a mensagem.

é isso, não é???

mas acho q estou misturando os canais... qdo vcs falam em fatoração, o q estão querendo dizer com isso?? pq, afinal, a definição de numero primo não é aquele que não tem nenhum divisor fora 1 e ele mesmo??

acho q tvz estejamos confundindo alguma coisa; tvz o RSA seja na verdade baseado em dois numeros que sejam primos entre si, não??

 

[Swanhild]

O problema do número primo é dizer se um dado número é primo ou não, enquanto que o problema da fatoração é achar os fatores primos de um dado número. É claro que se alguém sabe resolver o segundo problema eficientemente, ele sabe também resolver o primeiro também eficientemente. O contrário no entanto ainda não se sabe se é verdade; parece que achar os fatores depressa é muito mais complicado do que simplesmente dizer se o número é primo ou não depressa.

Observem que as palavras eficientemente e depressa aí fazem alguma diferença. Eu quero dizer com elas tempo polinomial determinístico.

 

[Anna Cwen]

ah, então é isso mesmo; eu tinha misturado os canais...

nós pegamos dois numeros que não são primos, certo??

lembrei de uma coisa agora... se nao me engano, meu professor citou uma coisa interessante sobre numeros primos...
era de se imaginar que, ao caminharmos para numeros maiores, a ocorrência de numeros primos fosse diminuindo cada vez mais, certo?? pois é, isso NÃO acontece. eles continuam aparecendo, com uma frequencia que diminui mto pouco (ou nada, não tenho certeza )

 

[Cildraemoth]

RSA em resumo (se eu não errei nada):

Escolher dois primos p e q. Multiplicá-los para obter o número N.

Escolher um número e qualquer*.

A sua chave pública é o par (e, N). Para criptografar uma mensagem M (que no caso é um número), basta calcular y = M^e mod N. y é a mensagem criptografada.**

Para decodificar y e obter M novamente, precisamos do número d, que é o inverso de e módulo (p-1)*(q-1). Esse inverso obtém-se com o algoritmo euclidiano estendido. A "mágica" é que y^d mod N = M. Aliás, nem pode ser chamado mágica, é fácil de provar isso.

A dificuldade está em encontrar d. Sabemos e e N. Se pudermos fatorar N, obtendo p e q, podemos calcular d facilmente. Se não pudermos fatorar, nada feito. Toda a segurança depende disso, do fato de que não se consegue fatorar N (pois é um número realmente grande) num tempo hábil.

Há muito tempo já há algoritmos rápidos para testar se um número é primo ou não. Eles eram probabilísticos, ou seja, havia uma chance de uns décimos de % de darem um resultado errado, mas isso não era um problema. Agora parece que há algoritmos determinísticos também rápidos para testar a primalidade, mas isso não interfere na segurança do RSA. Enquanto não se puder fatorar números grandes num tempo hábil, não se poderá quebrar RSA.

* Bem, tem algumas restrições que não vêm ao caso agora.
** Aqui também há umas considerações de ordem prática que não vêm ao caso agora.

 

[Anna Cwen]

hum, brigada, ex, eu não tava mesmo lembrando como funcionava...