Números primos e algoritmos – Parte I

Um dos fundamentos da criptografia e dos sistemas de assinatura digital são os números primos. O princípio que rege a criptografia assimétrica (RSA) é o fato de ser rápido descobrir se um número é primo e é lento fatorar um número.

O RSA fica para outro post, agora queria focar na pergunta: como faz para saber se um número é primo?

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i < x; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Obviamente esta função não é a melhor, ela roda em O(n) ou seja o tempo de execução cresce linearmente com o tamanho do número em questão.

Uma otimização que alguns alunos espertos no curso de Computação I fazem é a seguinte:

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< x/2; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Isto diminui o tempo de execução pela metade mas não muda a complexidade do algoritmo, ela continua sendo O(n). Portanto para números grandes isto não ajuda muito.

Uma coisa que podemos usar para melhorar a complexidade (ainda não ajuda muito, mas hoje paramos por aqui) é o fato de que se um número não tem nenhum divisor menor que a raiz quadrada dele ele não tem nenhum divisor (a prova disto é fácil e fica como exercício para o leitor 🙂 )

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< sqrt(x); i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Neste caso a complexidade que era O(n) passa a ser O(√n)

Melhorou? Sim. Mas ainda não é o suficiente. No próximo capítulo desta série, veremos métodos que dizem se um número é provavelmente primo.

Se você achar algum erro nos códigos acima, comente.

Os neutrinos mais rápidos que a velocidade da luz

Li um excelente post no ArsTechnica detalhando o experimento que foi feito na Suiça e que mostrou neutrinos chegando 60ns antes da luz num trajeto de 730km. Li também um post no MeioBit a respeito que não foi muito feliz: o Cardoso escreve muito bem, mas os dois textos dele de hoje foram fracos do ponto de vista da ciência.

Os próprios cientistas que participaram do experimento estão procurando achar furos nos seus resultados, talvez escaldados pelo efeito fusão à frio, talvez por receio de estar jogando por terra um dos pilares da física moderna: nada se move mais rápido que a luz (dizem que a diarréia sim).

E onde podem estar estas fontes de erro? No artigo que eles disponibilizaram hoje são algumas fontes de erro apontadas e descartadas:

  1. erro na medição da distância: descartado pois a precisão da medida confirmada por duas fontes independentes é de 7cm em 730km (~0,000001%)
  2. erro na medição do tempo: máximo erro do sistema 2,8ns
  3. erros devido aos relógios utilizados: <10ps
Fontes de Erro Experimento Neutrinos

Um dos cientistas diz que o achado é tão inesperado que ele espera que algum outro laboratório confirme o experimento antes de comemorar a descoberta.

Então, como diria minha avó: prudência e canja de galinha não fazem mal a ninguém. Não saia por aí dizendo que Einstein estava errado antes do assunto terminar de ser investigado.

Experimento Neutrinos velozes

Quer ganhar US$ 1.000.000,00?

Ninguém disse que é fácil, mas aqui vai uma dica quente 🙂

O Prêmio Problemas do Milênio consiste em sete problemas matemáticos e computacionais em aberto que pagam um milhão de obamas para o primeiro que os resolver. Você tem portanto sete chances de ganhar :D, na verdade seis porque um russo resolveu o problema número 3 mas disse que não queria o prêmio (vai entender um matemático russo).

Quem quiser ler mais sobre as regras do concurso: http://www.ams.org/notices/200606/fea-jaffe.pdf

Na foto abaixo você pode ver o rapaz que resolveu o problema número 3, mas esqueceu de ir buscar …

Perelman

Já ia me esquecendo …. Se resolver algum, você entrega eles aqui: http://www.claymath.org/millennium/

RSA SecurdID, o buraco pode ser maior que parece

Quando foi amplamente divulgado em março que o produto SecurID da RSA sofreu uma importante falha de segurança, muitos especialistas afirmaram que o problema era muito mais teórico que prático e que os usuários de bancos, que usamos nossos tokens RSA para autenticação poderíamos ficar tranquilos.

Não foi bem assim. E as noticias do ataque eletrônico com possível roubo de material militar na Lockheed Martin mostra a gravidade do problema.

Os tokens servem para aumentar a segurança da criptografia com a autenticação de duas camadas. Neste tipo de autenticação é utilizado algo que somente você (na teoria) conhece, no caso a senha, com algo que você possui (o token). No caso de autenticação biométrica seria a combinação da senha com algo que você tem de pessoal (íris, digitais, formato da mão, etc.)

Como muitos usuários empregam senhas fáceis como manuel123 ou a data de seu aniversário concatenado com de sua mulher, a segunda camada de autenticação exige que o invasor saiba a sua senha e roube seu token.

O token é um relógio, uma senha e uma função matemática F que une a hora H com a senha S para formar uma sequência de números que é exibida no display. Esta sequência é F(H,S). Como a função F é conhecida (aparentemente foi quebrada há alguns anos) e a hora H é conhecida, o cara que está fazendo o ataque teria que conhecer S para violar seu sistema. No entanto S é algo que está inserido de maneira inviolável no dispositivo.

Na outra ponta está o site ou banco que está recebendo a autenticação, este lado ao receber o número de série do reloginho (que fica no verso) tem que ter uma tabela de S associados a cada relógio que distribuiu para conferir F(H,S) e ver se está correto.

Embora não esteja claro o que aconteceu (cf. http://www.rsa.com/node.aspx?id=3872) parece que vazou o banco de dados, ou parte do banco de dados de associação entre o número de série do reloginho e a senha S. Se de fato isto se confirma, e o ataque a Lockheed Martin foi feito usando informações obtidas deste banco de dados, houve um duro golpe na segurança das autenticações e será preciso pensar alguma forma mais segura de gerar os dados do token. Além disso as perdas para a RSA e para os usuários podem ser muito elevadas.

 

Profecias tecnológicas para 2011

Bom, vou utilizar meus dons de profecia para adiantar para vocês o que acontecerá em termos de tecnologia em 2011.

Nokia: A Nokia atualmente passa por um momento difícil, não é preciso ser profeta para saber disto, e suas ações valem hoje um quarto do que valiam no começo de 2008. Um pechincha de 38B de dólares. A Nokia será comprada pela Microsoft que terminará com o velho e bom Symbian e acabará com a festa dos Maemo, Meego, Inimeegos da vida.

Microsoft: A gigante de Redmond, com o inicial sucesso do Windows Phone 7 deve trazer surpresas para 2011. Uma possível é a acima mencionada compra da Nokia. Outra, não tão surpresa, é a aquisição do Yahoo, desta vez para valer. Além disso o profeta assegura que um sucessor do XBox 360 será lançado com Kinetics nativo e uma GPU monstruosa. O Service Pack do Windows 7 será lançado e trará consigo um suporte nativo a virtualização.

Google: 2011 será o ano do Google enterrar seus mortos, Buzz, Orkut, Google TV. O foco será no Android, Buscador, Mapas e uma outra inovação que ainda não consigo profetizar. O Google pode em 2011 fazer mudanças drásticas na sua direção, quem sabe um CEO mais agressivo? Em termos de aquisições, visualizo o Google adquirindo o Twitter.

Apple: Steve Jobs é um cara difícil de profetizar, mas pelo menos uma coisa consegui ver, além do IPad 2 que já é dado como certo. A Apple irá comprar a Rovio e integrar o Angry Birds nos IPod Touch e IPhones! Será o iAngryBirds.

Oracle: Vai continuar trollando com processos seus inimigos, vai continuar comprando empresas a torto e a direito. Quem será a bola da vez? Adobe!

Adobe: Depois de lançar o Creative Suite CS6 será comprada pela Oracle. Motivo? Patentes!

HP: Será comprada pela Dell.

IBM: Lançará o chip Power8 com 10Ghz de Clock!

Acabo aqui minha brincadeira de começo de ano, você tem alguma previsão para 2011?

UPDATE: Devido aos acontecimentos de hoje (11/02/2010), marco em bold o que já acertei. A da Nokia ainda não acabou o ano, mas já dou como certo o bold.

Google Beat, o que está sendo mais procurado e aonde

Quando temos muitos dados uma dificuldade é fazer com que eles sejam úteis e o Google tem algumas ferramentas para isto como o Google Trends e o Insight For Search

Agora estão publicando uma série de vídeos mostrando formas interessantes de ver estes dados:

Veja o vídeo abaixo e se gostar assine o canal do Youtube do Google Beat

Fonte: Google Blogs

TK85, meu amigo Yossef e uma sugestão

Mil desculpas por fazer outro post com evocações de memórias pessoais, mas acontece que os comentários que escreveram no post de ontem sobre o Hello World fizeram com que eu resgatasse um monte de lembranças de infância e o motivo deste post é para contar uma história e fazer uma sugestão.

Em 1985, então um pirralho de 10 anos, ganhamos o nosso primeiro computador. Era um TK85 da Microdigital como o da foto deste post, ele possuia um processador Z80, 16kB de RAM, 10kB de ROM, Display de 22×32 em modo texto e 64×44 em modo gráfico e pesava menos de meio quilo. A maior parte dos celulares atuais tem mais de 1.000.000 mais poder de processamento e armazenamento que o pequeno TK85 mas para nós aquilo era muito legal.

Uns anos depois conheci um cara chamado Yossef (que aliás tem histórias inacreditáveis, especialmente com o motorista que ele tinha em seus anos de DJ), ficamos muito amigos e sei que ele vem montando um museu de computadores. Quase consegui para ele um DEC PDP-11 que o InCor estava descartando. Sei que ele tem no Rio de Janeiro atualmente uma bela coleção de peças desta época inesquecível da computação e vou tentar que ele escreva um post para o Zeletron contando a história das raridades que há no acervo dele.

Agora a sugestão: cada um dos leitores do Zeletron tem a sua história com relação a tecnologia. Quer tenham começado com um LINC ou com um Core i7 esta história pode ser interessante. Escrevam sua história nos comentários deste post, vamos escolher as melhores e caso os autores concordem podemos transformá-las num post para a leitura de fim de semana para a próxima semana. Que tal?

Aguardo vossos comentários.