Metraipolis › archive › dc_92aaec1ab0ea

Algoritmo di Schönhage-Strassen — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Algoritmo_di_Sch%C3%B6nhage-Strassen
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T16:25:25.739Z
SHA-256 of the archived text
7d49f91584139abe15c83a94f1a4626830eb0a16ca9400126d24a84581dda5af
Stable URL of this page
https://metraipolis.com/documento/dc_92aaec1ab0ea

How to cite

Algoritmo di Schönhage-Strassen — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Sch%C3%B6nhage-Strassen (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_92aaec1ab0ea (Metraipolis archive dc_92aaec1ab0ea, sha256 7d49f91584139abe15c83a94f1a4626830eb0a16ca9400126d24a84581dda5af)
BibTeX
@misc{dc92aaec1ab0ea,
  title = {Algoritmo di Schönhage-Strassen — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Algoritmo_di_Sch%C3%B6nhage-Strassen},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_92aaec1ab0ea; sha256 7d49f91584139abe15c83a94f1a4626830eb0a16ca9400126d24a84581dda5af},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Sch%C3%B6nhage-Strassen. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. 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 22n + 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, 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 2215 a 2217 (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. C'è una realizzazione in Java dell'algoritmo di Schönhage-Strassen che lo usa per i numeri con più di 74.000 cifre decimali. 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.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Algoritmo di Schönhage-Strassen» — https://it.wikipedia.org/wiki/Algoritmo_di_Sch%C3%B6nhage-Strassen
Wikidata Q1938391: «algoritmo di multiplicazione» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1938391
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_Sch%C3%B6nhage-Strassen?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 152448042, consultata il 2026-10-15T16:00:47.566Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 37222a9dcb44a950062a890b9788608658bab9d13a96361558f7732a692f195a