Modüler aritmetik nedir

Modüler aritmetik, sayıları belirli bir bölen üzerinden denklik sınıflarına göre değerlendiren bir sayı sistemidir. Gündelik hayatta saat hesaplarken bu sistemi farkında olmadan kullanırız: saat 22'de 5 saat ilerlediğimizde 22 + 5 = 27 buluruz, ama saat 27 diye bir zaman yoktur. 27 mod 24 = 3 işlemi sabah 3'ü verir. Saat kadranı 24 üzerinden döner; bir tam tur sonrasında başa dönersiniz.

Bu örüntü "modüler aritmetik" adını alır. Bölen n, modül olarak adlandırılır. a sayısını n'ye böldüğünüzde kalan r ise a'nın n modülünce değeri r'dir.

Denklik gösterimi

İki sayının aynı kalanı verip vermediğini ifade etmek için denklik gösterimi kullanılır:

a ≡ b (mod n)

Bu, a ve b'nin n'ye bölündüğünde aynı kalanı verdiği anlamına gelir. Örneğin 17 ≡ 5 (mod 12), çünkü ikisi de 12'ye bölündüğünde kalan 5'tir. Benzer biçimde 100 ≡ 1 (mod 99) yazılabilir.

Modüler aritmetikte kalanı hesaplamak için araç şu bölümü ve kalanı görünür kılar: a = n × q + r biçiminde, burada q bölüm ve r kalandır.

Negatif sayıların modu

Matematiksel mod tanımı gereği kalan her zaman 0 ile n−1 arasında bir değer alır. −7 mod 5 işlemini ele alalım. −7 = 5 × (−2) + 3 olduğu için sonuç 3'tür. Araç da bu matematiksel tanımı kullanır.

Programlama dillerinde durum farklı olabilir. C ve Java gibi dillerde % işleci "kalan" verir, "mod" değil. Bu dillerde −7 % 5 sonucu −2'dir, çünkü bölüm sıfıra doğru yuvarlanır: −7 / 5 = −1,4, bölüm −1, kalan −7 − 5×(−1) = −2. Python'da ise % matematiksel moda uyar ve −7 % 5 = 3 döner. Farklı dillerde kod yazarken bu ayrımı göz önünde bulundurmak gerekir.

Toplama ve çarpma özellikleri

Modüler aritmetikte toplama ve çarpma işlemleri aşağıdaki kurallara uyar:

(a + b) mod n = ((a mod n) + (b mod n)) mod n

(a × b) mod n = ((a mod n) × (b mod n)) mod n

Bu özellikler çok büyük sayılarla çalışırken bellek ve işlem tasarrufu sağlar. Bir aşamada kalan alınarak sonuç küçük tutulur; işleme devam edilir. Araç da büyük tam sayılar için bu yaklaşımı kullanır.

Modüler üs alma: hızlı yöntem

a^b mod n hesabını kaba kuvvetle yapmak büyük üsler için hantal olur. Hızlı üs alma yöntemi üssü ikili sisteme çevirip gerekli kare ve çarpma adımlarını minimuma indirir. Bu yönteme "kare al ve çarp" da denir.

3^13 mod 7 hesabını adım adım görelim. Önce 13'ü ikili sisteme çeviririz: 13 = 8 + 4 + 1, dolayısıyla 1101₂. İkili gösterimde bit değeri 1 olan haneler üsse karşılık gelir. 13 = 2³ + 2² + 2⁰ olduğundan 3^13 = 3^8 × 3^4 × 3^1 yazılabilir.

İkili dönüşümler için binary çevirici aracı bu adımı otomatikleştirir.

Ardışık kareleme işlemleri:

Dahil olan kuvvetlerin mod 7 değerlerini çarparız:

3^13 mod 7 = (3 × 4 × 2) mod 7 = 24 mod 7 = 3

Doğrulama: 24 = 3 × 7 + 3, kalan 3. Araçtaki üslü sayı işlemleri için üslü sayı hesaplama aracına da bakabilirsiniz.

Modüler ters

a × x ≡ 1 (mod n) denklemini sağlayan x değerine a'nın n modülünce tersi denir ve a⁻¹ mod n gösterimiyle yazılır. Bu ters, ancak EBOB(a, n) = 1 koşulu sağlandığında vardır; yani a ve n aralarında asal olmalıdır. EBOB hesabı için EBOB-EKOK hesaplama aracını kullanabilirsiniz.

Genişletilmiş Öklid algoritması bu tersi verimli biçimde bulur. Algoritma a ve n üzerinde art arda bölme yapar, sonra geri adım atarak çözümü inşa eder.

3⁻¹ mod 11 hesabını ele alalım. Genişletilmiş Öklid adımları:

• 11 = 3 × 3 + 2
• 3 = 2 × 1 + 1
• 2 = 1 × 2 + 0

Geri adımla: 1 = 3 − 2 × 1 = 3 − (11 − 3 × 3) = 4 × 3 − 11. Sonuç: 3 × 4 ≡ 1 (mod 11), dolayısıyla 3⁻¹ mod 11 = 4'tür. Kontrol: 3 × 4 = 12 = 11 + 1 ≡ 1 (mod 11).

Daha büyük bir örnek: RSA şifrelemede sıklıkla rastlanan bir hesaplama türüdür. e = 17 ve λ(n) = 3.120 ise şifre çözme üssü d şöyle bulunur:

17⁻¹ mod 3120 = 2753

Kontrol: 17 × 2.753 = 46.801 = 15 × 3.120 + 1, kalan 1. Araç bu hesabı genişletilmiş Öklid algoritmasıyla adım tablosuyla gösterir. EBOB(17, 3120) = 1 olduğu için ters mevcuttur.

Kullanım alanları

TC kimlik numarası doğrulaması

TC kimlik numarasının 10. ve 11. haneleri bir kontrol mekanizması içerir. İlk dokuz haneyi d1'den d9'a kadar etiketlersek kurallar şöyledir:

10. hane = ((d1+d3+d5+d7+d9) × 7 − (d2+d4+d6+d8)) mod 10

11. hane = (d1+d2+d3+d4+d5+d6+d7+d8+d9+d10) mod 10

Tek sıradaki hanelerin ağırlığı 7 kat olduğundan çift sıradaki hanelere oranla daha baskın etkiye sahiptir. Bu yapı tek basamak hatalarının büyük bölümünü yakalar.

IBAN kontrolü

IBAN doğrulamasında kontrol rakamları mod 97 üzerinden hesaplanır. İlk dört karakter sona taşınır, harfler sayıya dönüştürülür ve elde edilen büyük tam sayı 97'ye bölünür; kalan 1 ise IBAN geçerlidir. Araç BigInt desteğiyle bu büyüklükteki sayıları sorunsuz işler.

RSA şifreleme

RSA, iki büyük asal sayının çarpımına dayanan bir açık anahtarlı şifreleme yöntemidir. Şifreleme üssü e ile modülün λ değeri aralarında asal seçilir; şifre çözme üssü d ise e⁻¹ mod λ(n) ile bulunur. Asal sayılara odaklanmak isteyenler için asal sayı hesaplama aracı ve büyük sayıların çarpanlarını bulmak için asal çarpan hesaplama aracı birlikte kullanılabilir.

Haftanın gününü bulma

Belirli bir tarihin haftanın hangi gününe denk geldiğini hesaplamak için kullanılan formüller mod 7 aritmetiğine dayanır. Zeller formülü bu yaklaşımın en bilinen örneğidir; ay, gün ve yıldan elde edilen bir ifade 7'ye bölünür ve kalan günü verir.

Diğer matematik araçlarıyla bağlantı

Modüler aritmetik pek çok konuyla kesişir. EBOB hesabı genişletilmiş Öklid için temel adımdır. Hızlı üs alma, ikili gösterim bilgisini doğrudan kullanır. Asal sayılar ise hem RSA hem de denklem çözülebilirliği açısından belirleyicidir. Tüm matematik hesaplama araçlarına buradan ulaşabilirsiniz.