Matematik / Sayı Teorisi
Asallar, OBEB ve modüler aritmetik
Eratosthenes Kalburu
Her asalın katlarını karesinden başlayarak eleyerek n'e kadar tüm asalları bulur.
Süre O(n log log n) · Alan O(n)
Öklid Algoritması (OBEB)
(a, b) çiftini kalan sıfır olana dek (b, a mod b) ile değiştirerek en büyük ortak böleni hesaplar.
Süre O(log min(a, b)) · Alan O(1)
Genişletilmiş Öklid Algoritması
Öklid'i Bézout katsayılarını izleyerek çalıştırır; gcd(a, b) = x·a + y·b ile biter — modüler tersin anahtarı.
Süre O(log min(a, b)) · Alan O(1)
Hızlı Üs Alma
Tabanı karesini alarak ve yalnızca üssün 1-bitlerinde çarparak baseᵉˣᵖ mod m'yi O(log üs) sürede hesaplar.
Süre O(log exp) · Alan O(1)