Yazan : Şadi Evren ŞEKER

Steven Pohlig ve Marin Hellman tarafından geliştirilen, ayrık logaritma probleminin (discrete logarithm) çözümü için bir alternatif sunan algoritmadır.

Algoritma basitçe aşağıdaki denklemde bulunan x değerine bir çözüm arar:

egx (mod p)

Bu durum tam olarak da ayrık logaritmanın tanımıdır ve yukarıdaki denklem, aşağıdaki hale dönüştürülebilir:

x ≡ logg e (mod p)

Algoritma birkaç adımdan oluşur.

  1. Ayrık logaritması hesaplanacak olan grubun (g) asal çarpanlarının bulunması. Bu aşama için totient fonksiyonu (totient function) kullanılır.
  2. Birinci adımda bulunan değerler için çin kalan teorisinin kullanılması (chineese remainder theorem) ve her çarpan için ayrı bir denklem elde edilmesi. Bu aşamada da daha hızlı sonuca ulaşmak için bebek ve dev adımları algoritmasını (baby step giant step) kullanabiliriz
  3. İkinci adımın bütün asal sayılar için tekrarlanması
  4. İkinci ve üçüncü adımların tekrarlanması sonucunda elde edilen denklemlerin çin kalan teoremi ile çözümü.

Yukarıda adımları verilen bu algoritmanın çalışmasını bir örnek üzerinden görerek anlamaya çalışalım.

Örneğin ayrık logaritmasını bulmak istediğimiz denklem aşağıdaki şekilde verilmiş olsun.

x ≡ log6 7531 (mod 8101)

Daha açık olması açısından, yukarıdaki denklemi, aşağıdaki şekilde de yazabiliriz.

75316x (mod 8101)

Öncelikle totient fonksiyonu bulmak için çarpanlarına ayırma işlemi yapıyoruz:

p-1 = 8101 – 1 = 8100 = 223452 olarak yazılabilir. (Lütfen Ferma’nın küçük teoremini hatırlayınız (Fermat’s little theorem))

Yukarıda elde edilen bu değerler Çin kalan teoremine göre aşağıdaki şekilde bir denkleme işaret eder:

x2 ≡ x mod (22)

x3 ≡ x mod (34)

x5 ≡ x mod (52)

Yukarıdaki denklemleri yerine yazacak olursak:

x2 ≡ x mod (4)

x3 ≡ x mod (81)

x5 ≡ x mod (25)

Yukarıdaki denklemlerin her birini ayrı ayrı çözüp aynı x değeri için beklenen x2,x3 ve x5 değerlerini bulmaya çalışalım.

İlk olarak x2 değerini hesaplamaya çalışıyoruz. Denklemimizdeki mod işlemi 22 olduğu için 2 tabanında çift değer hesaplanacaktır.

x2=c0 (2)0+c1(2)1 ,olarak yazılabilir.

Bu denklemdeki çarpanları, aşağıdaki şekilde yapabiliriz:

İkinci çarpan için de aşağıdaki denklemi bulacağız:

İlk denklemi çözerek başlayalım.

7531 (p-1)/2 = 7531 4050 = -1, bunun anlamı, c0 değerimizin vâr olduğu ve 1 olduğudur.

İkinci denklemi çözmek için ilk denklemden elde ettiğimiz sonuca, 7531’i bölüyoruz.

7531(a)-1 = 7531(6751) = 8006 mod 8101

8006 (p-1)/4 = 8006 2025 = 1 ve dolayısıyla c1 değerini 0 olarak buluyoruz. (yukarıdaki ikinci denklemde sadece a0 =1 olacağı için c1(p-1)/2 değeri olacaktır ve bu durumda 0 veren tek c1 değeri 0’dır.)

x2 denklemine dönüp denklemimizi yeniden yazalım:

x2 = c0 (2)0+ c1(2)1 = 1 + 0 (2) = 1

dolayısıyla Çin kalan teoremindeki ilk denklemimiz:

1 ≡ x mod (22) olarak bulunmuş olunur.

Gelelim ikinci denklemimize,

x3 ≡ x mod (34)

4ncü dereceden olan denklemin çözümü için aşağıdaki denklemi yazabiliriz:

x3 = c0 (3)0 + c1 (3)1 + c2 (3)2 + c3(3)3 yazılabilir. Bu denklemi ilerletirsek:

x3 = c0 + 3c1 + 9c2 + 27c3 şeklinde yazabiliriz. Denklemimizdeki çarpanları teker teker bulalım:

7531 (p-1)/3 mod 8101 = 2217 buradan c0 = 2 olarak bulunur.

Sıradaki çarpan olan c1’i bulmak için önce 7531 sayısını c0’a bölüyoruz:

7531 / 2 = 6735 mod 8101 bulunuyor. Ve c1 için denklemi çözüyoruz:

6735 (p-1)/9 = 1 dolayısıyla c1 = 0 olarak bulunuyor.

6735 değerini a3c1 değerine bölüyoruz 6735 / a0 = 6735 mod 8101 ve denklemimizi yazıpyoruz:

6735(p-1)/27 = 2217 olarak bulunuyor ve c2 = 2 sonucuna varıyoruz. Son olarak c3 hesaplayabilmek için 6735 / a9c2 değerini hesaplıyoruz:

6735 / a18 = 6992 mod 8101 olarak bulunuyor.

Denklemimizi yazarsak

6992 (p-1) / 81 = 5883 olarak bulunuyor ve bu değere göre c3 = 1 bulunuyor.

Denklemimizi yeniden yazarsak:

x3 = c0 + 3c1 + 9c2 + 27c3

x3 = 2 + 3 0 + 9 2+ 27 1

x3 = 47 olarak bulunur. Bu durumda çin kalan teoremindeki ikinci denklemimiz aşağıdaki şekildedir:

47 ≡ x mod (34)

Gelelim son denklemimize:

x5 ≡ x mod (52)

Denklemimiz ikinci dereceden olduğu için x5 denklemini aşağıdaki şekilde iki çarpanla yazabiliriz:

x5 ≡ c0 + 5c1

7531(p-1)/5 = 5221 dolayısıyla c0 = 4 olarak bulunur.

Bölme işleminden sonra 7531 / a4 = 7613 mod 8101

7613(p-1)/25 = 356 dolayısıyla c1 = 2 olarak bulunur.

Denklemimizi yeniden yazacak olursak

x5 = 4 + 2 5 = 14 olarak bulunur ve denklemimiz:

14 ≡ x mod (52) olarak yazılabilir.

Şimdi yukarıda elde ettiğimiz üç denklemi yeniden listeleyelim :

1 ≡ x mod (22)

47 ≡ x mod (34)

14 ≡ x mod (52)

Çin kalan teorisine göre her değerin tersini bulup çarpalım:

4 x 81 x 25 = 8100

8100 / 4 = 2025 ve 2025’in mod 4 için tersi 1

8100 / 81 = 100 ve 100’ün mod 81 için tersi 64

8100 / 25 = 324 ve 324’ün mod 25 için tersi 24 olarak bulunur. Denklemde yerine yazarsak:

X = 1 2025 1 + 47 100 67 + 14 324 24 = 6689 mod 8101 olarak bulunmuş olunur.

Şimdi sorunun başına dönüp sağlamamızı yapalım:

75316x (mod 8101)

Denkleminde x = 6689 olması durumu için denk oldukları görülebilir.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


7 × dokuz =