Denklikler ve Modüler Aritmetik
Modüler aritmetik, tam sayıları sabit bir modül ile bölünebilirlik açısından inceler, tam sayıları sonlu bir Z/nZ halkasına dönüştürür ve sayı teorisine en esnek hesaplama aracını sağlar.
Tanım
İki tam sayı, farkları n ile bölünebiliyorsa n modülüne göre denktir. Modüler aritmetik, ortaya çıkan kalan sınıflarının aritmetiğidir ve bu sınıflar değişmeli Z/nZ halkasını oluşturur.
Kapsam
Bu konu, denklik bağıntısını ve kalan sınıflarını, Z/nZ'deki aritmetiği, doğrusal ve polinom denkliklerini, Çin kalan teoremini, Fermat'nın küçük teoremini ve Euler teoremini, birim grubunun yapısını, ilkel kökleri ve elemanların mertebesini kapsar. Temel ve hesaplamalı sayı teorisinin çoğu bu dilde ifade edilmektedir.
Temel sorular
- ax ≡ b (mod n) şeklindeki doğrusal bir denkliğin ne zaman çözümleri vardır ve kaç tanedir?
- Çin kalan teoremi, Z/nZ'yi asal kuvvet modülleri üzerinden bir çarpıma nasıl ayrıştırır?
- Fermat'nın küçük teoremi ve Euler teoremi neden geçerlidir ve birimlerin mertebesi hakkında ne söylerler?
- Hangi modüller için bir ilkel kök mevcuttur, bu da birim grubunu döngüsel yapar?
Temel kuramlar
- Çin kalan teoremi
- Modüller ikişerli aralarında asal ise, eşzamanlı denklikler sisteminin modül çarpımına göre tek bir çözümü vardır; eşdeğer olarak Z/nZ, asal kuvvet çarpanları üzerindeki Z'nin çarpımına izomorfiktir.
- Fermat'nın küçük teoremi ve Euler teoremi
- n ile aralarında asal bir a için, a'nın n'nin totientine yükseltilmiş hali n modülüne göre bire denktir; asal durum (Fermat) asal sayı testlerinin temelini oluştururken, genel durum RSA'nın temelini oluşturmaktadır.
- İlkel kökler ve grup yapısı
- n modülüne göre birimlerin çarpımsal grubu tam olarak n bir, iki, dört, tek bir asal kuvvet veya iki katı olduğunda döngüseldir; bir üreteç ilkel bir köktür ve ayrık bir logaritma sağlar.
Klinik önem
Modüler aritmetik, kriptografinin (RSA, Diffie-Hellman, eliptik eğri şemaları), sağlama toplamlarının ve hata tespitinin (ISBN, hash fonksiyonları) ve sözde rastgele sayı üretiminin hesaplama motorudur ve bu da onu sayı teorisinin en yaygın kullanılan kısmı haline getirmektedir.
Tarihçe
Özel durumları eski Çin ve Hint matematiğinde (ilkinin adını taşıyan kalan problemi) görülse de, denkliklerin sistematik teorisi Gauss tarafından Disquisitiones Arithmeticae (1801) adlı eserinde tanıtılmıştır; burada notasyonu oluşturmuş ve merkezi yapısal sonuçları kanıtlamıştır.
Öne çıkan isimler
- Carl Friedrich Gauss
- Pierre de Fermat
- Leonhard Euler
İlgili konular
Temel eserler
- irelandRosen1990
Sıkça sorulan sorular
- a ≡ b (mod n) gösterimi ne anlama gelir?
- Bu, n'nin a eksi b farkını böldüğü anlamına gelir; eşdeğer olarak a ve b, n'ye bölündüğünde aynı kalanı verir.
- RSA neden Euler teoremine dayanır?
- RSA şifrelemesi ve şifre çözme, bileşimleri orijinal mesajı döndüren modüler üs almalardır, çünkü Euler teoremi ilgili üssün anahtar modülüne göre birim eleman olarak hareket etmesini garanti eder.