Chinese Remainder Theorem
Chinesischer Restsatz: Sind die Moduln paarweise teilerfremd, so hat ein Kongruenzsystem genau eine Lösung modulo ihrem Produkt.
Zweck
Arithmetik mit großem Modul in parallele Arithmetik mit kleinen Moduln zerlegen und so modulare Big-Number-Berechnungen beschleunigen.
Mechanismus
Gegeben x≡a_i (mod n_i) mit paarweise teilerfremden n_i hat x eine eindeutige Lösung mod N (N=∏n_i). Verwende N_i=N/n_i, M_i=N_i^(-1) mod n_i und x=∑a_i*N_i*M_i mod N.
Anwendungsfälle
- RSA-Beschleunigung
- Modulare Arithmetik großer Zahlen
- Zahlentheoretische Algorithmen