Sayı Teorisi Algoritmaları : Matematiksel Temeller ve Uygulamalar

Sayı Teorisi Nedir ve Neden Algoritmaya İhtiyaç Duyar?

Matematiksel olarak sayı teorisi, tam sayıların ( Integers ) özelliklerini ve birbirleriyle olan ilişkilerini inceleyen kadim bir daldır.

Ancak bir yazılımcı için sayı teorisi, sadece "sayılarla oynamak" değil; internetin kilidi olan Kriptografi'nin, veriyi benzersiz kılan Hashing yöntemlerinin ve optimizasyonun temelidir.

Sayı teorisi algoritmalarına duyduğumuz ihtiyaç, özellikle modern dünyada asal sayılar ve modüler aritmetik üzerinden dönen devasa işlem yüklerinden doğar.

Örneğin: Kredi kartı bilgilerinizi koruyan RSA şifrelemesi, yüzlerce basamaklı iki asal sayının çarpımını geri döndürmenin

( asal çarpanlara ayırma ) imkansızlığına dayanır.

Bu süreci saniyeler içinde yönetmek, etkin modüler üs alma ve asal test algoritmaları olmadan imkansızdır.

Algoritmik düzeyde biz, bu soyut kavramları ( asal çarpanlar, modüler tersi, en büyük ortak bölen ) sadece teorik olarak değil;

bit manipülasyonu ve hızlı üs alma teknikleri perspektifiyle ele alırız.

Dünya Standartları ve İleri Seviye Kullanım Sayı teorisinin en ikonik algoritması kuşkusuz Öklid Algoritması (Euclidean Algorithm)'dır.

M.Ö. 300'lü yıllardan bugüne uzanan bu yöntem, dünyanın en eski ve hâlâ en sık kullanılan algoritmalarından biri olarak, O(log n) verimliliği ile modern veri yapılarının temelini atar.

Blockchain teknolojisindeki Eliptik Eğri Kriptografisi (ECC) sayı teorisinin sınırlarını zorlarken; Çin Kalan Teoremi (CRT) devasa hesaplamaları küçük parçalara bölerek paralel işlemcilerin gücünü kullanmamızı sağlar.

Sayı teorisi, dijital güvenliğin ve veri bütünlüğünün görünmez zırhıdır.

BigInt, Arbitrary-Precision ve İşlemci Limitleri

Sayı teorisi algoritmalarıyla çalışırken karşılaşılan en temel mimari engel, modern CPU'ların sabit genişlikli (fixed-width) kayıtçılarla

( \(32\) veya \(64\)-bit ) çalışacak şekilde tasarlanmış olmasıdır.

Kriptografik protokollerde kullanılan \(2048\) veya \(4096\)-bitlik devasa sayılar, standart bir işlemcinin tek bir saat çevriminde işleyebileceği sınırın çok ötesindedir.

Bu durum, biz yazılımcıları Arbitrary-Precision Arithmetic kullanmaya zorlar.

JavaScript ekosisteminde BigInt, C++ tarafında ise GMP (GNU Multiple Precision) gibi kütüphaneler; büyük sayıları bellek üzerinde parçalara bölerek yönetir.

Ancak bu esneklik, beraberinde ciddi bir CPU Maliyeti getirir.

Standart bir çarpma işlemi tek döngüde biterken, devasa sayıların çarpımı karmaşık döngüler ve bellek tahsisleri gerektirir.

Yanlış veri tipi seçimi veya taşma ( Integer Overflow ) hataları, algoritmanın matematiksel mantığı kusursuz olsa bile, pratikte anahtar üretimini bozabilir veya sistemi Side-Channel Attack gibi zamanlama analizlerine açık hale getirebilir.

Tanım ve Matematiksel Mantık

Trial Division, verilen bir tam sayının asal olup olmadığını belirlemek için kullanılan, tarihteki en eski ve kavramsal olarak en yalın deterministik algoritmadır.

Algoritmanın özü, hedef sayının kendisinden küçük olan "deneme bölenlerine" sırayla bölünmesidir.

Eğer sayı, 1 ve kendisi dışında herhangi bir tam sayıya kalansız bölünüyorsa Bileşik ( Composite ), aksi takdirde Asal ( Prime ) kabul edilir.

Bu yöntem, karmaşık şifreleme sistemlerinden önce sayının "temel atomlarını" kontrol eden ilk güvenlik süzgecidir.

Algoritma İşleyişi ve Karekök Kısıtı

Algoritma, asallık testini n sayısına kadar değil, yalnızca √n değerine kadar yaparak devasa bir performans sıçraması gerçekleştirir.

Eğer bir sayının böleni varsa, bu bölenlerin en az biri mutlaka √n değerine eşit veya ondan küçüktür.

Bu kural, arama uzayını dramatik şekilde daraltarak işlem süresini asimptotik olarak optimize eder.

Adım Adım Yürütme: Süreç önce 2 ve 3 gibi Temel Asallar kontrolü ile başlar, ardından çift sayıları hızla elemek için Dış Döngü 3'ten başlar.

İç Mekanizma, deneme bölenlerini ikişer ikişer artırarak (3, 5, 7...) sadece tek sayılar üzerinden kalansız bölme ( n mod i == 0 ) testini koşturur.

Herhangi bir adımda bölünen bulunursa işlem anında false döner; bu da algoritmanın gereksiz CPU döngüsü harcamasını önler.

Performans ve Hız: Trial Division, küçük ve orta ölçekli sayılar için deterministik kesinliği sayesinde son derece güvenilirdir.

Ancak zaman karmaşıklığı O(√n) olduğu için, kriptografik düzeydeki (yüzlerce basamaklı) sayılarda üstel bir yavaşlama göstererek pratik limitlerine ulaşır.

Hesaplama Yoğunluğu, sayının basamak sayısı arttıkça "brute-force" doğası gereği işlemciyi doyuma ulaştırır.

function isPrimeTrialDivision(n) {
    if (n < 2) return false;
    if (n === 2) return true;
    if (n % 2 === 0) return false;
    
    for (let i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i === 0) return false;
    }
    
    return true;
}

Tanım ve Eliminasyon Mantığı

Sieve of Eratosthenes, belirli bir üst sınıra ( n ) kadar olan tüm asal sayıları bulmak için geliştirilmiş, tarihteki en verimli toplu eliminasyon algoritmasıdır.

Algoritmanın temel felsefesi, sayıları tek tek test etmek yerine, asal sayıların katlarını sistematik olarak listeden silerek ilerlemektir.

Bu "kalbur" mantığı sayesinde, geriye elenmemiş olarak kalan tüm sayılar zorunlu olarak asaldır.

M.Ö. 3. yüzyıldan beri kullanılan bu yöntem, modern bilgisayar biliminde devasa asal sayı listeleri oluşturmanın en hızlı yolu kabul edilir.

Algoritma İşleyişi ve Karekök Optimizasyonu

Kalbur, asallık testini her sayı için yeniden başlatmaz.

Bunun yerine, bulunan her asalın katlarını "asal değildir" olarak işaretler.

Algoritma, asalların katlarını eleme işlemine p asalının karesinden ( p² ) başlar.

Çünkü p'den küçük olan katlar ( 2p, 3p ), zaten daha önceki küçük asallar tarafından listeden silinmiştir.

Bu kural, CPU döngülerini gereksiz tekrarlardan korur.

Adım Adım Yürütme: Önce 0'dan n'ye kadar tüm elemanları true kabul eden bir dizi oluşturulur.

Dış Döngü, 2'den başlayarak √n sınırına kadar ilerler. Eğer mevcut sayı elenmemişse ( hâlâ true ise ), o bir asaldır.

İç Döngü, bulunan bu asalın tüm katlarını dizide false olarak işaretleyerek kalburdan aşağı atar.

Tüm süreç tamamlandığında, dizide hâlâ true değerine sahip olan indisler, aradığımız asal sayıların tam listesini oluşturur.

Performans ve Hız: Sieve of Eratosthenes, O(n log log n) zaman karmaşıklığı ile toplu asal bulmada rakipsizdir.

Ancak alan karmaşıklığı O(n) olduğu için, çok devasa limitlerde bellek tüketimi bir darboğaz oluşturabilir.

Bellek Yoğunluğu, n sayısına kadar olan her bir sayı için bellekte yer ayrılmasını gerektirir.

Mühendislik başarısı; statik bir dizi yerine bit-set yapıları kullanarak bellek kullanımını 8 kat azaltabilmekten geçer.

function sieveOfEratosthenes(n) {
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    const primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }
    
    return primes;
}

function sieveOptimized(n) {
    if (n < 2) return [];
    if (n === 2) return [2];
    
    const isPrime = new Array(Math.floor((n - 1) / 2) + 1).fill(true);
    const primes = [2];
    
    for (let i = 3; i * i <= n; i += 2) {
        if (isPrime[Math.floor((i - 1) / 2)]) {
            for (let j = i * i; j<= n; j += 2 * i) {
                isPrime[Math.floor((j - 1) / 2)] = false;
            }
        }
    }
    
    for (let i = 3; i <= n; i += 2) {
        if (isPrime[Math.floor((i - 1) / 2)]) {
            primes.push(i);
        }
    }
    
    return primes;
}

Tanım ve Fermat'nın Küçük Teoremi

Fermat Primality Testi, bir n tam sayısının asal olup olmadığını kontrol etmek için tasarlanmış, Pierre de Fermat'nın Küçük Teoremi'ne dayanan yüksek performanslı bir olasılıksal algoritmadır.

Bu test, bir sayının asal olduğunu %100 kesinlikle kanıtlamasa da, o sayının Bileşik olduğunu saniyenin binde birinde ispatlayabilir.

Modern kriptografide devasa sayıların ön elemesi için kullanılan en hızlı "yalan dedektörü"dür.

Teoremin kalbi şu eşitliğe dayanır: n bir asal sayıysa, 1 ile n-1 arasındaki her "a" tam sayısı için a^(n-1) ≡ 1 (mod n) kuralı daima geçerlidir.

Algoritma İşleyişi ve Tanık (Witness) Seçimi

Algoritma, asallığı sorgulanan n sayısı için rastgele bir a seçerek sürece başlar.

Eğer seçilen bu "a" sayısı Fermat eşitliğini sağlamazsa, n sayısının asallık iddiası anında çöker.

Ancak eşitlik sağlanırsa, n sayısı bir Fermat Pseudoprime olabilir.

Bu riski minimize etmek için Byteomi mühendislik pratiğinde test, farklı "a" değerleriyle k kez tekrarlanarak güvenilirlik artırılır.

Adım Adım Yürütme: Test, katsayı matrisindeki Modüler Üs Alma (Modular Exponentiation) operasyonuyla başlar.

İşlem Safhası, seçilen her rastgele "a" için \(a^{n-1} \bmod n\) sonucunun 1 olup olmadığını kontrol eder.

Eğer tek bir iterasyonda bile sonuç 1'den farklı çıkarsa, n sayısı için kesinlikle Bileşik kararı verilir.

k adet testin tamamı başarılı geçerse sayı "muhtemelen asaldır".

Performans ve Hız: Fermat testi, O(k log³ n) zaman karmaşıklığı ile Trial Division gibi yöntemleri sahadan siler.

En büyük zayıflığı ise Carmichael Sayıları olarak adlandırılan sayılardır. (561, 1105...).

Bu nadir bileşik sayılar, Fermat testini her seferinde kandırarak kendilerini asal gibi gösterirler.

Hesaplama Verimliliği, çok büyük bit genişliğindeki sayılarda bile saniyeler içinde sonuç verir.

function modExp(base, exponent, modulus) {
    let result = 1;
    base = base % modulus;
    
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    
    return result;
}

function fermatPrimalityTest(n, k = 5) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0) return false;
    
    for (let i = 0; i < k; i++) {
        const a = Math.floor(Math.random() * (n - 3)) + 2;
        
        if (modExp(a, n - 1, n) !== 1) {
            return false;
        }
    }
    
    return true;
}

function fermatDeterministic(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0) return false;
    
    for (let a = 2; a < n; a++) {
        if (modExp(a, n - 1, n) !== 1) {
            return false;
        }
    }
    
    return true;
}

Tanım ve Yapısal Üstünlük

Miller-Rabin Primality Testi, bir n tam sayısının asallığını sorgulayan, günümüzün en güvenilir ve endüstri standardı kabul edilen

olasılıksal algoritmasıdır.

Bu algoritma, Fermat Testi'nin en büyük zayıflığı olan Carmichael Sayıları sorununu tamamen ortadan kaldırır.

Sayının bileşik olduğunu saptama gücü o kadar yüksektir ki, her iterasyonda hata payını matematiksel olarak dörtte birine düşürür.

Temelinde, n-1 sayısının 2^r * d şeklinde parçalanması ve ardından kuadratik kalıntı analizinin yapılması yatar.

Algoritma İşleyişi ve Güçlü Tanık Analizi

Miller-Rabin, sadece \(a^{n-1} ≡ 1\) olup olmadığına bakmaz; aynı zamanda bu sonuca giden kare alma adımlarını da denetler.

Eğer bir sayı asalsa, 1'in karekökü mod n'de ya 1 ya da -1 (n-1) olmalıdır.

Algoritma, rastgele bir a seçer ve \(a^d \bmod n\) ile başlar.

Ardından r kez kare alarak ilerler.

Eğer bu süreçte "anormal" bir karekök davranışı sezilirse, sayı anında Kesin Bileşik olarak damgalanır.

Adım Adım Yürütme: Süreç, n-1 içindeki tüm 2 çarpanlarını ayıklayan Parçalama Safhası ile başlar.

İterasyon Döngüsü, seçilen 'a' tanığı için önce \(x = a^d \bmod n\) değerini hesaplar.

Eğer \(x=1\) veya \(x=n-1\) ise sayı "asal adayı" olarak bir sonraki tura geçer.

Eğer bu koşul sağlanmazsa, x değeri r-1 kez kare alınarak (x = x² mod n) kontrol edilir.

Döngü bitmeden \(x = n-1\) durumuna ulaşılmazsa, sayı kesinlikle Bileşik olarak ilan edilir.

Performans ve Hız: Miller-Rabin, O(k log³ n) karmaşıklığı ile çalışır.

k arttıkça güvenilirlik logaritmik değil, üstel olarak artar.

Genellikle 40-50 iterasyon, kozmik radyasyonun hata yapma olasılığından bile daha düşük bir hata payı sağlar.

Kriptografik Güç, bu algoritmayı RSA anahtarı üretiminde vazgeçilmez kılar.

Mühendislik başarısı; deterministik kesinlikte ısrar edip sistemi yavaşlatmak yerine, akıllı olasılıksal eşiklerle performansı maksimize etmektir.

function modExp(base, exponent, modulus) {
    let result = 1;
    base = base % modulus;
    
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    
    return result;
}

function millerRabinPrimalityTest(n, k = 5) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0) return false;
    
    let d = n - 1;
    let r = 0;
    while (d % 2 === 0) {
        d = Math.floor(d / 2);
        r++;
    }
    
    for (let i = 0; i < k; i++) {
        const a = Math.floor(Math.random() * (n - 3)) + 2;
        let x = modExp(a, d, n);
        
        if (x === 1 || x === n - 1) {
            continue;
        }
        
        let found = false;
        for (let j = 0; j < r - 1; j++) {
            x = modExp(x, 2, n);
            if (x === n - 1) {
                found = true;
                break;
            }
        }
        
        if (!found) {
            return false;
        }
    }
    
    return true;
}

function millerRabinDeterministic(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0) return false;
    
    const bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
    
    let d = n - 1;
    let r = 0;
    while (d % 2 === 0) {
        d = Math.floor(d / 2);
        r++;
    }
    
    for (const a of bases) {
        if (a >= n) break;
        
        let x = modExp(a, d, n);
        
        if (x === 1 || x === n - 1) {
            continue;
        }
        
        let found = false;
        for (let j = 0; j < r - 1; j++) {
            x = modExp(x, 2, n);
            if (x === n - 1) {
                found = true;
                break;
            }
        }
        
        if (!found) {
            return false;
        }
    }
    
    return true;
}

Tanım ve Aritmetiğin Temel Teoremi

Prime Factorization, 1'den büyük herhangi bir tam sayıyı, çarpıldıklarında orijinal sayıyı veren asal sayılar kümesine ayrıştırma sürecidir.

Aritmetiğin Temel Teoremi'ne göre; her tam sayı, çarpanların sırası gözetilmeksizin, benzersiz bir asal çarpan dizisine sahiptir.

Bu algoritma, bir sayının matematiksel "parmak izini" ortaya çıkarır.

Kriptografiden veri sıkıştırmaya kadar pek çok alanda, karmaşık bir yapıyı en basit bileşenlerine indirgemek için bu atomik analiz yöntemi kullanılır.

Algoritma Prensibi: Tekrarlı Bölme ve √n Sınırı

Algoritma, Trial Division mantığını bir adım ileri taşıyarak "yok etme" prensibiyle çalışır.

Bulunan her asal çarpan, hedef sayıyı küçülterek bir sonraki çarpanın aranacağı uzayı daraltır.

Karekök Optimizasyonu: Bir sayıdan tüm küçük asal çarpanlar ayıklandıktan sonra, kalan sayı hâlâ tam bölünemiyorsa ve denenen çarpan √n sınırını aşmışsa, geriye kalan değerin kendisi asaldır.

Adım Adım Yürütme: İşlem, n çift olduğu sürece 2'ye bölerek başlar. Bu, sayının içindeki tüm "çiftlik" yükünü boşaltır.

Döngü Safhası, 3'ten başlayarak √n limitine kadar tek sayılar üzerinden ilerler ve her adımda \(n \bmod i == 0\) kontrolü yapılır.

Eğer bölünen bulunursa, sayı bu çarpana kalansız bölünemeyene kadar tekrarlı bölme uygulanır ve çarpan listeye eklenir.

Performans ve Hız: Algoritmanın verimliliği, sayının sahip olduğu asal çarpanların büyüklüğüne bağlıdır.

En kötü durumda ( sayı asalsa veya iki büyük asaldan oluşuyorsa ) zaman karmaşıklığı O(√n) seviyesindedir.

Zorluk Bariyeri: Çok büyük iki asal sayının çarpımını çarpanlarına ayırmak, modern süper bilgisayarların bile milyonlarca yılını alabilir; asimetrik şifrelemenin tüm güvenliği bu "hesaplama zorluğuna" dayanır.

function primeFactorization(n) {
    const factors = [];
    
    while (n % 2 === 0) {
        factors.push(2);
        n = Math.floor(n / 2);
    }
    
    let i = 3;
    while (i * i <= n) {
        while (n % i === 0) {
            factors.push(i);
            n = Math.floor(n / i);
        }
        i += 2;
    }
    
    if (n > 2) {
        factors.push(n);
    }
    
    return factors;
}

const number = 9991;
const result = primeFactorization(number);
console.log(`The prime factors of ${number} are: [${result}]`);

function primeFactorizationOptimized(n) {
    if (n < 2) return [];
    if (n === 2) return [2];
    
    const factors = [];
    
    while (n % 2 === 0) {
        factors.push(2);
        n = Math.floor(n / 2);
    }
    
    for (let i = 3; i * i <= n; i += 2) {
        while (n % i === 0) {
            factors.push(i);
            n = Math.floor(n / i);
        }
    }
    
    if (n > 2) {
        factors.push(n);
    }
    
    return factors;
}

Tanım ve Bellek Darboğazı Çözümü

Segmented Sieve, klasik Eratosthenes Kalburu'nun devasa veri setlerinde yaşadığı O(n) alan karmaşıklığı sorununu çözmek için geliştirilmiş hibrit bir algoritmadır.

Standart kalbur yöntemi, milyarlarca sayıyı test etmek için gigabaytlarca RAM gerektirirken; Parçalı Kalbur, hedef aralığı küçük segmentlere ayırarak her seferinde sadece bir parçayı işler.

Bu strateji, bellek ihtiyacını \(n\) değerinden \(\sqrt{n}\) değerine düşürerek, sınırlı donanım kaynaklarıyla devasa sayı aralıklarında asal sayı taraması yapılmasına olanak tanır.

Algoritma Prensibi: İki Aşamalı Eleme

Algoritma "parçala ve fethet" mantığıyla çalışır.

Önce üst sınırın kareköküne kadar olan Temel Asallar bulunur.

Ardından bu asallar, büyük aralığın her bir parçası üzerinde birer "silgi" gibi kullanılır.

Her segment, işlemcinin L1/L2 Cache kapasitesine sığacak şekilde boyutlandırılır.

Bu sayede veriler ana bellek yerine doğrudan CPU önbelleğinde işlenerek işlem hızı maksimize edilir.

Adım Adım Yürütme: Süreç, \(\sqrt{H}\) limitine kadar olan asalları Simple Sieve ile bir diziye kaydederek başlar.

Segmentasyon safhasında, [ L , H ] aralığı \(S\) boyutunda parçalara bölünür ve her parça için geçici, küçük bir boolean dizisi oluşturulur.

Kademeli Eleme işleminde, temel asallar listesindeki her p için parçanın içindeki ilk katı hesaplanır ve o parçadaki tüm katları false olarak işaretlenir.

Her parça bittiğinde elenmemiş sayılar sonuç listesine aktarılır ve bellek sıfırlanarak bir sonraki parçaya geçilir.

Performans ve Hız: Segmented Sieve, klasik kalburun \(O(n \log \log n)\) hızını korurken, alan karmaşıklığını O(√n) seviyesine indirir.

En büyük avantajı, çok geniş aralıklarda çalışırken Out of Memory hatalarını engellemesi ve CPU Cache verimliliğini artırmasıdır.

Uygulama Zorluğu, her segment için başlangıç katlarını hassas bir şekilde hesaplama gerekliliğinden doğan mantıksal karmaşıklıktır.

function segmentedSieve(low, high) {
    if (low > high) return [];
    
    const limit = Math.floor(Math.sqrt(high));
    const isPrime = new Array(limit + 1).fill(true);
    const primes = [];
    
    for (let i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            primes.push(i);
            for (let j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    const rangeSize = high - low + 1;
    const isPrimeRange = new Array(rangeSize).fill(true);
    
    if (low === 1) isPrimeRange[0] = false;
    
    for (const prime of primes) {
        let start = Math.max(prime * prime, Math.ceil(low / prime) * prime);
        
        for (let j = start; j <= high; j += prime) {
            if (j >= low) {
            isPrimeRange[j - low] = false;
            }
        }
    }
    
    const result = [];
    for (let i = 0; i < rangeSize; i++) {
        if (isPrimeRange[i]) {
            result.push(low + i);
        }
    }
    
    return result;
}

const low = 10;
const high = 50;
const primesInRange = segmentedSieve(low, high);
console.log(`Primes in range [${low}, ${high}]: ${primesInRange}`);

const low2 = 1;
const high2 = 100;
const primesInRange2 = segmentedSieve(low2, high2);
console.log(`Primes in range [${low2}, ${high2}]: ${primesInRange2}`);

Tanım ve Öz-Bölen İlişkisi

Perfect Number, kendisi hariç tüm pozitif tam bölenlerinin toplamına tam olarak eşit olan sayılara verilen isimdir.

Antik çağlardan beri matematikçileri büyüleyen bu kavram, sayının kendi içindeki toplamsal simetrisini temsil eder.

Örneğin: 6 sayısının öz-bölenleri olan 1, 2 ve 3 toplandığında sonuç yine 6 olur.

Algoritmik düzeyde biz; bu sayıları tespit etmek için sayının tüm çarpan yapısını hızlıca analiz eden ve "mükemmellik" denklemini

( Sum of Divisors == N ) test eden yöntemler kurgularız.

Algoritma Prensibi: Karekök Tabanlı Çarpan Tespiti

Bir sayının mükemmel olup olmadığını anlamak için tüm sayıları tek tek denemek yerine, çarpanların simetri özelliğini kullanırız.

Karekök kuralına göre; eğer \(i\) sayısı \(N\)'in bir böleniyse, \(N/i\) değeri de otomatik olarak bir bölendir.

Bu sayede arama döngüsünü sadece √N sınırına kadar koşturarak, işlem maliyetini minimize ederiz.

Adım Adım Yürütme: Süreç, toplam değişkenini 1 ile başlatarak ( çünkü 1 her sayının öz-bölenidir ) ve \(N \le 1\) durumlarını eleyerek başlar.

Döngü Safhası, 2 sayısından başlayarak √N limitine kadar ilerler.

Eğer \(N \bmod i == 0\) durumu gerçekleşirse, hem \(i\) hem de eşleniği olan \(N/i\) toplama dahil edilir.

Eğer sayı bir tam kare ise (\(i \cdot i == N\)), aynı sayıyı iki kez eklememek için özel bir tekil ekleme kontrolü yapılır.

Performans ve Hız: Algoritma, O(√N) zaman karmaşıklığı ile çalışır.

Bu hız, düşük ve orta ölçekli sayılarda anlık sonuç verse de, Mersenne asalları ile ilişkili devasa mükemmel sayıların keşfinde yetersiz kalır.

Deterministik Güç: Bu yöntem, olasılıksal değildir; sonucun doğruluğu tam matematiksel ispata dayanır.

function isPerfectNumber(num) {
  if (num <= 1) {
    return false;
  }

  let sumOfDivisors = 1; 
  const limit = Math.sqrt(num);

  for (let i = 2; i <= limit; i++) {
    if (num % i === 0) {
      sumOfDivisors += i;
      if (i * i !== num) {
        sumOfDivisors += num / i;
      }
    }
  }

  return sumOfDivisors === num;
}

console.log(isPerfectNumber(6));  // true
console.log(isPerfectNumber(28)); // true
console.log(isPerfectNumber(496)); // true
console.log(isPerfectNumber(12)); // false

Tanım ve Karşılıklı Bölen İlişkisi

Amicable Number, her birinin kendisi hariç pozitif tam bölenlerinin toplamı, diğer sayıya eşit olan özel bir sayı çiftidir.

Pisagor'dan beri bilinen bu ilişki, sayıların yapısal simetrisini "ikili" bir düzleme taşır.

Resmi olarak: \(a\) ve \(b\) gibi iki sayı için; SumOfDivisors(a) == b VE SumOfDivisors(b) == a şartı sağlanmalıdır ( burada \(a \neq b\) ).

Tarihteki en ünlü örnek, ( 220, 284 ) çiftidir.

220'nin öz bölenleri toplandığında 284 elde edilirken, 284'ün öz bölenleri toplandığında tam olarak 220 sonucuyla karşılaşılır.

Algoritma Prensibi: Çift Yönlü Doğrulama

Algoritma, bir sayının çarpan yapısını analiz edip sonuçtan tekrar geriye ulaşmaya çalışır.

Bu, veritabanı yönetimindeki Foreign Key ilişkisine benzer bir bütünlük kontrolüdür.

Bölenler Toplamı Optimizasyonu: Her sayı için tüm bölenleri aramak yerine, arama uzayını √n ile sınırlayarak asimptotik hızı koruruz.

Adım Adım Yürütme: Arama süreci 2'den başlayarak belirli bir \(N\) limitine kadar bir Dış Döngü koşturur.

İlk Analiz aşamasında, mevcut \(a\) sayısının öz bölenleri toplanarak bir \(b\) adayı elde edilir.

İkinci Analiz aşamasında, bulunan bu \(b\) adayı için öz bölenler tekrar toplanır.

Eğer sonuç başlangıçtaki \(a\) sayısına eşitse ve \(a \neq b\) ise, bir Dost Çift bulunmuş olur.

Performans ve Hız: Algoritma, ham tarama limitine bağlı olarak O(N√N) zaman karmaşıklığı ile çalışır.

Bu, tarama aralığı büyüdükçe CPU yükünün ağırlaşması anlamına gelir.

Bellek Stratejisi: Daha önce hesaplanmış bölen toplamlarını bir Lookup Table üzerinde saklamak, mükerrer hesaplamaları önleyerek hızı artırır ancak alan maliyetini yükseltir.

function sumOfProperDivisors(n) {
  let sum = 1;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      sum += i;
      if (i * i !== n) {
        sum += n / i;
      }
    }
  }
  return sum;
}

function findAmicablePair(n) {
  const sumN = sumOfProperDivisors(n);
  if (sumN > n) {
    const sumM = sumOfProperDivisors(sumN);
    if (sumM === n) {
      return [n, sumN];
    }
  }
  return null;
}

function findAmicableNumbersUpTo(limit) {
  const amicablePairs = [];
  const foundPairs = new Set();
  for (let num = 2; num <= limit; num++) {
    const pair = findAmicablePair(num);
    if (pair && !foundPairs.has(pair[0]) && !foundPairs.has(pair[1])) {
      amicablePairs.push(pair);
      foundPairs.add(pair[0]);
      foundPairs.add(pair[1]);
    }
  }
  return amicablePairs;
}

const amicableList = findAmicableNumbersUpTo(300);
console.log(amicableList);

Tanım ve Yapısal Karakteristik

Mersenne Primes, \(M_p = 2^p - 1\) formülüne uyan ve kendisi de bir asal sayı olan nadir tam sayılardır.

Bu formüldeki \(p\) üssünün kendisi de mutlaka bir asal sayı olmalıdır; aksi halde sonuç otomatik olarak bileşik çıkar.

Adını Marin Mersenne'den alan bu sınıf, evrendeki en büyük asal sayıların yuvasıdır.

Kriptografik güvenliğin sınırlarını zorlamaktan, rastgele sayı üreticilerine kadar dijital dünyanın en uç noktalarında görev yaparlar.

Algoritmik düzeyde bu sayılar, standart asallık testlerinin "hesaplama duvarına" çarptığı noktada başlar.

Milyonlarca haneli bir sayıyı test etmek için genel amaçlı algoritmalar yerine, bu yapıya özel Lucas-Lehmer Testi kullanılır.

Lucas-Lehmer Testi: Deterministik Kesinlik

Lucas-Lehmer algoritması, bir Mersenne sayısının asallığını olasılıklara yer bırakmadan, tam bir deterministik ispatla ortaya koyar.

Testin verimliliği, modüler aritmetiği Mersenne sayılarının bit yapısına (binary) uygun şekilde manipüle edebilmesinden gelir.

Algoritma, \(s_0 = 4\) değeriyle başlayan bir dizi üzerinden ilerler ve her adımda sayının karesi alınır ve 2 çıkarılır.

Eğer \(p-2\) adım sonunda elde edilen rezidü \(M_p\) modülünde sıfıra ulaşırsa, sayı asaldır.

Adım Adım Yürütme: Süreç, \(p\) üssünün asallığını Miller-Rabin gibi hızlı bir yöntemle doğrulayan bir Ön Koşul Testi ile başlar ve iteratif döngü, \(p-2\) kez tekrarlanır.

Her döngüde \(s = (s^2 - 2) \bmod (2^p - 1)\) işlemi koşturulur.

Bu işlem sırasında oluşan devasa sayıları kontrol altında tutmak için Byteomi mühendisliğinde Hızlı Fourier Dönüşümü (FFT) tabanlı çarpma teknikleri devreye girer, sonuç 0 ise "Kraliyet Asalı" onaylanır.

Performans ve Hız: Lucas-Lehmer testi, \(O(p^2 \cdot \log p)\) veya FFT optimizasyonuyla \(O(p \cdot \log p \cdot \log \log p)\) karmaşıklığına sahiptir.

Donanım Bağımlılığı: Milyonlarca basamaklı sayıları işlemek, standart 64-bit işlemcilerin kapasitesini aştığı için BigInt ve GPU tabanlı paralel hesaplama mimarileri zorunludur.

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  for (let i = 5; i * i <= n; i = i + 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
  return true;
}

function lucasLehmerTest(p) {
  if (!isPrime(p)) {
    return false;
  }
  
  const mersenneM = (2n ** BigInt(p)) - 1n;
  let s = 4n;

  for (let i = 0; i < p - 2; i++) {
    s = (s * s - 2n) % mersenneM;
  }

  return s === 0n;
}

function findMersennePrimes(count) {
  let primesFound = 0;
  let p = 2;
  while (primesFound < count) {
    if (isPrime(p)) {
      if (lucasLehmerTest(p)) {
        const mersennePrime = (2n ** BigInt(p)) - 1n;
        console.log(`Mersenne Prime found: M(${p}) = ${mersennePrime}`);
        primesFound++;
      }
    }
    p++;
  }
}

findMersennePrimes(4);

Tanım ve Tarihsel Yanılgı

Fermat Numbers, \(F_n = 2^{2^n} + 1\) formülüne sahip olan ve n'nin her artışında boyutu akıl almaz bir hızla katlanan özel bir tam sayı sınıfıdır.

Pierre de Fermat, başlangıçta bu formdaki tüm sayıların asal olduğunu iddia etmiş olsa da; günümüzde sadece ilk beş Fermat sayısının (\(F_0\) - \(F_4\)) asal olduğu bilinmektedir.

\(F_5\) değerinden itibaren bu sayılar, devasa boyutlardaki Bileşik yapılara dönüşür.

Algoritmik düzeyde bu sayılar, bilgisayar biliminin hesaplama kapasitesini ölçmek için kullanılan birer laboratuvar gibidir. Standart testlerin yetersiz kaldığı bu zirvede, sadece bu yapıya özel tasarlanmış Pepin Testi hüküm sürer.

Pepin Testi: Fermat Yapısına Özel Kesinlik

Pepin Testi, Fermat sayılarının asallığını olasılıklara yer bırakmadan kanıtlayan, zarif bir deterministik algoritmadır.

Miller-Rabin gibi rastgele tanıklara ihtiyaç duymaz; tek bir sabit taban üzerinden hüküm verir.

Temel motoru modüler aritmetiğe dayanır: Bir \(F_n\) sayısının asal kabul edilmesi için \(3^{(F_n-1)/2} \equiv -1 \pmod{F_n}\) eşitliğini tam olarak sağlaması şarttır.

Bu, Fermat sayısının içsel simetrisinin bir asallık imzasıdır.

Adım Adım Yürütme: Süreç, verilen n değeri için \(F_n = 2^{2^n} + 1\) sayısının BigInt mimarisiyle hesaplanmasıyla başlar.

Üs Analizi safhasında, test için gereken kritik üs değeri \(E = (F_n-1)/2\) olarak belirlenir.

Modüler Operasyon adımında, \(3^E \pmod{F_n}\) işlemi yüksek verimli Binary Exponentiation tekniğiyle koşturulur.

Eğer nihai sonuç \(F_n - 1\) (\(-1\)'e denk) ise, sayı tartışmasız bir Fermat Asalıdır. Diğer tüm durumlarda "Bileşik" damgasını alır.

Performans ve Hız: Pepin Testi, Fermat sayısının devasa bit genişliği nedeniyle O(2^n) veya logaritmik olarak \(O(\log^2 F_n)\) karmaşıklığına sahiptir.

Hafıza Bariyeri: \(F_n\) sayıları "çift üstel" büyüdüğü için, örneğin \(F_{20}\) gibi bir sayıyı sadece bellekte saklamak bile modern veri merkezlerinin sınırlarını zorlayabilir.

function pepinTest(n) {
  if (n <= 0) {
    return false;
  }
  
  const fermatNumber = (2n ** (2n ** BigInt(n))) + 1n;
  
  // Modüler üs alma fonksiyonu (exponentiation by squaring)
  function modular_pow(base, exp, mod) {
    let res = 1n;
    base %= mod;
    while (exp > 0) {
      if (exp % 2n === 1n) {
        res = (res * base) % mod;
      }
      base = (base * base) % mod;
      exp /= 2n;
    }
    return res;
  }
  
  const exponent = (fermatNumber - 1n) / 2n;
  const result = modular_pow(3n, exponent, fermatNumber);
  
  return result === fermatNumber - 1n;
}

function findFermatPrimes(count) {
  let primesFound = 0;
  let n = 0;
  while (primesFound < count) {
    if (pepinTest(n)) {
      const fermatNumber = (2n ** (2n ** BigInt(n))) + 1n;
      console.log(`Fermat Prime found: F(${n}) = ${fermatNumber}`);
      primesFound++;
    }
    n++;
  }
}

findFermatPrimes(5);

Tanım ve Atomik Birleştirme

LCM (Least Common Multiple), verilen iki veya daha fazla tam sayının ortak katları arasında yer alan, sıfırdan farklı en küçük pozitif tam sayıdır.

Asal çarpanlara ayırma yöntemiyle LCM bulma; sayıları en temel yapı taşlarına indirgeme ve bu çarpanların her birinin en yüksek kuvvetlerini sentezleyerek kapsayıcı bir üst yapı oluşturma sürecidir.

Bu yöntem, sayıların içsel mimarisini ortaya koyduğu için LCM'nin matematiksel kökenini anlamanın en kesin yoludur.

Algoritma Prensibi: Maksimum Kuvvetler Birliği

Algoritmanın ana motoru "kapsayıcılık" ilkesidir.

Sonuç (LCM), hem \(a\) sayısını hem de \(b\) sayısını içinde tam olarak barındırmalıdır.

Bunun için her iki sayının asal çarpan listeleri taranır.

Kuvvet Seçimi: Eğer bir asal çarpan her iki sayıda da varsa, en yüksek üsse (kuvvete) sahip olan seçilir.

Eğer bir çarpan sadece bir sayıda varsa, o çarpan da LCM'ye dahil edilir.

Bu, ortak katın "en küçük" olmasını garanti eder.

Adım Adım Yürütme: Süreç, verilen sayıları Prime Factorization algoritmasıyla atomlarına ayırarak başlar.

Haritalama Safhası: Tüm benzersiz asal tabanlar bir kümede toplanır, her taban için sayıların içindeki üsler karşılaştırılır.

Sentezleme: Seçilen maksimum kuvvetler (\(p_1^{max1} \cdot p_2^{max2} \dots\)) birbiriyle çarpılarak Nihai LCM değeri inşa edilir.

Performans ve Hız: Bu yöntemin hızı, asal çarpanlara ayırma işleminin maliyeti olan O(√n) ile doğrudan ilişkilidir.

Verimlilik Analizi: Küçük sayılarda çok şık bir çözüm sunsa da, büyük sayılarda Öklid Algoritması tabanlı formül (\(LCM = |a \cdot b| / GCD\)) çok daha hızlı sonuç verir.

function primeFactors(n) {
    const factors = [];
    while (n % 2 === 0) {
        factors.push(2);
        n /= 2;
    }
    for (let i = 3; i * i <= n; i += 2) {
        while (n % i === 0) {
            factors.push(i);
            n /= i;
        }
    }
    if (n > 2) factors.push(n);
    return factors;
}

function lcmViaFactors(a, b) {
    const factorsA = primeFactors(a);
    const factorsB = primeFactors(b);
    let result = 1;
    const unique = Array.from(new Set([...factorsA, ...factorsB]));
    unique.forEach(f => {
        const count = Math.max(factorsA.filter(x => x === f).length, factorsB.filter(x => x === f).length);
        result *= Math.pow(f, count);
    });
    return result;
}

console.log(primeFactors(84));
console.log(lcmViaFactors(12, 18));

Tanım ve Fonksiyonel Formül

GCD Tabanlı LCM bulma yöntemi, iki sayının çarpımı ile onların en büyük ortak böleni arasındaki doğrusal ilişkiyi kullanan son derece verimli bir algoritmadır.

Bu yöntemin temelinde yatan evrensel formül: LCM(a, b) = |a * b| / GCD(a, b) şeklindedir.

Asal çarpanlara ayırma gibi maliyetli işlemler yerine, sadece temel aritmetik operasyonları ve hızlı Öklid algoritmasını kullanır.

Yazılım mühendisliğinde, LCM ihtiyacı duyulan hemen her senaryoda hızı ve sadeliği nedeniyle bu formülasyon standart kabul edilir.

Algoritma Prensibi: Öklid ile Logaritmik Hız

Algoritmanın motoru, GCD hesaplamak için kullanılan Öklid Algoritması'dır.

Bu algoritma logaritmik zamanda çalıştığı için, çok büyük sayılarda bile LCM değerini neredeyse anlık olarak üretir.

Mühendislik Önceliği: Klasik formülde önce çarpma işlemi yapılması, büyük sayılarda Integer Overflow riskini doğurur.

Byteomi standartlarında biz bu riski, işlemi \((a / GCD(a, b)) * b\) sırasıyla yaparak minimize ederiz.

Adım Adım Yürütme: Süreç, verilen a ve b sayılarının Öklid Algoritması ile GCD'sinin bulunmasıyla başlar.

Sayısal Güvenlik aşamasında, taşma hatasını önlemek adına a sayısı önce GCD'ye bölünür.

Nihai Çarpım: Bölüm sonucu elde edilen değer, b sayısı ile çarpılarak En Küçük Ortak Kat değerine ulaşılır.

Performans ve Hız: Algoritma, Öklid'in performansı olan O(log(min(a, b))) karmaşıklığıyla çalışır.

Bu, sayı teorisindeki en hızlı hesaplama yöntemlerinden biridir.

Taşma Yönetimi: Formülün sırası değiştirilse bile, nihai LCM değeri veri tipinin kapasitesini aşıyorsa sonuç hatalı çıkabilir; bu yüzden çok büyük sayılarda BigInt kullanımı zorunludur.

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcm(a, b) {
    return Math.abs(a * b) / gcd(a, b);
}

function lcmMultiple(numbers) {
    if (numbers.length === 0) return 0;
    if (numbers.length === 1) return Math.abs(numbers[0]);
    
    let result = Math.abs(numbers[0]);
    for (let i = 1; i < numbers.length; i++) {
        result = lcm(result, Math.abs(numbers[i]));
    }
    return result;
}

function lcmSafe(a, b) {
    const gcdValue = gcd(a, b);
    return Math.abs(a / gcdValue) * Math.abs(b);
}

function gcdRecursive(a, b) {
    return b === 0 ? a : gcdRecursive(b, a % b);
}

function lcmRecursive(a, b) {
    return Math.abs(a * b) / gcdRecursive(a, b);
}
                        

Tanım ve Yapısal Ayrıştırma

Trial Division Factorization, verilen bir bileşik tam sayıyı, çarpıldıklarında o sayıyı veren asal çarpanlar dizisine dönüştüren en kadim ve temel algoritmadır.

Algoritmanın ana misyonu, sayıyı en küçük asal olan 2'den başlayarak sistematik bir şekilde bölmek ve "atomik" hale gelene kadar bu işlemi sürdürmektir.

Bu süreç, sayının matematiksel özünü ortaya çıkarır.

Algoritma Prensibi: Tekrarlı Bölme ve Karekök Kısıtı

Algoritma, ham bir bölme işleminden ziyade iki ana strateji ile güçlendirilmiştir:

Tekrarlı Bölme (Exhaustive Division): Bir asal çarpan bulunduğunda, sayı artık o çarpana tam bölünemeyene kadar while loop mekanizmasıyla küçültülür.

Bu, aynı çarpanın kuvvetlerini ( 12 için 2² gibi ) hatasız yakalamayı sağlar.

Karekök Kuralı: Bir bileşik sayının çarpan araması, sayının güncel değerinin √N sınırını geçtiği anda durdurulur.

Eğer bu sınıra kadar çarpan bulunamazsa, geriye kalan sayı asaldır.

Adım Adım Yürütme: Süreç, sayıyı tüm çift çarpanlarından arındıran Bölme-2 safhasıyla başlar.

Asimetrik Arama: 3'ten başlayarak √N sınırına kadar sadece tek sayılar üzerinden potansiyel çarpanlar taranır.

Kalıntı Kontrolü: Tüm döngüler bittiğinde eğer N > 1 ise, geriye kalan bu değer son Asal Çarpan olarak listeye eklenir.

Performans ve Hız: Algoritma, O(√n) zaman karmaşıklığı ile çalışır.

Küçük ve orta ölçekli sayılar için deterministik ve kusursuzdur.

Sezgisel Yaklaşım: Bu algoritma, bir sayıyı "bitirinceye kadar" sorgulayan inatçı bir müfettiş gibidir.

Karmaşık problemleri daha küçük alt problemlere bölerek hesaplama karmaşıklığını basitleştirmenin en güzel örneğidir.

function trialDivisionFactorize(n) {
    const factors = [];
    while (n % 2 === 0) {
        factors.push(2);
        n /= 2;
    }
    for (let i = 3; i * i <= n; i += 2) {
        while (n % i === 0) {
            factors.push(i);
            n /= i;
        }
    }
    if (n > 2) factors.push(n);
    return factors;
}

console.log(trialDivisionFactorize(84)); // [2, 2, 3, 7]

Tanım ve İki Kare Farkı Özdeşliği

Fermat Factorization, verilen bir tek tam sayıyı iki tam karenin farkı olarak ifade ederek çarpanlarına ayıran, Pierre de Fermat imzalı zarif bir algoritmadır.

Algoritmanın kalbi, ortaokul cebirinden tanıdığımız a² - b² = (a-b)(a+b) özdeşliğine dayanır.

Eğer bir N sayısını iki karenin farkı olarak yazabilirsek, çarpanlarını doğrudan \(p = a-b\) ve \(q = a+b\) olarak elde ederiz.

Bu yöntem, Trial Division'ın aksine sayıları tek tek bölmek yerine, tam kare bir b² değeri bulmak için sistematik bir tarama koşturur.

Algoritma Prensibi: Karekökten Başlayan Arama

Algoritma, \(a\) değeri için arama işlemini en mantıklı noktadan, yani ⌈√N⌉ (N'nin karekökünden büyük veya eşit en küçük tam sayı) değerinden başlatır.

Arama Stratejisi: Her adımda \(b^2 = a^2 - N\) değeri hesaplanır.

Eğer elde edilen bu sonuç mükemmel bir tam kareyse ( 9, 16, 25... ), aranan \(b\) değeri bulunmuş demektir.

Aksi takdirde \(a\) bir artırılır ve yeni bir tam kare adayı sorgulanır.

Adım Adım Yürütme: Süreç, N sayısının tek olduğunu ( çünkü çift sayılar bu formülde verimsizdir ) doğrulayarak başlar.

İterasyon Fazı: \(a\) başlangıç noktasından itibaren \(a^2 - N\) işleminin sonucunu denetler.

Tam Kare Testi: İşlemcinin sqrt fonksiyonu veya bit düzeyindeki tam kare testleri ile sonucun bir tam sayı olup olmadığına bakılır.

İlk eşleşmede döngü kırılır ve çarpanlar p = a-b ve q = a+b formülleriyle anında hesaplanır.

Performans ve Hız: Fermat algoritması, çarpanlar (\(p\) ve \(q\)) birbirine ne kadar yakınsa o kadar üstel bir hızda çalışır.

Mühendislik Kısıtı: Eğer çarpanlar birbirinden çok uzaksa ( biri 3, diğeri devasa bir asal ise ), algoritma \(O(N)\) karmaşıklığına kadar gerileyerek performans felaketine yol açabilir.

function isPerfectSquare(x) {
    const s = Math.floor(Math.sqrt(x));
    return s * s === x;
}

function fermatFactorize(n) {
    if (n <= 0) return null;
    if (n % 2 === 0) return [2, n / 2];

    let a = Math.ceil(Math.sqrt(n));
    let b2 = a * a - n;

    while (!isPerfectSquare(b2)) {
        a += 1;
        b2 = a * a - n;
    }

    const b = Math.sqrt(b2);
    return [a - b, a + b];
}

console.log(fermatFactorize(5959));

Tanım ve Problem İndirgeme

Quadratic Sieve (QS), özellikle 50 ile 100 basamak arasındaki tam sayıları çarpanlarına ayırmak için kullanılan, Fermat Factorization mantığını modern bir seviyeye taşıyan yüksek performanslı bir algoritmadır.

Algoritma, doğrudan bölme yapmak yerine \(x^2 \equiv y^2 \pmod{N}\) formundaki modüler kare eşitliklerini arar.

Bu eşitlik bulunduğunda, \(N\) sayısının çarpanları \(GCD(x-y, N)\) ve \(GCD(x+y, N)\) operasyonlarıyla gün yüzüne çıkarılır.

1990'ların başına kadar dünyanın en hızlı çarpanlara ayırma yöntemi kabul edilen bu algoritma, günümüzde hala 100 basamağa kadar olan sayılar için altın standart niteliğindedir.

Algoritma Prensibi: Eleme ve Matris Çözümlemesi

QS, problemi çözmek için "Smooth Numbers" kavramını kullanır.

Bir sayının çarpanları sadece önceden belirlenmiş küçük asallardan ( Factor Base ) oluşuyorsa, o sayı "smooth" kabul edilir.

Doğrusal Cebir Entegrasyonu: Algoritma, binlerce pürüzsüz sayı toplar ve bunların asal çarpan kuvvetlerini bir Binary Matrix haline getirir.

Bu matris üzerinde Gauss Eliminasyonu koşturularak, çarpımları tam kare olan özel bir alt küme bulunur.

Adım Adım Yürütme: Süreç, \(N\) sayısının boyutuna göre optimize edilmiş bir Faktör Tabanı oluşturulmasıyla başlar.

Eleme (Sieving) Safhası: Çok sayıda \(x^2 \pmod{N}\) değeri taranır ve sadece faktör tabanındaki asallara tam bölünebilenler "ilişki" olarak kaydedilir.

Matris Çözümü: Toplanan bu veriler, sonlu alanlar üzerinde Gaussian Elimination ile işlenerek aranan \(x^2 \equiv y^2\) dengesi kurulur.

Son adımda, elde edilen tam kareler üzerinden EBOB hesaplanarak \(N\)'in gizli çarpanları deşifre edilir.

Performans ve Hız: QS, alt-üstel bir karmaşıklığa sahiptir: \(O(e^{\sqrt{\ln N \ln \ln N}})\).

Bu, sayı büyüdükçe hızın Trial Division gibi algoritmalara göre çok daha yavaş düştüğü anlamına gelir.

Paralel Hesaplama: Eleme aşaması bağımsız parçalara bölünebildiği için, QS modern süper bilgisayarlarda ve dağıtık sistemlerde mükemmel bir verimle çalışır.

function isPrime(n) {
    if (n < 2) return false;
    for (let i = 2; i * i <= n; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

function isSmooth(n, factorBase) {
    for (let p of factorBase) {
        while (n % p === 0) {
            n /= p;
        }
    }
    return n === 1;
}

function getExponentVector(n, factorBase) {
    const vector = [];
    for (let p of factorBase) {
        let exponent = 0;
        while (n % p === 0) {
            n /= p;
            exponent++;
        }
        vector.push(exponent % 2);
    }
    return vector;
}

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return Math.abs(a);
}

function gaussianElimination(matrix) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let rank = 0;
    
    for (let col = 0; col < cols && rank < rows; col++) {
        let pivot = -1;
        for (let row = rank; row < rows; row++) {
            if (matrix[row][col] === 1) {
                pivot = row;
                break;
            }
        }
        
        if (pivot !== -1) {
            [matrix[rank], matrix[pivot]] = [matrix[pivot], matrix[rank]];
            
            for (let row = 0; row < rows; row++) {
                if (row !== rank && matrix[row][col] === 1) {
                    for (let c = 0; c < cols; c++) {
                        matrix[row][c] = (matrix[row][c] + matrix[rank][c]) % 2;
                    }
                }
            }
            rank++;
        }
    }
    
    return matrix.slice(rank);
}

function quadraticSieveModel(n, factorBaseLimit) {
    if (n % 2 === 0) return [2, n / 2];
    
    const factorBase = [];
    for (let p = 2; p <= factorBaseLimit; p++) {
        if (isPrime(p) && n % p !== 0) {
            factorBase.push(p);
        }
    }
    
    const relations = [];
    const sqrtN = Math.floor(Math.sqrt(n));
    
    for (let k = 1; k < 1000; k++) {
        const x = sqrtN + k;
        let y = (x * x) % n;
        
        if (isSmooth(y, factorBase)) {
            const exponentVector = getExponentVector(y, factorBase);
            relations.push([x, exponentVector]);
        }
        
        if (relations.length > factorBase.length) break;
    }
    
    if (relations.length <= factorBase.length) return null;
    
    const matrix = relations.map(rel => rel[1]);
    const nullSpace = gaussianElimination(matrix);
    
    for (let nullVector of nullSpace) {
        let xProduct = 1;
        let yProduct = 1;
        
        for (let i = 0; i < relations.length; i++) {
            if (nullVector[i] === 1) {
                xProduct = (xProduct * relations[i][0]) % n;
                const y = (relations[i][0] * relations[i][0]) % n;
                yProduct = (yProduct * y) % n;
            }
        }
        
        const factor = gcd(Math.abs(xProduct - Math.sqrt(yProduct)), n);
        if (factor !== 1 && factor !== n) {
            return [factor, n / factor];
        }
    }
    
    return null;
}

Tanım ve Olasılıksal Yaklaşım

Pollard's Rho, özellikle 10 ile 60 basamaklı bileşik sayıları çarpanlarına ayırmak için tasarlanmış, rastgele dizi ilerlemeleri üzerinden sonuç üreten olasılıksal bir algoritmadır.

Algoritma, adını sayının modüler bir fonksiyon altında ürettiği dizinin görselleştiğinde Yunan alfabesindeki ρ (rho) harfine benzemesinden alır.

Trial Division algoritması hantal kaldığı, Quadratic Sieve algoritması ise fazla karmaşık olduğu "orta-üst" segmentte en verimli çözümdür.

Temel felsefesi, N sayısını bölmek yerine, dizideki iki elemanın farkı ile N'nin ortak bir bölenini ( GCD ) yakalamaya dayanır.

Algoritma Prensibi: Tortoise and Hare (Kaplumbağa ve Tavşan)

Algoritma, Floyd'un döngü bulma metodolojisini kullanır.

Dizideki iki işaretçiden biri ( Kaplumbağa ) birer adım ilerlerken, diğeri ( Tavşan ) ikişer adım ilerler.

Doğum Günü Paradoksu Etkisi: Rastgele seçilen sayılar arasındaki farkın, N'nin bir çarpanı olan \(p\) sayısına bölünme olasılığı, sayıların doğrudan \(p\)'ye eşit olma olasılığından çok daha yüksektir.

Bu paradoks, Pollard's Rho'nun beklenmedik hızının ana kaynağıdır.

Adım Adım Yürütme: Arama, rastgele bir \(x_0\) başlangıç değeri ve \(f(x) = (x^2 + c) \bmod N\) şeklinde bir Polinom Fonksiyonu ile başlar.

Döngü Safhası: Kaplumbağa \(x = f(x)\) ve Tavşan \(y = f(f(y))\) olarak güncellenir ve her adımda \(GCD(|x - y|, N)\) kontrol edilir.

Eğer bu GCD değeri 1'den büyük ve N'den küçük bir değer (\(d\)) üretirse, bir Asal Çarpan başarıyla yakalanmış olur.

Sonuç N çıkarsa, farklı bir \(c\) sabiti ile test yeniden başlatılır.

Performans ve Hız: Pollard's Rho, en küçük asal çarpan \(p\) olmak üzere yaklaşık O(√p) adımda sonuç verir.

Bu, Trial Division algoritmasının \(O(√N)\) olan karmaşıklığına göre devasa bir optimizasyondur.

Bellek Verimliliği: Algoritma sadece birkaç değişken sakladığı için \(O(1)\) alan karmaşıklığıyla çalışır; bu da onu bellek kısıtlı donanımlarda rakipsiz kılar.

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function pollardsRho(n) {
    if (n % 2 === 0) return 2;
    if (n === 1) return 1;
    
    let x = 2;
    let y = 2;
    let d = 1;
    
    const f = (x) => (x * x + 1) % n;
    
    while (d === 1) {
        x = f(x);
        y = f(f(y));
        d = gcd(Math.abs(x - y), n);
    }
    
    return d === n ? null : d;
}

function pollardsRhoWithCustomFunction(n, c = 1) {
    if (n % 2 === 0) return 2;
    if (n === 1) return 1;
    
    let x = 2;
    let y = 2;
    let d = 1;
    
    const f = (x) => (x * x + c) % n;
    
    while (d === 1) {
        x = f(x);
        y = f(f(y));
        d = gcd(Math.abs(x - y), n);
    }
    
    return d === n ? null : d;
}

function pollardsRhoWithBrent(n) {
    if (n % 2 === 0) return 2;
    if (n === 1) return 1;
    
    let y = Math.floor(Math.random() * (n - 1)) + 1;
    let c = Math.floor(Math.random() * (n - 1)) + 1;
    let m = Math.floor(Math.random() * (n - 1)) + 1;
    
    let g = 1;
    let r = 1;
    let q = 1;
    
    while (g === 1) {
        let x = y;
        for (let i = 0; i < r; i++) {
            y = (y * y + c) % n;
        }
        
        let k = 0;
        while (k < r && g === 1) {
            let ys = y;
            for (let i = 0; i < Math.min(m, r - k); i++) {
                y = (y * y + c) % n;
                q = (q * Math.abs(x - y)) % n;
            }
            g = gcd(q, n);
            k += m;
        }
        r *= 2;
    }
    
    if (g === n) {
        do {
            ys = (ys * ys + c) % n;
            g = gcd(Math.abs(x - ys), n);
        } while (g === 1);
    }
    
    return g === n ? null : g;
}

function pollardsRhoCompleteFactorization(n) {
    if (n <= 1) return [];
    if (n === 2) return [2];
    
    const factors = [];
    const stack = [n];
    
    while (stack.length > 0) {
        const current = stack.pop();
        
        if (current === 1) continue;
        
        if (isPrime(current)) {
            factors.push(current);
            continue;
        }
        
        const factor = pollardsRho(current);
        if (factor === null || factor === current) {
            factors.push(current);
        } else {
            stack.push(factor);
            stack.push(current / factor);
        }
    }
    
    return factors.sort((a, b) => a - b);
}

function pollardsRhoWithMultipleAttempts(n, maxAttempts = 10) {
    if (n % 2 === 0) return 2;
    if (n === 1) return 1;
    
    for (let attempt = 0; attempt < maxAttempts; attempt++) {
        const c = Math.floor(Math.random() * (n - 1)) + 1;
        const factor = pollardsRhoWithCustomFunction(n, c);
        
        if (factor !== null && factor !== n) {
            return factor;
        }
    }
    
    return null;
}

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) {
            return false;
        }
    }
    
    return true;
}

function pollardsRhoWithTimeLimit(n, timeLimitMs = 5000) {
    if (n % 2 === 0) return 2;
    if (n === 1) return 1;
    
    const startTime = Date.now();
    let x = 2;
    let y = 2;
    let d = 1;
    
    const f = (x) => (x * x + 1) % n;
    
    while (d === 1 && (Date.now() - startTime) < timeLimitMs) {
        x = f(x);
        y = f(f(y));
        d = gcd(Math.abs(x - y), n);
    }
    
    if ((Date.now() - startTime) >= timeLimitMs) {
        return null;
    }
    
    return d === n ? null : d;
}

Tanım ve Modüler İndirgeme

Euclidean Algorithm, iki pozitif tam sayının En Büyük Ortak Bölenini bulmak için kullanılan, tarihin bilinen en verimli ve zarif algoritmalarından biridir.

M.Ö. 300'lü yıllarda Öklid tarafından tanımlanan bu yöntem, sayıları çarpanlarına ayırmak gibi maliyetli bir yola girmek yerine, ardışık bölme işlemlerinin kalanlarını kullanarak sonucu doğrudan yakalar.

Algoritmanın Çekirdek Mantığı: İki sayının ortak böleni, aynı zamanda bu sayıların farkını ve birbirine bölümünden kalanını da tam bölmek zorundadır.

Bu değişmez kural, sayıları adım adım küçülterek çözüme ulaştırır.

Algoritma Prensibi: Kalanların Simetrisi

Öklid algoritması, GCD(a, b) = GCD(b, a % b) denklemi üzerine kuruludur.

Bu kural, büyük olan sayıyı her adımda küçük olanın "kalanı" ile yer değiştirerek arama uzayını hızla daraltır.

Döngüsel İniş: Bölme işleminde kalan sıfır olana kadar bu yer değiştirme devam eder.

Kalanın sıfır olduğu andaki bölene ulaştığımızda, o değer her iki orijinal sayıyı da bölebilen en büyük tam sayıdır.

Adım Adım Yürütme: Süreç, verilen iki sayının hangisinin daha büyük olduğunun tespitiyle başlar.

İndirgeme Safhası: \(a\) sayısı \(b\)'ye bölünür ve kalan \(r\) hesaplanır.

Ardından \(a\) yerine \(b\), \(b\) yerine ise \(r\) atanır.

Terminasyon (Bitiş): Bu döngü, kalan \(r=0\) olana kadar sürdürülür.

Son sıfırdan farklı kalan değeri, aradığımız EBOB sonucudur.

Performans ve Hız: Öklid Algoritması, O(log(min(a, b))) zaman karmaşıklığı ile çalışır.

Bu logaritmik hız, trilyonlarca basamaklı sayılarda bile saniyeler içinde sonuç alınmasını sağlar.

Lame Teoremi: Algoritmanın en kötü durum senaryosu, ardışık Fibonacci sayılarıdır; çünkü bu sayılar kalanlar arasında en yavaş küçülmeyi gösteren yapılardır.

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function gcdRecursive(a, b) {
    return b === 0 ? a : gcdRecursive(b, a % b);
}

function extendedGcd(a, b) {
    if (a === 0) {
        return { gcd: b, x: 0, y: 1 };
    }
    
    let result = extendedGcd(b % a, a);
    let gcd = result.gcd;
    let x1 = result.x;
    let y1 = result.y;
    
    let x = y1 - Math.floor(b / a) * x1;
    let y = x1;
    
    return { gcd: gcd, x: x, y: y };
}

function modInverse(a, m) {
    let result = extendedGcd(a, m);
    if (result.gcd !== 1) {
        throw new Error("Modular inverse doesn't exist");
    }
    return ((result.x % m) + m) % m;
}

function binaryGcd(a, b) {
    if (a === 0) return b;
    if (b === 0) return a;
    
    let shift = 0;
    while (((a | b) & 1) === 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    
    while ((a & 1) === 0) {
        a >>= 1;
    }
    
    do {
        while ((b & 1) === 0) {
            b >>= 1;
        }
        
        if (a > b) {
            [a, b] = [b, a];
        }
        b = b - a;
    } while (b !== 0);
    
    return a << shift;
}

Tanım ve Basamak Bazlı Simülasyon

Lehmer's GCD Algorithm, klasik Öklid yönteminin devasa tamsayılar üzerindeki performans darboğazlarını aşmak için geliştirilmiş

hızlandırılmış bir varyanttır.

Klasik Öklid algoritması her adımda maliyetli modül (kalan) işlemleri yaparken; Lehmer, sayıların yalnızca en anlamlı basamaklarını kullanarak birden fazla Öklid adımını tek bir hamlede simüle eder.

Günümüzde profesyonel matematik kütüphaneleri, yüzlerce basamaklı sayılar söz konusu olduğunda GCD hesaplaması için Lehmer mimarisini bir endüstri standardı olarak kullanır.

Algoritma Prensibi: Matris Dönüşümü ve Tahmin

Algoritmanın ana stratejisi, büyük \(a\) ve \(b\) sayılarını küçük "üst basamak" kopyalarına indirgemektir.

Bu küçük kopyalar üzerinde yapılan ardışık Öklid adımları, bir 2x2 Dönüşüm Matrisi içinde biriktirilir.

Lineer Hızlandırma: Küçük sayılar üzerindeki bölümler, büyük sayılarla aynı olduğu sürece tahmin devam eder.

Tahmin güvenilirliğini yitirdiğinde, biriktirilen matris orijinal büyük sayılara uygulanarak tek bir çarpma işlemiyle sayılar binlerce kat küçültülür.

Adım Adım Yürütme: İşlem, sayıların bit uzunluğunun kontrolü ile başlar; eğer sayılar standart kayıtçı boyutuna sığacak kadar küçükse

Klasik Öklid devreye girer.

Tahmin Safhası: Sayıların en üst 32 veya 64 biti alınır ve bu limitli hassasiyet üzerinde hızlı Öklid adımları koşturulur.

Global Güncelleme: Elde edilen matris, orijinal büyük sayılara uygulanır.

Bu, büyük sayılar üzerinde onlarca kez bölme yapmak yerine tek bir vektör-matris çarpımı yapmak demektir.

Performans ve Hız: Lehmer'in algoritması, büyük sayılar üzerinde klasik Öklid'e göre 2 ile 10 kat arasında hız artışı sağlar.

İşlem Maliyeti: Algoritmanın "Overhead" fazladır; bu yüzden küçük sayılarda klasik yönteme göre daha yavaş kalabilir.

Devasa verileri her saniye bölmek yerine, üst limit tahmini ile CPU çevrimlerinden tasarruf ederiz.

function gcdEuclidean(a, b) {
    while (b !== 0n) {
        [a, b] = [b, a % b];
    }
    return a;
}

function lehmersGcd(a, b) {
    a = a < 0n ? -a : a;
    b = b < 0n ? -b : b;
    if (a < b) [a, b] = [b, a];

    while (b !== 0n) {
        if (b.toString(2).length < 64) {
            return gcdEuclidean(a, b);
        }

        const n = 64;
        let aTop = a >> (BigInt(a.toString(2).length) - BigInt(n));
        let bTop = b >> (BigInt(b.toString(2).length) - BigInt(n));

        let A = 1n, B = 0n, C = 0n, D = 1n;

        while (true) {
            let q;
            if (bTop + C === 0n || bTop + D === 0n) break;
            
            const q1 = (aTop + A) / (bTop + C);
            const q2 = (aTop + B) / (bTop + D);

            if (q1 !== q2) break;

            q = q1;
            [A, B, C, D] = [C, D, A - q * C, B - q * D];
            [aTop, bTop] = [bTop, aTop - q * bTop];
        }

        if (B === 0n) {
            [a, b] = [b, a % b];
        } else {
            const newA = A * a + B * b;
            const newB = C * a + D * b;
            a = newA < 0n ? -newA : newA;
            b = newB < 0n ? -newB : newB;
        }
    }
    return a;
}

const a = 1234567890123456789012345678901234567890n;
const b = 9876543210987654321098765432109876543210n;
console.log(`Lehmer's GCD: ${lehmersGcd(a, b)}`);

Tanım ve Sayısal Patlama Sorunu

Modular Exponentiation, çok büyük tam sayılarla çalışırken \(b^e \pmod{m}\) formülünü hesaplamak için kullanılan, yüksek verimli bir algoritmadır.

Normal şartlarda \(2^{1000}\) gibi bir üs alma işlemi, evrendeki atom sayısından daha büyük bir değer üretir ve belleği anında felç eder.

Bu algoritma, üs alırken sayıyı büyütmek yerine, her çarpım adımında Modüler İndirgeme uygulayarak sonuçları daima yönetilebilir bir eşikte tutar.

RSA ve Diffie-Hellman gibi kriptografik sistemlerin kalbi bu işleme dayanır; çünkü güvenliğin anahtarı, bu işlemi hızlı yapabilmek ama tersini çözememektir.

Algoritma Prensibi: Binary Exponentiation (Kareleme)

Algoritmanın ana stratejisi, üssü (e) ikilik tabana ayırarak çarpmayı optimize etmektir.

Bir sayıyı binlerce kez kendisiyle çarpmak yerine, her adımda kare alma yoluna gidilir.

Logaritmik İndirgeme: Modüler aritmetiğin dağılma özelliği sayesinde, \((x \cdot y) \pmod{m} = ((x \pmod{m}) \cdot (y \pmod{m})) \pmod{m}\) kuralı işletilir.

Bu, işlem karmaşıklığını \(O(e)\) gibi doğrusal bir seviyeden, şaşırtıcı bir hız olan O(log e) seviyesine düşürür.

Adım Adım Yürütme: İşlem, tabanı (b) modül \(m\) içine çekerek ve sonucu 1'e eşitleyerek başlar.

Bit Analizi: Üssün ( e ) her bir biti sağdan sola taranır.

Eğer mevcut bit 1 ise, o ana kadar elde edilen "kare kuvvet", sonuca çarpım olarak eklenir.

Ardışık Kareleme: Her adımda taban kendi karesiyle güncellenir ( \(b = b^2 \bmod m\) ).

Bu, \(b^1, b^2, b^4, b^8...\) serisini hazırlar.

Üs değerindeki tüm bitler işlendiğinde, elde edilen r değeri, devasa bir sayının modüler karşılığını kesin olarak verir.

Performans ve Hız: Modüler üs alma, üs değeri ne kadar devasa olursa olsun logaritmik hız bariyerini aşmaz.

Bellek Güvenliği: İşlemler sırasında hiçbir ara değer \(m^2\) değerini aşmadığı için, bellek taşmaları (stack overflow) tamamen engellenir.

Mühendislik başarısı; matematiksel bir imkansızlığı (sayısal patlama), bit düzeyinde manipülasyon ve modüler sınırlama ile bir saniyeden kısa sürede çözebilmektir.

function modExp(base, exponent, modulus) {
    if (modulus === 1) return 0;
    
    let result = 1;
    base = base % modulus;
    
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    
    return result;
}

function modExpRecursive(base, exponent, modulus) {
    if (modulus === 1) return 0;
    if (exponent === 0) return 1;
    if (exponent === 1) return base % modulus;
    
    if (exponent % 2 === 0) {
        let half = modExpRecursive(base, exponent / 2, modulus);
        return (half * half) % modulus;
    } else {
        return (base * modExpRecursive(base, exponent - 1, modulus)) % modulus;
    }
}

function modExpMontgomeryLadder(base, exponent, modulus) {
    if (modulus === 1) return 0;
    
    let r0 = 1;
    let r1 = base % modulus;
    
    let exp = exponent;
    let bitLength = Math.floor(Math.log2(exp)) + 1;
    
    for (let i = bitLength - 1; i >= 0; i--) {
        if ((exp >> i) & 1) {
            r0 = (r0 * r1) % modulus;
            r1 = (r1 * r1) % modulus;
        } else {
            r1 = (r0 * r1) % modulus;
            r0 = (r0 * r0) % modulus;
        }
    }
    
    return r0;
}

Tanım ve Modüler Sistemlerin Birleşimi

Chinese Remainder Theorem (CRT), birden fazla doğrusal kongrüans sistemine tek ve benzersiz bir çözüm bulmaya yarayan güçlü bir matematiksel algoritmadır.

Temel mantığı; bir sayının farklı bölenlere göre verdiği kalanlar biliniyorsa, o sayının orijinal halini belirli bir aralıkta keşfedebilmektir.

M.S. 3. yüzyılda Sun Tzu tarafından temelleri atılan bu teorem, modern dünyada Büyük Veri Aritmetiği'ni optimize etmek için kullanılır.

Algoritmanın geçerli olması için tek bir mutlak kural vardır: Tüm modüller ( \(m_1, m_2, \dots\) ) birbirleriyle Aralarında Asal olmalıdır.

Algoritma Prensibi: Katkı Bazlı İnşa

CRT, problemi çözmek için "Katkıların Toplamı" stratejisini izler.

Her bir modüler denklemin çözüme yapacağı etki ayrı ayrı hesaplanır ve ardından bu etkiler devasa bir Birleşik Modül altında sentezlenir.

Aritmetik Bölünme: Büyük sayılar üzerindeki ağır işlemleri, CRT sayesinde daha küçük modüller üzerinde paralel olarak yapabiliriz.

Bu, işlemci üzerindeki yükü hafifleterek Hesaplama Hızını dramatik şekilde artırır.

Adım Adım Yürütme: Süreç, tüm modüllerin çarpımı olan Global Modül değerinin hesaplanmasıyla başlar.

Yardımcı Modül (M_i): Her bir \(m_i\) için, M'nin o modüle bölünmesiyle elde edilen (\(M/m_i\)) değeri bulunur.

Bu, ilgili modülün çözüm üzerindeki ağırlığını temsil eder.

Modüler Ters (y_i): Genişletilmiş Öklid Algoritması kullanılarak her bir yardımcı modülün kendi yerel modülüne göre tersi hesaplanır.

Nihai çözüm, tüm bu değerlerin x = Σ(a_i * M_i * y_i) mod M formülüyle toplanmasıyla elde edilir.

Performans ve Hız: CRT, karmaşık tamsayı problemlerini parçalara ayırarak O(k log² M) gibi oldukça verimli bir sürede çözer.

Kriptografik Avantaj: RSA imzalamada CRT kullanımı, imza atma hızını ortalama 4 kat artırır; bu da sunucu tarafındaki yükü büyük oranda azaltır.

Devasa bir kilidi tek bir anahtarla açmak yerine, küçük şifre parçalarını bir araya getirerek bütüne ulaşırız.

Mühendislik başarısı; tek bir noktadaki işlem yükünü, paralelleştirilebilir modüler hücreler dağıtabilme becerisidir.

function extendedGcd(a, b) {
    if (a === 0) return [b, 0, 1];
    const [gcd, x1, y1] = extendedGcd(b % a, a);
    const x = y1 - Math.floor(b / a) * x1;
    const y = x1;
    return [gcd, x, y];
}

function modInverse(a, m) {
    const [gcd, x] = extendedGcd(a, m);
    if (gcd !== 1) throw new Error("Modular inverse does not exist");
    return ((x % m) + m) % m;
}

function chineseRemainderTheorem(remainders, moduli) {
    const k = remainders.length;
    if (k !== moduli.length) throw new Error("Arrays must have same length");
    
    let result = 0;
    let product = 1;
    
    for (let i = 0; i < k; i++) {
        product *= moduli[i];
    }
    
    for (let i = 0; i < k; i++) {
        const p = product / moduli[i];
        const inv = modInverse(p, moduli[i]);
        result = (result + remainders[i] * p * inv) % product;
    }
    
    return result;
}

function chineseRemainderTheoremWithValidation(remainders, moduli) {
    const k = remainders.length;
    if (k !== moduli.length) throw new Error("Arrays must have same length");
    
    for (let i = 0; i < k; i++) {
        for (let j = i + 1; j < k; j++) {
            const [gcd] = extendedGcd(moduli[i], moduli[j]);
            if (gcd !== 1) {
                throw new Error("Moduli must be pairwise coprime");
            }
        }
    }
    
    return chineseRemainderTheorem(remainders, moduli);
}

function chineseRemainderTheoremNonCoprime(remainders, moduli) {
    const k = remainders.length;
    if (k !== moduli.length) throw new Error("Arrays must have same length");
    
    let a1 = remainders[0];
    let m1 = moduli[0];
    
    for (let i = 1; i < k; i++) {
        const a2 = remainders[i];
        const m2 = moduli[i];
        
        const [gcd, x, y] = extendedGcd(m1, m2);
        
        if ((a1 - a2) % gcd !== 0) {
            throw new Error("No solution exists");
        }
        
        const lcm = (m1 * m2) / gcd;
        const x0 = ((a1 + (a2 - a1) / gcd * x * m1) % lcm + lcm) % lcm;
        
        a1 = x0;
        m1 = lcm;
    }
    
    return a1;
}

function solveLinearCongruence(a, b, m) {
    const [gcd, x] = extendedGcd(a, m);
    if (b % gcd !== 0) return null;
    
    const x0 = (x * (b / gcd)) % m;
    const solutions = [];
    
    for (let i = 0; i < gcd; i++) {
        solutions.push((x0 + i * (m / gcd)) % m);
    }
    
    return solutions;
}

function crtForRSA(ciphertext, p, q, d) {
    const n = p * q;
    const dp = d % (p - 1);
    const dq = d % (q - 1);
    
    const mp = modExp(ciphertext, dp, p);
    const mq = modExp(ciphertext, dq, q);
    
    const remainders = [mp, mq];
    const moduli = [p, q];
    
    return chineseRemainderTheorem(remainders, moduli);
}

function modExp(base, exponent, modulus) {
    if (modulus === 1) return 0;
    
    let result = 1;
    base = base % modulus;
    
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    
    return result;
}

Tanım ve Varlık Koşulu

Modular Multiplicative Inverse, verilen bir \(a\) tam sayısının \(m\) modülüne göre "çarpımsal karşılığını" bulma işlemidir.

Klasik matematikte bir sayıyı \(a\)'ya bölmek, o sayıyı \(1/a\) ile çarpmaktır.

Modüler aritmetikte ise payda kavramı yoktur; bunun yerine \(a \cdot x \equiv 1 \pmod{m}\) denkliğini sağlayan \(x\) değerini buluruz.

Kritik Kısıt: Bir modüler tersin var olabilmesi için \(a\) ve \(m\) sayılarının Aralarında Asal ( \(GCD(a, m) = 1\) ) olması mutlak zorunluluktur.

Eğer bu şart sağlanmazsa, modüler dünyada o sayıya "bölme" işlemi yapılamaz.

Algoritma Prensibi: Genişletilmiş Öklid ve Bézout

Modüler tersi hesaplamanın en güçlü yolu Genişletilmiş Öklid Algoritması'dır.

Bu yöntem, Öklid'in kalan bulma mekanizmasını kullanarak \(a \cdot x + m \cdot y = 1\) denklemini çözer.

Katsayı Takibi: Algoritma geriye doğru iz sürerek öyle bir \(x\) katsayısı bulur ki; bu değer \(a\) ile çarpıldığında, \(m\)'nin tam katlarından tam olarak

1 fazla veya 1 eksik bir sonuç üretir ve bu \(x\) katsayısı, bizim aradığımız modüler terstir.

Adım Adım Yürütme: Süreç, \(a\) ve \(m\) arasındaki GCD kontrolü ile başlar. Sonuç 1 değilse işlem "Ters Mevcut Değil" hatasıyla sonlanır.

İleri Safha: Standart Öklid adımları uygulanırken, her adımda katsayılar (\(x_i, y_i\)) güncellenir.

Normalizasyon: Elde edilen \(x\) katsayısı negatif çıkarsa, tanım aralığına (\(0\) ile \(m-1\)) çekmek için üzerine \(m\) eklenir.

Sonuç olarak elde edilen pozitif \(x\), modüler denklemdeki Gizli Anahtar görevini görür.

Performans ve Hız: Algoritma, Öklid'in mirası olan O(log m) zaman karmaşıklığıyla çalışır.

Bu, kriptografik anahtar üretiminde saniyenin binde birinde sonuç alınmasını sağlar.

Fermat Alternatifi: Eğer modül \(m\) bir asal sayı ise, alternatif olarak Fermat'nın Küçük Teoremi (\(a^{m-2} \bmod m\)) de kullanılabilir; ancak Genişletilmiş Öklid genel amaçlı olmasıyla daha esnektir.

Bir veriyi modüler dünyada \(a\) ile çarparak karıştırıyorsak, onu eski haline getirecek tek yol Modüler Ters ile çarpmaktır.

function modInverse(a, m) {
    let [old_r, r] = [a, m];
    let [old_s, s] = [1, 0];
    let [old_t, t] = [0, 1];
    
    while (r !== 0) {
        let quotient = Math.floor(old_r / r);
        [old_r, r] = [r, old_r - quotient * r];
        [old_s, s] = [s, old_s - quotient * s];
        [old_t, t] = [t, old_t - quotient * t];
    }
    
    if (old_r !== 1) {
        return null;
    }
    
    return ((old_s % m) + m) % m;
}

function modInverseFermat(a, m) {
    if (m <= 1) return null;
    
    let result = 1;
    let base = a;
    let exp = m - 2;
    
    while (exp > 0) {
        if (exp % 2 === 1) {
            result = (result * base) % m;
        }
        base = (base * base) % m;
        exp = Math.floor(exp / 2);
    }
    
    return result;
}

console.log(modInverse(3, 11));
console.log(modInverseFermat(3, 11));

Tanım ve Varlık Koşulu

Linear Congruence Solver, \(ax \equiv b \pmod{m}\) formundaki denklemlerde \(x\) bilinmeyenini bulmak için tasarlanmış bir algoritmadır.

Bu ifade, "\(a\) ile \(x\)'in çarpımının \(m\) ile bölümünden kalan \(b\)'dir" mantığını temsil eder.

Her modüler denklem çözülebilir değildir.

Bir çözümün var olabilmesi için matematiksel Varlık Koşulu şudur: \(a\) ve \(m\) sayılarının en büyük ortak böleni ( \(g = GCD(a, m)\)), \(b\ ) değerini tam olarak bölmelidir.

Eğer \(g\), \(b\)'yi bölmüyorsa, modüler uzayda bu denklemi sağlayan hiçbir \(x\) tam sayısı yoktur.

Eğer bölüyorsa, denklem tam olarak g adet benzersiz çözüme sahiptir.

Algoritma Prensibi: Sadeleştirme ve Ters Eleman

Algoritma, karmaşık bir sistemi en yalın haline getirmek için "Normalizasyon" tekniğini kullanır.

Tüm terimler \(g\) değerine bölünerek \(a'x \equiv b' \pmod{m'}\) formuna indirgenir.

Modüler Manipülasyon: Bu sadeleştirme sayesinde \(a'\) ve \(m'\) artık Aralarında Asal hale gelir.

Bu noktadan sonra çözüm, \(a'\) sayısının modüler tersini bulup \(b'\) ile çarpmaktan ibaret bir doğrusal işleme dönüşür.

Adım Adım Yürütme: Süreç, \(g = GCD(a, m)\) hesaplaması ve \(b \bmod g == 0\) kontrolü ile başlar.

Sadeleştirme Safhası: Tüm katsayılar \(g\) ile bölünerek denklemin temel formu oluşturulur.

Ters Eleman Entegrasyonu: Genişletilmiş Öklid Algoritması ile \(a'\)'nün tersi (\(inv\)) hesaplanır ve temel çözüm \(x_0 = (b' \cdot inv) \bmod m'\) bulunur.

Diğer tüm çözümler, \(x_0\) değerine \(m\) modülünün katları eklenerek (g kez) inşa edilir.

Performans ve Hız: Algoritmanın ana maliyeti \(GCD\) ve modüler ters işlemlerine bağlıdır, bu da O(log m) gibi son derece yüksek bir performans sunar.

Çözüm Kümesi: \(g > 1\) olduğu durumlarda birden fazla geçerli yanıtın çıkması, algoritmanın deterministik ama çoklu sonuçlu doğasını gösterir.

Kriptografik sistemlerdeki anahtar çakışmalarını yönetmek ve periyodik sistemlerin senkronizasyonunu sağlamak için bu matematiksel terazi kullanılır.

function extendedGCD(a, b) {
  if (b === 0) return [a, 1, 0];
  const [g, x1, y1] = extendedGCD(b, a % b);
  return [g, y1, x1 - Math.floor(a / b) * y1];
}

function modInverse(a, m) {
  const [g, x] = extendedGCD(a, m);
  if (g !== 1) return null;
  return (x % m + m) % m;
}

function solveLinearCongruence(a, b, m) {
  const [g] = extendedGCD(a, m);
  if (b % g !== 0) return null;
  const a_ = a / g, b_ = b / g, m_ = m / g;
  const inv = modInverse(a_, m_);
  if (inv === null) return null;
  const x0 = (b_ * inv) % m_;
  let solutions = [];
  for (let k = 0; k < g; k++) {
    solutions.push((x0 + k * m_) % m);
  }
  return solutions;
}

console.log(solveLinearCongruence(3, 2, 7));
console.log(solveLinearCongruence(4, 2, 6));