Em 1971, o matemático americano Daniel Shanks publicou um método para um problema que nada tinha a ver com dinheiro digital. A ideia era simples o bastante para caber num parágrafo e boa o bastante para atravessar meio século: em vez de percorrer o caminho inteiro de uma ponta, percorra metade de cada ponta e encontre-se no meio.
O problema, aqui, é o da aula anterior na sua versão favorável: a chave pública Q é conhecida, sabe-se que ela vale k vezes G, e sabe-se que k está entre zero e N. Encontrar k por força bruta custaria N passos. O método de Shanks custa cerca de duas vezes a raiz de N.
O truque é escrever k de um jeito diferente. Chame de m a raiz quadrada de N, arredondada para cima. Todo número entre zero e N pode ser escrito como i vezes m mais j, com i e j menores que m — é a mesma decomposição que você faz ao dizer que 47 é quatro dezenas e sete unidades, só que com m no lugar de dez.
Substituindo na equação, Q é igual a i vezes m mais j, tudo multiplicado por G. Passe o j para o outro lado: Q menos j vezes G é igual a i vezes o ponto m vezes G. Repare no que aconteceu. Do lado esquerdo só há coisas que dependem de j; do lado direito, só coisas que dependem de i. Os dois lados foram separados.
Daí vem o nome. Os passos de bebê são os m valores do lado esquerdo: calcula-se Q menos j vezes G para cada j, e guarda-se cada resultado numa tabela. Os passos de gigante são os m valores do lado direito: calcula-se i vezes o ponto mG, para cada i, e a cada um procura-se na tabela. Quando um valor bate, os i e j correspondentes revelam k, porque k é i vezes m mais j.
Em bits, a economia é limpa. Um intervalo de setenta bits tem 2^69 candidatos, e a raiz quadrada disso é algo em torno de 2^34,5 — pouco mais de vinte e quatro bilhões de passos de cada lado. Uma máquina que faz alguns bilhões de operações por segundo atravessa isso em minutos, não em milênios.
Só que a conta acima é a do tempo, e o método cobra em outra moeda. A tabela dos passos de bebê precisa existir inteira antes que os passos de gigante comecem. São vinte e quatro bilhões de entradas, e cada entrada guarda pelo menos um pedaço da coordenada do ponto e o valor de j — algo como trinta bytes por linha, sendo generoso. Isso dá perto de setecentos e cinquenta gigabytes de memória, para um intervalo de setenta bits.
E a memória cresce na mesma raiz que o tempo. Oitenta bits pedem cerca de vinte e quatro terabytes; noventa pedem quase oitocentos. Guardar isso em disco em vez de memória não resolve, porque cada passo de gigante faz uma consulta a um endereço imprevisível, e disco não gosta de acesso aleatório: o método deixa de ser limitado pelo cálculo e passa a ser limitado pelo tempo de procurar.
Existem versões que reduzem a tabela guardando apenas parte de cada ponto e aceitando conferir os falsos positivos depois. Elas ajudam por um fator constante e não mudam a natureza do problema: o passo de bebê e passo de gigante é um método que troca memória por tempo, e essa troca tem um limite físico que chega rápido.
Foi para escapar exatamente desse limite que se procurou outro caminho — um que custe a mesma raiz quadrada em tempo e praticamente nada em memória. Ele existe, tem nome de animal e é o algoritmo que derrubou os maiores desafios já resolvidos. Na próxima aula, os cangurus de Pollard.