Gli scienziati dell'U.S. Army Research Laboratory hanno scoperto un modo per sfruttare le emergenti architetture di computer simili al cervello per un secolare problema di teoria dei numeri noto come fattorizzazione di interi.

Imitando le funzioni cerebrali dei mammiferi nell'informatica, Gli scienziati dell'esercito stanno aprendo un nuovo spazio di soluzioni che si allontana dalle architetture informatiche tradizionali e verso dispositivi in ​​grado di operare in dimensioni estreme, il peso-, e ambienti con limitazioni di alimentazione.

"Con più potenza di calcolo sul campo di battaglia, possiamo elaborare le informazioni e risolvere problemi computazionalmente difficili più velocemente, " ha detto il dottor John V. "Vinnie" Monaco, un informatico dell'ARL. "Programmare il tipo di dispositivi che soddisfano questi criteri, Per esempio, computer ispirati al cervello, è impegnativo, e decifrare i codici crittografici è solo un'applicazione che dimostra che sappiamo come farlo."

Il problema stesso può essere espresso in termini semplici. Prendi un intero composto N ed esprimilo come prodotto dei suoi componenti primi. La maggior parte delle persone ha completato questo compito ad un certo punto della scuola elementare, spesso un esercizio di aritmetica elementare. Per esempio, 55 può essere espresso come 5*11 e 63 come 3*3*7. Quello che molti non si sono resi conto è che stavano eseguendo un compito che, se completato abbastanza rapidamente per grandi numeri, potrebbe rompere gran parte dell'Internet moderno.

La crittografia a chiave pubblica è un metodo di comunicazione sicuro ampiamente utilizzato oggi, basato sull'algoritmo RSA sviluppato da Rivest, Shamir, e Adleman nel 1978. La sicurezza dell'algoritmo RSA si basa sulla difficoltà di fattorizzare un grande intero composto N, la chiave pubblica, che viene distribuito dal destinatario a chiunque voglia inviare un messaggio cifrato. Se N può essere scomposto nelle sue componenti prime, quindi la chiave privata, necessario per decifrare il messaggio, può essere recuperato. Però, la difficoltà nel scomporre in fattori grandi interi diventa presto evidente.

Quando la dimensione di N aumenta di una singola cifra, il tempo necessario per fattorizzare N provando tutte le possibili combinazioni di fattori primi è approssimativamente raddoppiato. Ciò significa che se un numero con dieci cifre impiega 1 minuto per essere scomposto, un numero con venti cifre impiegherà circa 17 ore e un numero con 30 cifre circa due anni, una crescita esponenziale dello sforzo. Questa difficoltà è alla base della sicurezza dell'algoritmo RSA.

Sfidando questo, Monaco e il suo collega Dr. Manuel Vindiola, della Divisione di Scienze Computazionali del laboratorio, ha dimostrato come i computer simili a cervelli forniscano un'accelerazione agli algoritmi attualmente più noti per la fattorizzazione degli interi.

Il team di ricercatori ha escogitato un modo per fattorizzare grandi interi compositi sfruttando il massiccio parallelismo di nuove architetture di computer che imitano il funzionamento del cervello dei mammiferi. I cosiddetti computer neuromorfici operano secondo principi molto diversi dai computer convenzionali, come laptop e dispositivi mobili, tutto basato su un'architettura descritta da John von Neumann nel 1945.

Nell'architettura von Neumann, la memoria è separata dall'unità di elaborazione centrale, o CPU, che deve leggere e scrivere in memoria su un bus. Questo bus ha una larghezza di banda limitata, e la maggior parte del tempo, la CPU è in attesa di accedere alla memoria, spesso indicato come il collo di bottiglia di von Neumann.

Computer neuromorfici, d'altra parte, non soffrono di un collo di bottiglia di von Neumann. Non c'è CPU, memoria, o autobus. Anziché, incorporano molte unità di calcolo individuali, proprio come i neuroni nel cervello.

Queste unità sono collegate da percorsi fisici o simulati per il passaggio dei dati, analogo alle connessioni sinaptiche tra i neuroni. Molti dispositivi neuromorfi funzionano in base alle proprietà di risposta fisica del materiale sottostante, come laser al grafene o giunzioni tunnel magnetiche. A causa di ciò, questi dispositivi consumano ordini di grandezza in meno di energia rispetto ai loro omologhi von Neumann e possono operare su una scala temporale molecolare. Come tale, qualsiasi algoritmo in grado di funzionare su questi dispositivi trarrà vantaggio dalle loro capacità.

Lo speedup acquisito dai ricercatori dell'ARL è dovuto alla formulazione di un metodo per la fattorizzazione di interi con l'ausilio di un coprocessore neuromorfo. Gli attuali algoritmi più veloci per la fattorizzazione di interi consistono principalmente di due fasi, setacciatura e una riduzione a matrice, e la fase di setacciatura comprende la maggior parte dello sforzo computazionale.

Il setaccio implica la ricerca di molti interi che soddisfano una certa proprietà chiamata B-smooth, interi che non contengono un fattore primo maggiore di B. Monaco e Vindiola sono stati in grado di costruire una rete neurale che scopre i numeri B-smooth più rapidamente e con maggiore precisione rispetto a un'architettura di von Neumann. Il loro algoritmo sfrutta il massiccio parallelismo dei computer ispirati al cervello e l'innata capacità dei singoli neuroni di eseguire operazioni aritmetiche, come l'addizione. Poiché le architetture neuromorfe continuano ad aumentare in dimensioni e velocità, non limitato dalla legge di Moore, cresce anche la loro capacità di affrontare problemi di fattorizzazione di interi più grandi. Nel loro lavoro, si stima che le chiavi a 1024 bit potrebbero essere violate in circa un anno, un compito che una volta si pensava fosse irraggiungibile. Per confronto, il record attuale, un numero di 232 cifre decimali (RSA-768) richiedeva circa 2, 000 anni di tempo di calcolo nel corso di diversi anni.

Da una prospettiva più ampia, questa scoperta ci spinge a chiederci come un cambiamento nel paradigma informatico potrebbe influenzare alcuni dei nostri presupposti di sicurezza più basilari. Man mano che i dispositivi emergenti si spostano per incorporare un enorme parallelismo e sfruttare la fisica dei materiali per il calcolo, la durezza computazionale alla base di alcuni protocolli di sicurezza può essere sfidata in modi mai immaginati in precedenza. Questo lavoro apre anche le porte a nuove aree di ricerca di architetture informatiche emergenti, in termini di progettazione di algoritmi e rappresentazione di funzioni, insieme ad applicazioni di machine learning e intelligenza artificiale a bassa potenza.

"I messaggi crittografati in guerra spesso hanno una data di scadenza, quando i loro contenuti diventano inagibili, " Monaco ha detto. "C'è l'urgenza di decifrare le comunicazioni nemiche, soprattutto quelli a livello di campo, poiché questi scadono più velocemente, rispetto alla comunicazione ai livelli più alti. In condizioni di campo, potenza e connettività sono estremamente limitate. Questo è un forte fattore motivante per l'utilizzo di un computer ispirato dal cervello per un compito in cui i computer convenzionali non sono pratici".