Cientistas do Laboratório de Pesquisa do Exército dos EUA descobriram uma maneira de alavancar arquiteturas emergentes de computador semelhante ao cérebro para um problema teórico dos números milenar conhecido como fatoração de inteiros.

Ao imitar as funções cerebrais dos mamíferos na computação, Os cientistas do Exército estão abrindo um novo espaço de solução que se afasta das arquiteturas de computação tradicionais e se direciona a dispositivos que são capazes de operar em tamanhos extremos-, peso-, e ambientes com restrição de poder.

"Com mais poder de computação no campo de batalha, podemos processar informações e resolver problemas computacionalmente difíceis mais rapidamente, "disse o Dr. John V." Vinnie "Mônaco, um cientista da computação ARL. "Programando o tipo de dispositivo que se enquadra nesses critérios, por exemplo, computadores inspirados no cérebro, é desafiador, e decifrar códigos de criptografia é apenas um aplicativo que mostra que sabemos como fazer isso. "

O problema em si pode ser expresso em termos simples. Pegue um inteiro composto N e expresse-o como o produto de seus componentes principais. A maioria das pessoas completou esta tarefa em algum momento da escola primária, frequentemente um exercício de aritmética elementar. Por exemplo, 55 pode ser expresso como 5 * 11 e 63 como 3 * 3 * 7. O que muitos não perceberam é que estavam realizando uma tarefa que, se concluída com rapidez suficiente para um grande número, poderia quebrar grande parte da internet moderna.

A criptografia de chave pública é um método de comunicação segura amplamente usado hoje, baseado no algoritmo RSA desenvolvido pela Rivest, Shamir, e Adleman em 1978. A segurança do algoritmo RSA depende da dificuldade de fatorar um grande número inteiro composto N, a chave pública, que é distribuído pelo receptor a qualquer pessoa que queira enviar uma mensagem criptografada. Se N pode ser fatorado em seus componentes principais, então a chave privada, precisava descriptografar a mensagem, pode ser recuperado. Contudo, a dificuldade em fatorar números inteiros grandes rapidamente se torna aparente.

À medida que o tamanho de N aumenta em um único dígito, o tempo que levaria para fatorar N tentando todas as combinações possíveis de fatores primos é aproximadamente o dobro. Isso significa que se um número com dez dígitos leva 1 minuto para ser fatorado, um número com 20 dígitos levará cerca de 17 horas e um número com 30 dígitos cerca de dois anos, um crescimento exponencial do esforço. Essa dificuldade é a base da segurança do algoritmo RSA.

Desafiando isso, Mônaco e seu colega Dr. Manuel Vindiola, da Divisão de Ciências Computacionais do laboratório, demonstraram como os computadores semelhantes ao cérebro aumentam a velocidade dos algoritmos atualmente mais conhecidos para a fatoração de inteiros.

A equipe de pesquisadores desenvolveu uma maneira de fatorar grandes inteiros compostos, aproveitando o paralelismo maciço de novas arquiteturas de computador que imitam o funcionamento do cérebro dos mamíferos. Os chamados computadores neuromórficos operam sob princípios muito diferentes dos computadores convencionais, como laptops e dispositivos móveis, tudo baseado em uma arquitetura descrita por John von Neumann em 1945.

Na arquitetura de von Neumann, a memória é separada da unidade de processamento central, ou CPU, que deve ler e gravar na memória por meio de um barramento. Este barramento tem uma largura de banda limitada, e na maior parte do tempo, a CPU está esperando para acessar a memória, frequentemente referido como o gargalo de von Neumann.

Computadores neuromórficos, por outro lado, não sofrem de um gargalo de von Neumann. Não há CPU, memória, ou ônibus. Em vez de, eles incorporam muitas unidades de computação individuais, muito parecido com os neurônios do cérebro.

Essas unidades são conectadas por caminhos físicos ou simulados para transmitir dados, análogo a conexões sinápticas entre neurônios. Muitos dispositivos neuromórficos operam com base nas propriedades de resposta física do material subjacente, como lasers de grafeno ou junções de túnel magnético. Por causa disso, esses dispositivos consomem ordens de magnitude menos energia do que suas contrapartes de von Neumann e podem operar em uma escala de tempo molecular. Como tal, qualquer algoritmo capaz de funcionar nesses dispositivos pode se beneficiar de seus recursos.

O speedup adquirido pelos pesquisadores do ARL se deve à formulação de um método para fatoração de inteiros com o auxílio de um coprocessador neuromórfico. Os algoritmos mais rápidos atuais para fatorar inteiros consistem principalmente em dois estágios, peneiramento e redução da matriz, e o estágio de peneiramento compreende a maior parte do esforço computacional.

Peneirar envolve a busca de muitos inteiros que satisfaçam uma certa propriedade chamada B-smooth, inteiros que não contêm um fator primo maior que B. Monaco e Vindiola foram capazes de construir uma rede neural que descobre números B-smooth mais rapidamente e com maior precisão do que em uma arquitetura de von Neumann. Seu algoritmo aproveita o paralelismo maciço de computadores inspirados no cérebro e a capacidade inata de neurônios individuais para realizar operações aritméticas, como adição. À medida que as arquiteturas neuromórficas continuam a aumentar em tamanho e velocidade, não limitado pela Lei de Moore, sua capacidade de lidar com problemas maiores de fatoração de inteiros também cresce. Em seu trabalho, estima-se que as chaves de 1024 bits podem ser quebradas em cerca de um ano, uma tarefa que antes se pensava estar fora de alcance. Para comparação, o registro atual, um número de 232 dígitos decimais (RSA-768) levou cerca de 2, 000 anos de tempo de computação ao longo de vários anos.

De uma perspectiva mais ampla, essa descoberta nos leva a questionar como uma mudança no paradigma da computação pode afetar algumas de nossas premissas de segurança mais básicas. À medida que os dispositivos emergentes mudam para incorporar paralelismo maciço e aproveitar a física dos materiais para computar, a dureza computacional subjacente a alguns protocolos de segurança pode ser desafiada de maneiras não imaginadas anteriormente. Este trabalho também abre a porta para novas áreas de pesquisa de arquiteturas de computador emergentes, em termos de design de algoritmo e representação de função, ao lado de aplicativos de aprendizado de máquina de baixo consumo e inteligência artificial.

"As mensagens criptografadas na guerra geralmente têm uma data de validade, quando seu conteúdo se torna inutilizável, "Monaco disse." Há uma urgência para decifrar as comunicações inimigas, especialmente aqueles no nível de campo, já que estes expiram mais rápido, em comparação com a comunicação em escalões mais elevados. Em condições de campo, a potência e a conectividade são extremamente limitadas. Este é um forte fator de motivação para usar um computador inspirado no cérebro para uma tarefa onde os computadores convencionais não são práticos. "