Sayılar kuramı ve modüler aritmetik: adım adım çözümlü alıştırma soruları
Şekiller, ipuçları ve ayrıntılı çözümlerle ücretsiz Sayılar kuramı ve modüler aritmetik alıştırma soruları. Her seferinde yeni değerler, üç seviyede: ebob ve kalanlar, tersler ve denklikler, modüler kuvvetler ve RSA.
Ücretsiz alıştırma sorusuKolay
0 ≤ r < 11 olan r kalanını, yani 942 mod 11 değerini bulun.
Sayılar kuramı ve modüler aritmetik soruları nasıl çözülür
Önce her sayıyı n modunda indirgeyin; kalanlar 0 ile n − 1 arasındadır.
EBOB için Öklid algoritmasıyla art arda bölün; sıfırdan farklı son kalan EBOB’dur.
Bir ters için genişletilmiş algoritmayı çalıştırın ve a’nın katsayısını alın; negatifse n ekleyin.
a·x ≡ b denkliğini a⁻¹ ile çarparak çözün; iki denkliği x = r₁ + m₁k yazarak birleştirin.
Kuvvetler için üssü ikilik tabanda yazın ve art arda kare alın; RSA’da d = e⁻¹ mod φ(n) ve φ(n) = (p − 1)(q − 1)’dir.
Sık yapılan hatalar
Negatif bir sayı için negatif kalan vermek.
Öklid algoritmasını ilk kalanda durdurmak.
Tersi n ekleyerek pozitif yapmak yerine negatif bırakmak.
RSA üssü d’yi φ(n) yerine n modunda almak.
Fermat teoreminde üssü p − 1 yerine p modunda indirgemek.
Temel formüller
Kalanlı bölme
a = q·n + r, 0 ≤ r < n
Öklid
gcd(a, b) = gcd(b, a mod b)
En küçük ortak kat
lcm(a, b) = a·b/gcd(a, b)
Ters
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Doğrusal denklik
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Euler’in φ fonksiyonu
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Sayılar kuramı ve modüler aritmetik konusunu sıfırdan öğrenin
1Kalanlar ve denklikler
a’yı n’ye bölmek bir bölüm q ve bir kalan r verir: a = q·n + r, 0 ≤ r < n. Kalan a mod n olarak yazılır. Negatif bir sayıda q de negatiftir: −3 = −1·7 + 4, dolayısıyla −3 mod 7 = 4.
Aynı kalanı bırakıyorlarsa, yani n sayısı a − b’yi bölüyorsa, iki sayı n modunda denktir, a ≡ b (mod n).
Kalanlar her adımda indirgenebilir; bu da sayıları küçük tutar:
(a + b) mod n = ((a mod n) + (b mod n)) mod n, a·b için de aynısı
Örneğin 47·58 mod 9: 47 ≡ 2 ve 58 ≡ 4, dolayısıyla 47·58 ≡ 8 (mod 9).
Kendini sına −17 mod 5 kaçtır?
2
3
−2
−3
Cevap: 3. −17 = −4·5 + 3, dolayısıyla kalan 3’tür. 2 cevabı 17 mod 5’tir; bir kalan asla negatif olmaz.
2Öklid algoritması
En büyük ortak bölen ebob(a, b), ikisini de bölen en büyük sayıdır. Öklid algoritması ebob(a, b) = ebob(b, a mod b) eşitliğini kullanır:
Bölün: a = q·b + r.
(a, b) yerine (b, r) koyun.
Kalan 0 olana kadar tekrarlayın. Sıfırdan farklı son kalan EBOB’dur.
En küçük ortak kat bundan çıkar: ekok(a, b) = a·b / ebob(a, b).
Kendini sına ebob(84, 36) kaçtır?
12
252
4
6
Cevap: 12. 84 = 2·36 + 12 ve 36 = 3·12 + 0, dolayısıyla EBOB 12’dir. 252 en küçük ortak kattır, 84·36/12.
3Tersler ve genişletilmiş algoritma
a’nın n modundaki tersi, a·x ≡ 1 (mod n) olan x sayısıdır. Yalnızca ebob(a, n) = 1 olduğunda vardır.
Genişletilmiş Öklid algoritması Öklid’i (n, a) üzerinde çalıştırır ve her kalan için bir t katsayısı tutar; böylece her r kalanı r ≡ t·a (mod n) olur. n için t = 0, a için t = 1 ile başlayın; her yeni t, iki satır yukarıdaki t eksi q çarpı bir satır yukarıdaki t’dir. 1 kalanı göründüğünde onun t’si tersidir.
Ters ile a·x ≡ b (mod n) denkliği x ≡ a⁻¹·b ile çözülür. d = ebob(a, n) 1’den büyükse, d sayısı b’yi bölüyorsa d çözüm vardır, bölmüyorsa yoktur.
Modülleri aralarında asal olan iki denklik, x ≡ r₁ (mod m₁) ve x ≡ r₂ (mod m₂), m₁·m₂ modunda tam olarak bir çözüme sahiptir (Çin kalan teoremi). x = r₁ + m₁k yazın ve k için çözün.
Tekrarlı kare alma aᵏ mod n değerini hızlıca hesaplar: k’yi ikilik tabanda yazın, a, a², a⁴, a⁸, … değerlerini kare alıp indirgeyerek mod n’de bulun ve biti 1 olan kuvvetleri çarpın.
Fermat’nın küçük teoremi: a’yı bölmeyen bir p asalı için aᵖ⁻¹ ≡ 1 (mod p). Dolayısıyla üs p − 1 modunda indirgenebilir.
RSA, iki asal p ve q’dan bir anahtar kurar:
n = p·q ve φ(n) = (p − 1)(q − 1).
ebob(e, φ(n)) = 1 olacak şekilde e seçin; (n, e) genel anahtardır.
d = e⁻¹ mod φ(n) hesaplayın: özel anahtar.
Şifreleme c = mᵉ mod n; şifre çözme m = cᵈ mod n.
Euler’in φ(n) fonksiyonu, 1’den n’ye kadar n ile aralarında asal olan sayıları sayar: asal için φ(p) = p − 1, φ(pᵏ) = pᵏ − pᵏ⁻¹ ve φ aralarında asal çarpanlar için çarpımsaldır.
Kendini sına Bir RSA anahtarı p = 5, q = 11 ve e = 3 kullanıyor. d kaçtır?
13
27
37
3
Cevap: 27. φ(n) = 4·10 = 40 ve 3·27 = 81 = 2·40 + 1, dolayısıyla d = 27. 3’ün n = 55 modundaki tersi 37 olurdu, ama d, φ(n) modunda alınır.
5Sık yapılan hatalar
Negatif bir sayı için negatif kalan vermek: −17 mod 5, −2 değil 3’tür.
Öklid’i sıfırdan farklı son kalanda değil ilk kalanda durdurmak.
Genişletilmiş algoritmadan çıkan negatif bir katsayıya n eklemeyi unutmak.
RSA üssü d’yi φ(n) modunda değil n modunda hesaplamak.
Fermat teoreminde bir üssü p − 1 yerine p modunda indirgemek.
6Sınav soruları nasıl görünür
Kolay: ebob ve kalanlar. Bir ebob ya da ekok için Öklid algoritmasını çalıştırır, negatif sayıların kalanlarını bulur, toplamları ve çarpımları n modunda indirgersiniz.
Orta: tersler ve denklikler. Modüler tersleri genişletilmiş algoritmayla bulur, doğrusal denklikleri çözer, iki denkliği Çin kalan teoremiyle birleştirir ve Euler’in φ(n) değerini hesaplarsınız.
Zor: modüler kuvvetler ve RSA. Tekrarlı kare almayı ve Fermat teoremini kullanır, birden çok çözümlü denklikleri çözer, RSA özel üslerini, şifreli metinleri ve çözülmüş mesajları bulursunuz.
Büyük sayıları çarpmadan (914·953) mod 11 değerini bulun: önce indirgeyin.
n = 11
İstenen: (914·953) mod 11
İpuçlarını göster
(x·y) mod n = ((x mod n)·(y mod n)) mod n ve aynısı toplamlar için de geçerlidir.
914 mod 11 = 1, 953 mod 11 = 7.
Kalanların çarpımını 11 modunda indirgeyin.
Cevabı ve adım adım çözümü göster
Bölünebilme ve kalanlar: a mod n, 0 ≤ r < n ve a = q·n + r olan r kalanıdır; a negatif olduğunda da böyledir. Öklid algoritması a = q·b + r işlemini tekrarlayıp (a, b) yerine (b, r) koyarak ebob(a, b)’yi bulur; sıfırdan farklı son kalan ebob’dur. Sonra ekok(a, b) = a·b/ebob(a, b). Kalanlar her adımda indirgenebilir: (a + b) mod n ve (a·b) mod n yalnızca a mod n ve b mod n’e bağlıdır.
Her sayıyı indirgeyin
914 ≡ 1, 953 ≡ 7 (mod 11)
Birleştirin
1·7 = 7 ≡ 7 (mod 11)
Cevap
(914·953) mod 11 = 7
Örnek 2Orta
Euler’in φ fonksiyonunu bulun, φ(637): 1’den 637’e kadar 637 ile aralarında asal olan tam sayıların sayısı.
n = 637 = 72·13
İstenen: φ(637)
İpuçlarını göster
n sayısını asal çarpanlarına ayırın: 637 = 72·13.
φ aralarında asal çarpanlar için çarpımsaldır ve φ(pᵏ) = pᵏ − pᵏ⁻¹.
φ(n) = n·∏(1 − 1/p).
Cevabı ve adım adım çözümü göster
Tersler ve denklikler: a’nın n modunda tersi, tam olarak ebob(a, n) = 1 olduğunda vardır. Genişletilmiş Öklid algoritması 1 = s·n + t·a yazar ve sonra a⁻¹ ≡ t (mod n) olur. ebob(a, n) = 1 olan a·x ≡ b (mod n) denkliğinin çözümü x ≡ a⁻¹·b’dir. Modülleri aralarında asal olan x ≡ r₁ (mod m₁) ve x ≡ r₂ (mod m₂) denkliklerinin m₁·m₂ modunda bir çözümü vardır (Çin kalan teoremi). Euler’in φ(n) fonksiyonu 1’den n’ye kadar n ile aralarında asal olan sayıları sayar: φ(n) = n·∏(1 − 1/p).
Asal çarpanlar
637 = 72·13
φ değeri
φ(637) = φ(49)·φ(13) = 42·12 = 504
Cevap
φ(637) = 504
Örnek 3Zor
Bir RSA anahtarı p = 13, q = 37 ve e = 23 kullanıyor. c = 225 şifreli metnini çözün: mesajı, m, bulun.
p = 13q = 37e = 23c = 225
İstenen: m
İpuçlarını göster
n = 481, φ(n) = 432.
d = e⁻¹ mod φ(n) = 263.
m = cd mod n = 225263 mod 481: tekrarlı kare almayı kullanın.
Cevabı ve adım adım çözümü göster
Modüler kuvvetler ve RSA: aᵏ mod n değerini tekrarlı kare almayla hesaplayın: k’yi ikilik tabanda yazın, kare alın, her adımdan sonra indirgeyin ve biti 1 olan kuvvetleri çarpın. Fermat: a’yı bölmeyen bir p asalı için aᵖ⁻¹ ≡ 1 (mod p); dolayısıyla üs p − 1 modunda indirgenebilir. RSA: p ve q asallarını seçin, n = p·q ve φ(n) = (p − 1)(q − 1); genel üs e, φ(n) ile aralarında asaldır ve özel üs d = e⁻¹ mod φ(n)’dir. c = mᵉ mod n ile şifreleyin ve m = cᵈ mod n ile çözün.
Özel üs
n = 481, φ(n) = 432
d = 23−1 mod 432 = 263
Tekrarlı kare almayla çözün
263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)
Mesaj
m = 361
kontrol: 36123 mod 481 = 225
Cevap
m = 361
Sorular ve cevaplar
Sayılar kuramı ve modüler aritmetik nedir?
a’yı n’ye bölmek bir bölüm q ve bir kalan r verir: a = q·n + r, 0 ≤ r < n. Kalan a mod n olarak yazılır. Negatif bir sayıda q de negatiftir: −3 = −1·7 + 4, dolayısıyla −3 mod 7 = 4.
Aynı kalanı bırakıyorlarsa, yani n sayısı a − b’yi bölüyorsa, iki sayı n modunda denktir, a ≡ b (mod n).
Sayılar kuramı ve modüler aritmetik soruları adım adım nasıl çözülür?
Önce her sayıyı n modunda indirgeyin; kalanlar 0 ile n − 1 arasındadır.
EBOB için Öklid algoritmasıyla art arda bölün; sıfırdan farklı son kalan EBOB’dur.
Bir ters için genişletilmiş algoritmayı çalıştırın ve a’nın katsayısını alın; negatifse n ekleyin.
a·x ≡ b denkliğini a⁻¹ ile çarparak çözün; iki denkliği x = r₁ + m₁k yazarak birleştirin.
Kuvvetler için üssü ikilik tabanda yazın ve art arda kare alın; RSA’da d = e⁻¹ mod φ(n) ve φ(n) = (p − 1)(q − 1)’dir.
Sayılar kuramı ve modüler aritmetik konusunda en sık yapılan hatalar nelerdir?
Negatif bir sayı için negatif kalan vermek.
Öklid algoritmasını ilk kalanda durdurmak.
Tersi n ekleyerek pozitif yapmak yerine negatif bırakmak.
RSA üssü d’yi φ(n) yerine n modunda almak.
Fermat teoreminde üssü p − 1 yerine p modunda indirgemek.
Sayılar kuramı ve modüler aritmetik alıştırmaları neleri kapsar?
Kolay: ebob ve kalanlar
Orta: tersler ve denklikler
Zor: modüler kuvvetler ve RSA
Her soruda yeni değerler olur; böylece bir cevabı değil, yöntemi öğrenirsiniz. Takıldınız mı? Önce küçük bir ipucu açın, tam açıklamayı ise yalnızca gerektiğinde.
Çalışma nasıl işler
Her soruda yeni değerler olur; böylece bir cevabı değil, yöntemi öğrenirsiniz.
Takıldınız mı? Önce küçük bir ipucu açın, tam açıklamayı ise yalnızca gerektiğinde.
İlerlemeniz, hatalarınız ve kaydettiğiniz sorular saklanır; böylece sınavdan önce gözden geçirebilirsiniz.