Ana içerik
Bilgisayar Bilimi
Konu: Bilgisayar Bilimi > Ünite 2
Ders 5: Modüler Aritmetik- Modulo işlemcisi
- Modulo ile İlgili Zor Soru
- Denklik bağıntısı
- Modüler toplama ve çıkarma
- Modüler toplama
- Modulo ile İlgili Zor Soru (Toplama ve Çıkarma)
- Modüler çarpma
- Modüler çarpma
- Hızlı modüler üs alma
- Hızlı Modüler Üs Alma
- Öklid Algoritması
© 2023 Khan AcademyKullanım ŞartlarıGizlilik PolitikasıÇerez Politikası
Hızlı modüler üs alma
Eğer B 2'nin bir kuvvetiyse, A^B mod C'yi hızlıca nasıl hesaplarız ?
Modüler çarpmanın kurallarını kullanırsak:
ör. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
Bunu 7^256 mod 13 hızlıca hesaplamak için kullanabiliriz
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
Önceki 7^1 mod 13 cevabımızı bu denklem ile değiştirebiliriz.
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
Önceki 7^2 mod 13 cevabımızı bu denklem yerine koyabiliriz.
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
Önceki 7^4 mod 13 cevabımızı bu denklem ile değiştirebiliriz.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
Bu şekilde, önceki sonuçları bu denklemlerle değiştirerek devam ederiz.
... 5 yineleme sonunda:
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
Bu bize B'nin 2'nin kuvveti olduğu verildiğinde, A^B mod C 'yi hızlıca hesaplamak için bir metod verir.
Bununla birlikte, B 2'nin kuvveti değilken modüler üst almayı daha hızlı yapmak için bir metoda ihtiyacımız var.
Herhangi bir B için A^B mod C'yi hızlıca nasıl hesaplarız?
1. Adım: B'yi ikili sistemde yazarak 2'nin üstlerine böl
En sağdaki basamaktan başla, k=0 ve her basamak için:
- Eğer basamak 1 ise, 2^k için parçaya ihtiyacımız vardır, değilse yoktur
- k'ye 1 ekle ve soldaki basamağa geç
2. Adım: İki ≤ B'nin katlarına göre mod C'yi hesapla
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
3. Adım: Modüler çarpma özelliklerini kullanarak hesaplanmış mod C değerleri ile birleştir
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
Notlar:
Daha fazla optimizasyon tekniği bulunmaktadır ancak bunlar bu makalenin kapsamı dışındadırlar. Not edilmelidir ki, kriptografide modüler üst alma uygulandığında, B> 1000 kuvvetlerinin kullanılması alışılmadık değildir.
Tartışmaya katılmak ister misiniz?
Henüz gönderi yok.