L'algoritmo di Schönhage-Strassen è un algoritmo di moltiplicazione rapido per grandi numeri interi, sviluppato da Arnold Schönhage e Volker Strassen nel 1971.^[1] La sua complessità, nella notazione O-grande, è O(n log n log log n). L'algoritmo usa ricorsivi Trasformate di Fourier veloci negli anelli con 2²ⁿ + 1 elementi.

L'algoritmo di Schönhage-Strassen era asintoticamente il più veloce metodo di moltiplicazione conosciuto tra il 1971 ed il 2007, finché non è stato annunciato l'algoritmo di Fürer che ha complessità asintotica minore,^[2] però al momento raggiunge il vantaggio solo per numeri astronomicamente grandi e non è utilizzato praticamente.

In pratica, l'algoritmo di Schönhage-Strassen è più veloce di metodi vecchi come quello di Karatsuba e di Toom-Cook per i numeri da 2²¹⁵ a 2²¹⁷ (10.000 a 40.000 cifre decimali). La GNU Multi-Precision Library lo utilizza per valori di almeno 1728 a 7808 word a 64 bit (33.000 a 150.000 cifre decimali), a seconda dell'architettura.^[3] C'è una realizzazione in Java dell'algoritmo di Schönhage-Strassen che lo usa per i numeri con più di 74.000 cifre decimali.^[4]

Applicazioni dell'algoritmo di Schönhage-Strassen includono empirismo matematico come il GIMPS e calcolo di π, così come applicazioni pratiche quali la fattorizzazione con le curve ellittiche in cui la moltiplicazione di polinomi con coefficienti interi può essere efficientemente ridotta alla moltiplicazione di grandi numeri interi.^[5]