Como explicar o caso Snowden para sua tia.

Imagine que você está num domingo ensolarado na praia de Ipanema quando toca seu celular. Do outro lado da linha a Tia Betty que quer saber se ainda é seguro pagar a conta de luz pela internet. Ela leu o tal do caso Snowden, viu lá o Fantástico e ficou preocupada. Quer que você explique para ela o que está acontecendo.

Neste momento você conta até dez para não mandar a Tia Betty para aquele lugar, afinal sua mãe vai ficar chateada e pensa em como se livrar do problema de maneira rápida.

A questão não é saber se existe um meio completamente seguro de se comunicar pela Internet, mas de quem você quer se proteger?

Eu costumo dizer que uma pessoa (empresa, entidade ou governo) com tempo e recursos consegue invadir qualquer sistema. É uma questão de valor do alvo e capacidade do invasor. Um alvo de baixo valor em geral não paga os recursos necessários para quebrar um sistema básico de criptografia, provavelmente este é o caso da sua tia.

Mas em alguns casos o usuário pediu para ser burro, entrou duas vezes na fila e ainda mandou caprichar, é o caso do sujeito que veio chorar que tiraram dinheiro da conta dele. Segundo o mané, ele recebeu um e-mail do banco dizendo que eles precisavam confirmar os dados dele, aí num site mequetrefe com a cara do Santander, ele digitou o login, a senha, a senha do cartão e ainda se deu o trabalho de digitar os 50 dígitos do cartão de segurança, além, obviamente, do número do cartão de segurança. Convenhamos, que com um usuário assim, os hackers mais pé de chinelo, que compraram o “Haqueando” Contas de Banco em duas semanas, conseguem se dar bem.

Mas e o Snowden, pergunta sua tia. Neste momento, caso você queira aproveitar seu domingo é melhor dizer para ela que tudo não passa de teoria da conspiração.

Algum usuário mais crédulo poderá dizer agora, não é verdade que qualquer sistema seja vulnerável. Ele pode até argumentar que não quebraram o código do TrueCrypt do Daniel Dantas, mesmo o FBI não quebrou. É verdade, mas será que o Daniel Dantas é um “high value target” que os americanos vão usar aquele zero-day-exploit especial que estão guardando para pegar um terrorista?

O fato que sabemos é que o código do TrueCrypt, apesar de aberto, ainda não foi totalmente, e está longe de ser, completamente validado contra vulnerabilidades.

Se você quiser saber a razão do buraco ser muito mais embaixo eu tenho algumas sugestões de leitura:

In God we trust

P.S: Depois de ler isto que eu falei, você vai entender porque nem o Serpro nem os Correios, mesmo que não fossem o lodaçal que são, não teriam condições de fazer um e-mail seguro para a Dilma. Eu acredito que nenhuma empresa brasileira tem condições.

Cinco filmes sobre matemática que você deve ver.

Um dos posts mais populares do Zeletron é o dos cinco filmes que os amantes da tecnologia devem ver, e agora faço uma compilação pessoal do top5 em termos de matemática para você ter algo para ver hoje a noite 🙂

5) Moneyball (2011) – O homem que mudou o jogo
Usar estatística para vencer uma campeonato de Baseball? Não qualquer campeonato de baseball, mas a MLB. O treinador Billy Beane assume um risco ao contratar o matemático Peter Brand como seu assistente e aplicar um método matemático num esporte que sempre foi dominado por olheiros e pessoas com intuição. Será que o Oaklands A vai se sair bem com isto?

Grande filme e ótimo elenco.

4) I.Q. (1994) – A fórmula do amor

Um filme com Albert Einstein, Kurt Gödel e Boris Podolski, três gênios, que não conseguem trocar uma lâmpada. Este pode ser um breve descritivo para esta bela comédia romântica com Tim Hobbins e Meg Ryan. Não é 100% sobre matemática, mas vai fazer você se divertir.

3) 21 (2008) – Quebrando a banca
Baseado na história real de alguns estudantes do MIT que usando técnicas estatísticas, encontraram uma maneira de ganhar dinheiro no único jogo que apresenta uma fragilidade para os cassinos, o Black Jack ou 21. Baseado no livro “Bringing down the house”.

Eu conheci uma pessoa do MIT que disse que este esquema segue até hoje e que ele tinha participado dele durante algum tempo e que o filme é bem realista.

2) A Beautiful Mind (2001) – Uma mente brilhante

A vida do matemático, prêmio nobel de economia e desequilibrado mentalmente por uma grave doença, John Nash. Ganhador de Oscars e espetacularmente produzido é além disso uma história real.

A idéia de escrever no vidro com caneta de retroprojetor eu adotei desde aquela época para o desespero do pessoal da limpeza do trabalho.

1) Good Will Hunting (1997) – Gênio indomável

Matt Damon e Robin Williams fazem desta história, que mostra um rapaz genial que trabalhava como faxineiro no MIT, um dos grandes vencedores do Oscar. Há o lado humano, do rapaz que é genial, mas problemático que dá o grande toque de qualidade no filme. O seriado do Youtube Numberphile tem um episódio sobre a solução do problema do filme.

Gênio Indomável
Você sentiu falta de algum nesta lista?

Sugestão de Leitura: Prime Obsession

Existem livros que apesar de falarem de coisas bastante sofisticadas são muito agradáveis de ler e Prime Obsession é um deles.

Neste livro, John Derbyshare, conta a saga inacabada da busca do que é talvez o maior problema aberto na matemática e para o qual há um prêmio de US$ 1.000.000,00 para quem resolver: a Hipótese de Riemann.

Eu confesso que antes de ler o livro sabia muito pouca coisa sobre a Hipótese de Riemann (HR), mas o autor consegue com muita didática ir conduzindo o leitor passo a passo pelos labirintos matemáticos para que qualquer pessoa, ainda que sem formação matemática possa compreender a natureza do problema.

A HR diz que a função zeta de Riemann tem todos os zeros não triviais com parte inteira igual a 1/2.

E eu com isso, poderia dizer o leitor. A hipótese de Riemann além de ser uma excelente ferramenta para entender o comportamento dos números primos é o fundamento de muitas descobertas matemáticas, prová-las significa provar muitas outras coisas em consequência e refutá-la significa derrubar por terra vários outros resultados.

Além de agradável leitura, Prime Obsession leva o leitor a descobrir a era romântica da matemática, saindo de Leonard Euler, passando por Gauss, Riemann e vários gigantes que revolucionaram o campo nos séculos XVIII, XIX e XX.

Se você quiser dar um voto de confiança para este escriba aqui, leia este livro. Garanto que não se arrependerá.

Na Amazon: Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics

Na Livraria Cultura: Prime Obsession

Prime Obsession: Resenha

 

NOTA: A função zeta de Riemann é:

ζ(s) = 1 + 1/2s + 1/3s + 1/4s + ..

Primos na Espiral de Ulam

Uma das razões dos números primos serem tão legais se deve ao fato deles se comportarem de forma estranha. Eles parecem aleatórios.

Algumas vezes você tem longos espaços entre dois números primos e, de repente, como os ônibus, vêm dois de uma vez só. No entanto, no fundo no fundo, eles não são completamente aleatórios.

Um matemático Polonês chamado Stanislaw Ulam, que foi para os EUA pouco antes da Segunda Guerra Mundial, estava, depois da guerra, em 1963, assistindo uma apresentação de um trabalho chatíssimo e longo com um papel e uma caneta na mão e resolveu fazer a seguinte brincadeira para se distrair:

No centro do papel colocou o número 1 e foi fazendo uma espiral quadrada com a sequência, conforme a figura abaixo:
ulam1

Depois disso, começou a circular os números primos nesta espiral, conforme a figura a seguir:
ulam2

Ele ficou surpreso pelo fato dos números primos caírem em diagonais. Como todos os números primos, exceto o 2, são números ímpares e como as diagonais nesta espiral alternam entre pares e ímpares, não é surpresa que os números caiam em diagonais alternadas, mas que algumas diagonais tenham mais primos do que outras.

Pouco tempo depois ele resolveu fazer um programa usando o computador MANIAC II para imprimir pixels nos pontos primos (exatamente como eu fiz em vermelho no excel) e conseguiu fazer uma imagem com os números até 65.025 (255 x 255).

Aqui abro um parêntese para falar do MANIAC II.

Ele era um computador criado em 1957 com 4096 words de 48bits (24kbytes) de memória RAM em Magnetic-core Memory e 12288 words de 48bits (576kbytes) em Williams tubes. Em média, uma multiplicação neste computador demorava 180 microsegundos e uma divisão 300 microsegundos. Uma verdadeira eternidade para os tempos de hoje.

Voltando à espiral do Ulam, o que ele conseguiu com a impressão da matriz de 255 x 255 de pixels foi a confirmação do que ele havia visto com 100 números. Realmente há um padrão no qual os números primos aparecem em diagonais, com intervalos, é claro, e algumas diagonais parecem ter mais primos do que outras.

ulam-255x255

Todas as linhas nesta espiral obedecem à seguinte equação quadrática: 4x^2+bx+c

Por exemplo, a diagonal que começa no número 3 tem a seguinte equação: 4x^2-2x+1
3, 13, 31, 57, 91, … (Confira na imagem acima)

Na prática, há uma hipótese de que estas diagonais podem servir para procurarmos números primos grandes, já que algumas diagonais têm mais primos do que outras diagonais. Melhor dizendo, algumas equações quadráticas têm mais chance de retornar números primos do que outras.

Um exemplo de diagonal com 40 números primos em sequência é a seguinte: x^2-x+41 que gera a seguinte sequência de 40 números primos:

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601 (O 41o número é igual a 41^2 e, portanto, não é primo)

As diagonais com as maiores densidades de números primos conhecidas são a belezuras abaixo:

x^2 + x + 3399714628553118047

e (desculpe, não cabe na tela)

x^2 + x + 332518109806968781031500852571295088573128477514981900349983874538507313

O que interessa nisto tudo, é que, parece que, há fórmulas com mais densidade de primos do que outras (isso ainda não foi provado) e isto pode ajudar a resolver outros problemas, como a hipótese de Goldbach (que diz que todos os números pares maiores do que 2 podem ser expressados pela soma de dois números primos) ou a hipótese da existência de infinitos números primos gêmeos.

Como não poderia faltar, eu fiz uma implementação em javascript para mostrar esse grid, só que em vez de 255 x 255, o grid que eu fiz é de 1000×1000. O resultado está neste link. Obviamente você pode aumentar o tamanho do canvas para gerar coisas grandes, como essa de 25.000.000 de números (5000 x 5000) que eu fiz usando o mesmo código (Clica que aumenta).

ulam-5000x5000

 

Edição das 11:50 (Não podia faltar o código Python. O @jbvsmo depois dirá que está lento….)

#!/usr/bin/env python
import sys,math
import Image
 
size = int(sys.argv[1])
 
def sieveGen(siz):
    l = [2,3,5,7,11,13,17,19,23,29]
    if (siz < 31):
        return l
    for i in xrange(31,siz,2):
        isP = True
        rT = math.sqrt(i)
        for j in l:
            if i%j == 0:
                isP = False
                break
            if j>rT:
                break
        if isP:
            l.append(i)
    return l
 
mySieve = sieveGen(size)
 
 
def isPrime(n):
    if (n == 1):
        return False
    if (n < size):
        return (n in mySieve)
    isP = True
    sqrtN = math.sqrt(n)
    for j in mySieve:
        if (n%j)==0:
            return False
        if (j>sqrtN):
            return True
    return True
 
 
 
 
def spiral(N):
    im = Image.new("RGB", (N, N), "white")
    pix = im.load()
    red = (255,0,0)
    if(N%2):
        x = y = ((N-1)/2)
    else:
        x = y = (N/2)
    N2 = N*N
    dx = 1
    dy = 0
 
    val = 1
    amp = 1
    c = 0
 
    while (val <= N2):
        mvd = 0
        while ((mvd < amp) and (val <= N2)):
            if isPrime(val):
                pix[x-1,y-1] = red
            x += dx
            y += dy
            mvd += 1
            val += 1
 
        c += 1
        if (c == 2):
            c = 0
            amp += 1
 
        if (dx == 1):
            dx,dy = 0,1
        else:
            if (dy == 1):
                dx,dy = -1,0
            else: 
                if (dx == -1):
                    dx,dy = 0,-1
                else:
                    if (dy == -1):
                        dy,dx = 0,1
    im.transpose(Image.FLIP_TOP_BOTTOM).save("ulam.png")
 
spiral(size)

Estimando Pi com agulhas e linhas

Há alguns dias, assisti a um vídeo muito legal que mostrava que era possível estimar Pi pelo número de vezes que uma agulha cruzasse linhas verticais num tabuleiro no qual as linhas verticais fossem separadas por uma distância igual ao dobro do tamanho da agulha.

Para testar o que o sujeito fez no vídeo com fósforos, no lugar de agulhas, fiz um programinha em Javascript que deixo abaixo. Como o Javascript não é uma linguagem muito apropriada para isso, não esperem muita precisão nem muita performance. No final do post mostro uma solução mais elegante.

Atenção não coloque mais de 1.000.000 de agulhas ou seu browser pode travar.

Esse método de estimar Pi, é baseado no problema da agulha de Buffon, que foi proposto lá pelo século XVIII, pelo matemático francês Conde de Buffon.

A proposição diz o seguinte: Dada uma agulha com comprimento l e um assoalho com tábuas de largura t, a probabilidade de se jogar uma agulha no chão e ela cair sobre uma junção de tábuas é \frac{2l}{t\pi}.

Se l = \frac{t}{2}, então a probabilidade da agulha cair sobre uma junção é \frac{1}{\pi}

Portanto, se jogarmos N agulhas no chão e o número de agulhas que caírem sobre as junções for h, poderemos aproximar \pi pela fração \frac{N}{h}.

A demonstração dessa probabilidade você encontra aqui. Coloquei o link da Wikipedia em inglês porque essa página na Wikipedia lusófona está muito ruim.

Não satisfeito com a implementação porca que eu fiz em Javascript, o Pedro Paulo resolveu fazer uma muito mais eficiente e elegante em python, que deixo abaixo:

#!/usr/bin/env python
import math, random
 
def generateNeedles (n):
    cross = 0
    for i in xrange(n):
        x = random.random()
        theta = random.random()*(math.pi/2.0)
        if ((x + 0.25*math.cos(theta)) >= 1.0):
            cross += 1
        else:
            if ((x - 0.25*math.cos(theta)) <=0.0):
                cross += 1
    return cross
 
needleCount = 30000000
cross = generateNeedles(needleCount)
print cross,needleCount, needleCount / float(cross)

Ao executar o script acima obtive os seguintes resultados:

30.000 agulhas 3.13217790771
300.000 agulhas 3.14261171985
3.000.000 agulhas 3.14226609757
30.000.000 agulhas 3.1423348868

Esse Conde de Buffon deve ter perdido muita agulha deixando cair entre uma tábua e outra do piso de casa, só pode… 🙂