Çin Kalan Teoremi: Bin Yıllık Bulmacanın Modern Şifreleme Rolü

Sun Tzu'nun bulmacası

M.S. 3. yüzyılda Çinli matematikçi (askeri stratejist Sun Tzu ile karıştırılmamalı) Sun Zi "Sun Zi Suanjing" (Sun Zi'nin Hesap El Kitabı) adlı eserinde şöyle bir bulmaca koydu:

"Belirsiz sayıda nesne 3'erli gruplara ayrılınca 2 kalır, 5'erli gruplara ayrılınca 3 kalır, 7'şerli gruplara ayrılınca 2 kalır. Toplam kaçtır?"

Yani:

• $x \equiv 2 \pmod{3}$
• $x \equiv 3 \pmod{5}$
• $x \equiv 2 \pmod{7}$

Sun Zi'nin cevabı: 23. Doğrulayalım: $23 = 7 \cdot 3 + 2$, $23 = 4 \cdot 5 + 3$, $23 = 3 \cdot 7 + 2$. ✓ Üç koşul da sağlanır.

Bu bulmaca Çin Kalan Teoremi'nin (Chinese Remainder Theorem — CRT) ilk yazılı kaydıdır. Teorem genelleştirilmiş haliyle bin yıl sonra Hint matematikçileri (Brahmagupta, Bhaskara) tarafından da bağımsız olarak keşfedildi; Avrupa'ya Fibonacci eseriyle geçti.

Teorem (modern dilde)

Çin Kalan Teoremi: Eğer $m_1, m_2, \dots, m_k$ ikişer ikişer aralarında asal (en büyük ortak böleni 1) ise, herhangi $a_1, a_2, \dots, a_k$ kalanları için sistem:

$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \dots, \quad x \equiv a_k \pmod{m_k}$

$M = m_1 \cdot m_2 \cdots m_k$ olmak üzere $0$ ile $M-1$ arasında bir ve yalnız bir $x$ değerine sahiptir.

Yukarıdaki örnekte $M = 3 \cdot 5 \cdot 7 = 105$; 0–104 arasında tek çözüm 23. Diğer çözümler $23, 128, 233, \dots$ — 105 periyotlu.

Tek bir formül

Çözüm doğrudan formülle elde edilir. Her $i$ için:

• $M_i = M / m_i$ (diğer modüllerin çarpımı)
• $y_i = M_i^{-1} \pmod{m_i}$ (ters)

Sonra:
$x = \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \pmod M$

Sun Zi örneği için: $M_1 = 35,\ M_2 = 21,\ M_3 = 15$. Tersler $y_1 = 2,\ y_2 = 1,\ y_3 = 1$. Hesap: $2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233$. $233 \bmod 105 = 23$. ✓

"Modülerden modülere parçalama" gücü

Teoremin asıl güzelliği bir denkleme indirgenen bilgilerin bilgi kaybetmeden parçalanabileceğini göstermesidir. Büyük bir modülde işlem yapmak yerine küçük modüllerde paralel işlem yapıp sonuçları birleştirebilirsiniz. Buna bölümleme stratejisi denir.

Birkaç kritik uygulama:

1) RSA şifrelemenin hızlandırılması (CRT-RSA)

RSA özel anahtarıyla şifre çözmek $c^d \pmod n$ hesabı gerektirir; burada $n = p \cdot q$ iki büyük asalın çarpımıdır. Bu işlem doğrudan yapıldığında pahalıdır. Ama CRT ile:

• $c^d \bmod p$ ve $c^d \bmod q$'yu ayrı ayrı hesaplayın (her biri yarı bit uzunluğunda).
• Sonra CRT ile birleştirin.

Bu yöntem RSA şifre çözümünü yaklaşık 4 kat hızlandırır. Modern OpenSSL, hardware-tokenlar, mobil cihazlarda RSA hep CRT ile yapılır.

2) Sayısal hesaplama: büyük sayıları işlemek

Bilgisayar pahalı bir polinom hesabı yapacaksa, hesabı küçük asal modüllerde paralel yapar, sonra CRT ile birleştirir. Symbolic computation (Mathematica, Maple) ve kriptografik kütüphanelerin sabit aracıdır.

3) Hash fonksiyonları ve hata düzeltme

CRT, Reed-Solomon hata düzeltme kodlarının temel matematik aracıdır. CD'lerin çiziklerinin önemsiz görünmesi, DVB-T sinyalinin gürültüde okunabilmesi bu aileye dayanır.

4) Eşzamanlı zamanlama problemleri

"Otobüs A her 12 dakikada, B her 15 dakikada, C her 20 dakikada gelir. İlk üçü birlikte ne zaman gelir?" — basit ama CRT iskeletli bir soru.

Tarihsel öncülük

Çin Kalan Teoremi, matematiğin Çin'den dünyaya çıkan en zarif sonuçlarından biridir. Sonraki yüzyıllarda Qin Jiushao (1247) "Da Yan Shu" (Büyük Genişleme Tekniği) ile sistematik bir algoritma verdi. Hindistan ve İslam dünyasında bağımsız tekrar keşfedildi. Avrupa'da Bachet (1612) ve Euler (1734) modern formuna getirdi.

Modern soyut cebir CRT'yi halka teorisinin (ring theory) temel bir izomorfizm teoremine genelleştirir:

$\mathbb{Z}/M\mathbb{Z} \cong \mathbb{Z}/m_1\mathbb{Z} \times \dots \times \mathbb{Z}/m_k\mathbb{Z}$

Yani "büyük halka, küçük halkaların kartezyen çarpımına eştir." Bu bakış 19. ve 20. yüzyıl cebrinin önemli yapı taşlarından biridir.

Bin yıllık formül, milyar saniyelik etki

Sun Zi M.S. 250 civarında bir el kitabına bulmaca yazdı. Bugün her HTTPS bağlantısı kurulurken, her banka şifresi doğrulanırken o kitaptaki fikrin matematiksel torunu çalışıyor. Bilim tarihinde "uygulamasız saf matematik" diye bir şey yoktur — sadece henüz keşfedilmemiş uygulamalar vardır.