← Bergeç Arşiv
Üç bölümlük dizi · 05.02.2026 · 15 dk okuma

Enigma Bölüm 1

Matematiksel Ön Hazırlık
Yazar: Yasin Aydın

Bu çalışmada, 2. Dünya Savaşı sırasında Almanların mesajlarını şifrelemek için kullandığı Enigma makinesini anlatacağım. Yazı temel olarak üç bölümden oluşmaktadır: bu ilk bölüm permütasyonları, döngüleri, eşlenik permütasyonları, transpozisyonları ve involüsyonları ele aldığım matematiksel ön hazırlık kısmıdır. İkinci bölüm Enigma'nın bileşenlerinin çalışma prensipleri ve sistemin matematiksel olarak incelenmesi üzerine, son bölüm ise Enigma'nın çözülmesi süreci üzerine olacak.

Bir Enigma şifreleme makinesi ve Alan Turing
Bir Enigma M3 şifreleme makinesi ve Alan Turing.

Bir Kümenin Permütasyonları

Tanım 1 (Permütasyon). S, bir küme olsun. \pi: S \to S birebir ve örten fonksiyonuna S kümesinin bir permütasyonu denir. S kümesinin permütasyonlarının kümesi \mathrm{Sym}(S) olarak ifade edilir. Yani,
$$\mathrm{Sym}(S) = \{\pi \mid \pi: S \to S \text{ birebir ve örten}\}.$$
Ayrıca, n pozitif bir tam sayı olmak üzere, \mathrm{Sym}(\{1,2,\dots,n\}) kümesi de S_n olarak yazılır.

Gösterim 1. \pi \in \mathrm{Sym}(S) ve x, y \in S olsun. \pi(x) = y'yi x\pi = y olarak yazacağız.

Tanım 2. S, boş olmayan bir küme, x \in S ve \sigma \in \mathrm{Sym}(S) olmak üzere, eğer x\sigma = x ise \sigma, x'i sabitler denir ve x elemanına \sigma'nın bir sabit noktası denir.

Şimdi \mathrm{Sym}(S) kümesinin bazı özelliklerini inceleyelim. \mathrm{id}_S: S \to S ve tüm x \in S için \mathrm{id}_S(x) = x fonksiyonu birebir ve örten bir fonksiyondur, yani \mathrm{id}_S \in \mathrm{Sym}(S)'dir. Bu \mathrm{id}_S elemanı, \mathrm{Sym}(S) kümesinin birim elemanıdır ve e olarak da yazılır. Şimdi \sigma, \rho \in \mathrm{Sym}(S) olsun. \sigma ve \rho birebir ve örten fonksiyon olduğu için \sigma \circ \rho: S \to S fonksiyonu da birebir ve örten bir fonksiyon olur, yani \sigma \circ \rho \in \mathrm{Sym}(S)'dir. Bu bileşkeyi kısaca \rho\sigma olarak göstereceğiz. Son olarak, eğer \sigma \in \mathrm{Sym}(S) ise \sigma, birebir ve örten bir fonksiyon olduğundan dolayı \sigma'nın tersi \sigma^{-1}: S \to S vardır ve birebir ve örten bir fonksiyondur, yani \sigma^{-1} \in \mathrm{Sym}(S)'dır. Ayrıca ters fonksiyonun tanımı gereği \sigma\sigma^{-1} = \sigma^{-1}\sigma = e eşitliği sağlanır.

Teorem 1. S, boş olmayan bir küme olsun. \sigma_1, \sigma_2, \dots, \sigma_k \in \mathrm{Sym}(S) olsun. (\sigma_1\sigma_2 \dots \sigma_k)^{-1} = \sigma_k^{-1}\sigma_{k-1}^{-1} \dots \sigma_1^{-1} olur.
Kanıt 1.

İspatı k üzerinden tümevarım ile yapacağız. P(k) önermesi, (\sigma_1\sigma_2 \dots \sigma_k)^{-1} = \sigma_k^{-1}\sigma_{k-1}^{-1} \dots \sigma_1^{-1} eşitliği olsun.

k = 1 için \sigma_1^{-1} = \sigma_1^{-1} olduğundan P(1) açıkça doğrudur.

Şimdi P(2) durumuna bakalım. Bir elemanın tersinin tanımı gereği (\sigma_1\sigma_2)(\sigma_1\sigma_2)^{-1} = e olur. Eşitliği soldan \sigma_1^{-1} ile çarparsak \sigma_1^{-1}(\sigma_1\sigma_2)(\sigma_1\sigma_2)^{-1} = \sigma_1^{-1} elde ederiz. Birleşme özelliğinden ve \sigma_1^{-1}\sigma_1 = e olduğundan dolayı \sigma_2(\sigma_1\sigma_2)^{-1} = \sigma_1^{-1} kalır. Son olarak her iki tarafı soldan \sigma_2^{-1} ile çarparsak (\sigma_1\sigma_2)^{-1} = \sigma_2^{-1}\sigma_1^{-1} elde edilir. Yani P(2) doğrudur.

Şimdi P(k)'nın doğru olduğunu varsayalım ve P(k+1)'i inceleyelim.

$$(\sigma_1\sigma_2 \dots \sigma_k\sigma_{k+1})^{-1} = ((\sigma_1 \dots \sigma_k)\sigma_{k+1})^{-1}$$

şeklinde gruplayabiliriz. P(2) doğru olduğu için bu ifade \sigma_{k+1}^{-1}(\sigma_1 \dots \sigma_k)^{-1} şeklinde açılır. Tümevarım hipotezinden dolayı parantez içi \sigma_k^{-1} \dots \sigma_1^{-1} olarak yazılır. Sonuç olarak:

$$\sigma_{k+1}^{-1}(\sigma_k^{-1} \dots \sigma_1^{-1}) = \sigma_{k+1}^{-1}\sigma_k^{-1} \dots \sigma_1^{-1}$$

elde edilir. Yani P(k+1) doğrudur. ∎

Tanım 3 (Üs alma). S, boş olmayan bir küme ve \sigma \in \mathrm{Sym}(S) olsun. n \in \mathbb{N} için \sigma^n özyinelemeli olarak şu şekilde tanımlanır:
$$\sigma^n = \begin{cases} e & \text{eğer } n = 0 \\ \sigma^{n-1}\sigma & \text{eğer } n > 0 \end{cases}$$
Ayrıca, her n \in \mathbb{Z}^+ için \sigma^{-n} ifadesi, \sigma^n elemanının tersi olarak tanımlanır:
$$\sigma^{-n} = (\sigma^n)^{-1}$$

Gösterim 2. S, n elemanlı sonlu bir küme; \sigma \in \mathrm{Sym}(S) ve S'nin elemanları x_1, x_2, \dots, x_n olsun. Bu durumda \sigma şöyle gösterilebilir:

$$\sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \\ x_1\sigma & x_2\sigma & \cdots & x_n\sigma \end{pmatrix}$$

Ayrıca, enigma bağlamında S kümesi (alfabe) doğal bir sıralamaya sahip olduğu için, permütasyonu kısaca sadece görüntü kümesini yazarak

$$[\, x_1\sigma \quad x_2\sigma \quad \cdots \quad x_n\sigma \,]$$

biçiminde de gösterebiliriz. Tanım kümesindeki elemanların sabit bir sırası olmadığı durumlarda bu gösterim belirsizlik yaratabileceğinden kullanılmamalıdır.

Birkaç örnek yapalım: S = \{1,2,3,4\} olsun. Bu gösterimde

$$\mathrm{id}_S = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix}$$

olur. \sigma, \tau \in \mathrm{Sym}(S) olsun. \sigma ve \tau'yu aşağıdaki gibi tanımlayalım.

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix} \quad \text{ve} \quad \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}$$

Bu durumda,

$$\sigma\tau = \tau \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix}$$

ve

$$\tau\sigma = \sigma \circ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}$$

olur. Görüldüğü üzere \sigma\tau \neq \tau\sigma. Şimdi de \sigma'nın ve \tau'nun tersini bulalım:

$$\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix} \quad \text{ve} \quad \tau^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}$$

olur.

Döngü Kavramı

Tanım 4 (Döngü). S, n elemanlı bir küme ve \sigma \in \mathrm{Sym}(S) olsun. k \le n ve x_1, x_2 \dots x_k \in S farklı elemanlar olmak üzere, eğer \sigma
  • 1 \le i < k için x_i\sigma = x_{i+1},
  • x_k\sigma = x_1 ve
  • x \notin \{x_1, x_2, \dots, x_k\} için x\sigma = x
şartlarını sağlıyorsa \sigma'ya k-döngü ya da kısaca döngü denir. Burada k, \sigma'nın uzunluğudur.

Gösterim 3 (Döngü). Yukarıda tanımlanan \sigma k-döngüsü (x_1\, x_2\, \dots\, x_k) olarak gösterilebilir. Bu gösterimde kendine giden elemanlar yazılmaz. Ayrıca bu gösterim biricik değildir. (x_1\,x_2\,\dots\,x_k) = (x_2\,x_3\,\dots\,x_k\,x_1) = \dots = (x_k\,x_1\,\dots\,x_{k-1}). Bunların hepsi S kümesinin aynı \sigma permütasyonuna tekabül eder.

Yukarıda örnek olarak verdiğimiz \sigma ve \tau birer 4-döngüdür. Yeni döngü gösteriminde \sigma = (1\,2\,4\,3) ve \tau = (1\,4\,2\,3) olarak yazılır. Bu gösterimde döngülerin tersini bulmak kolaydır. Döngünün elemanları ters çevrilerek döngünün tersi bulunabilir. Bu yaklaşımla \sigma^{-1} = (3\,4\,2\,1) olarak bulunur.

Tanım 5 (Ayrık döngüler). S, n elemanlı sonlu bir küme ve \sigma_1, \sigma_2 \in \mathrm{Sym}(S) birer döngü olsun. x_1, \dots, x_k, y_1, \dots, y_l \in S olmak üzere, \sigma_1 = (x_1\,x_2\,\dots\,x_k) ve \sigma_2 = (y_1\,y_2\,\dots\,y_l) döngüleri için; eğer
$$\{x_1, \dots, x_k\} \cap \{y_1, \dots, y_l\} = \varnothing$$
oluyorsa, \sigma_1 ve \sigma_2'ye ayrık döngüler denir.
Teorem 2. S, n elemanlı sonlu bir küme ve \sigma_1, \sigma_2 \in \mathrm{Sym}(S) ayrık döngüler olsun. Bu durumda \sigma_1\sigma_2 = \sigma_2\sigma_1 olur.
Kanıt 2.

S, n elemanlı sonlu bir küme ve \sigma_1, \sigma_2 \in \mathrm{Sym}(S) ayrık döngüler olsun. \sigma_1 = (x_1\,x_2\,\dots\,x_k) ve \sigma_2 = (y_1\,y_2\,\dots\,y_l) olarak yazılsın. S kümesinden keyfi bir x elemanı alalım. x için üç durum söz konusudur:

Durum 1: x \in \{x_1, x_2, \dots, x_k\} olsun. Yani bir 1 \le i \le k için x = x_i olur. Şimdi eşitliğin iki tarafına bakalım:

  • x(\sigma_1\sigma_2) = (x\sigma_1)\sigma_2. Döngünün tanımından dolayı eğer i \neq k ise x_i\sigma_1 = x_{i+1} olur. Bu durumda (x\sigma_1)\sigma_2 = x_{i+1}\sigma_2 olur. Döngüler ayrık olduğu için ve x_{i+1} \in \{x_1, \dots, x_k\} olduğu için x_{i+1}\sigma_2 = x_{i+1} olur. i = k ise x_k\sigma_1 = x_1 olur. Aynı sebepten x\sigma_1\sigma_2 = x_k\sigma_1\sigma_2 = x_1\sigma_2 = x_1 olur.
  • x(\sigma_2\sigma_1) = (x\sigma_2)\sigma_1 = x\sigma_1. Döngünün tanımından dolayı eğer i \neq k ise x\sigma_1 = x_i\sigma_1 = x_{i+1} olur. i = k ise x_k\sigma_1 = x_1 olur.

Her iki durumda da sonuç aynı olduğu için eşitlik sağlanır.

Durum 2: x \in \{y_1, y_2, \dots, y_l\} olsun. Durum 1'e benzer şekilde kanıtlanabilir. Simetriden dolayı x\sigma_1\sigma_2 = x\sigma_2\sigma_1 sağlanır.

Durum 3: x \notin \{x_1, \dots, x_k\} ve x \notin \{y_1, \dots, y_l\} olsun. Bu durumda x her iki döngüde de yer almadığı için, iki döngü de x'i sabit bırakır: x\sigma_1 = x ve x\sigma_2 = x olur. Buradan: x\sigma_1\sigma_2 = x ve x\sigma_2\sigma_1 = x olur.

Sonuç olarak, her x \in S için x\sigma_1\sigma_2 = x\sigma_2\sigma_1 sağlandığından \sigma_1\sigma_2 = \sigma_2\sigma_1 olur. \blacksquare

Teorem 3. S, n elemanlı sonlu bir küme olsun. Her \sigma \in \mathrm{Sym}(S) permütasyonu, ayrık döngülerin çarpımı olarak yazılabilir ve bu yazılış, döngülerin sıralanışı haricinde biriciktir.
Kanıt 3.

x_1 \in S olsun. O_1 = \{x_1, x_1\sigma, x_1\sigma^2, \dots\} kümesine bakalım. S sonlu bir küme olduğu ve O_1 \subseteq S olduğu için, bu küme de sonludur. Dolayısıyla dizideki elemanlar bir süre sonra tekrar etmelidir. Yani 0 \le i < j olacak şekilde öyle i, j doğal sayıları vardır ki;

$$x_1\sigma^i = x_1\sigma^j$$

eşitliği sağlanır. Eşitliğin her iki tarafına sağdan \sigma^{-i} uygulayalım. Bu durumda x_1 = x_1\sigma^{j-i} olur.

A = \{k \in \mathbb{Z}^+ \mid x_1\sigma^k = x_1\} kümesini tanımlayalım. A \neq \varnothing olduğunu kanıtladık. A \subseteq \mathbb{Z}^+ olduğu için İyi Sıralama İlkesi gereği A kümesinin en küçük elemanı vardır. Bu eleman k_1 olsun. Şimdi x_1, x_1\sigma, \dots, x_1\sigma^{k_1-1} elemanlarının hepsinin farklı elemanlar olduğunu kanıtlayalım.

Bu elemanlardan ikisi aynı olsun. Yani 0 \le i < j \le k_1 - 1 için x_1\sigma^i = x_1\sigma^j olsun. Her iki tarafı sağdan \sigma^{-i} ile çarpalım. Bu durumda, x_1\sigma^{j-i} = x_1 olur. Yani j - i \in A olur. 0 \le j - i < k_1 olduğu için 1 \le j - i < k_1 olur. Bu k_1'in A kümesinin en küçük elemanı olmasıyla çelişir. Sonuç olarak, (x_1\, x_1\sigma\, \dots\, x_1\sigma^{k_1-1}) döngü olur.

Şimdi S \setminus O_1 kümesine bakalım. Eğer S \setminus O_1 = \varnothing ise \sigma permütasyonu tek bir döngüdür. Değilse, x_2 \in S \setminus O_1 alalım ve aynı yöntemi uygulayalım. Bu durumda (x_2\, x_2\sigma\, \dots\, x_2\sigma^{k_2-1}) ikinci bir döngü olur.

Şimdi (x_1\,x_1\sigma\,\dots\,x_1\sigma^{k_1-1}) ve (x_2\,x_2\sigma\,\dots\,x_2\sigma^{k_2-1}) döngülerinin ayrık olduğunu kanıtlayalım. Ayrık olmadıklarını varsayalım. O halde her iki döngüde de bulunan bir x \in S vardır. 0 \le i < k_1 ve 0 \le j < k_2 olmak üzere; x = x_1\sigma^i = x_2\sigma^j olsun. Her iki tarafa sağdan \sigma^{-j} uygulayarak x_2 = x_1\sigma^{i-j} elde edilir.

(i-j) sayısına k_1 ile bölme algoritması uygulayalım. q \in \mathbb{Z} ve 0 \le r < k_1 olmak üzere i - j = qk_1 + r olsun. Bu durumda:

$$x_2 = x_1\sigma^{i-j} = x_1\sigma^{qk_1+r} = x_1(\sigma^{k_1})^q\sigma^r$$

x_1\sigma^{k_1} = x_1 olduğundan, x_2 = x_1\sigma^r bulunur. 0 \le r < k_1 olduğundan bu ifade x_2 \in O_1 anlamına gelir. Ancak biz x_2'yi S \setminus O_1 kümesinden seçmiştik yani x_2 \notin O_1. Bu bir çelişkidir. Sonuç olarak bu iki döngü ayrıktır.

Bu işlemi S kümesindeki tüm elemanlar tükenene kadar sonlu adımda tekrarlayalım ve toplamda r tane ayrık döngü bulalım. Sonuç olarak \sigma permütasyonu:

$$\sigma = (x_1\, \dots\, x_1\sigma^{k_1-1})(x_2\, \dots\, x_2\sigma^{k_2-1}) \dots (x_r\, \dots\, x_r\sigma^{k_r-1})$$

şeklinde yazılabilir.

Şimdi bu yazılımın, döngülerin sıralanışı haricinde biricik olduğunu kanıtlayalım. \tau_1, \tau_2, \dots, \tau_k ve \rho_1, \rho_2, \dots, \rho_l kendi aralarında ayrık döngüler olmak üzere;

$$\sigma = \tau_1\tau_2 \dots \tau_k = \rho_1\rho_2 \dots \rho_l$$

olsun. Şimdi x_1\sigma \neq x_1 şartını sağlayan bir x_1 \in S alalım. Gerekirse döngülerin sıralanışını değiştirerek x_1 elemanının \rho_1 döngüsünde olduğunu varsayalım.

x_1 sabitlenmediği için diğer gösterimdeki \tau'lardan da birinde olmak zorundadır. Yine gerekirse \tau'ların sıralanışını değiştirerek x_1'in \tau_1'de olduğunu varsayalım.

\rho_1 bir döngü olduğu için, x_1 elemanının \sigma altındaki ardışık görüntüleri bu döngüyü oluşturur:

$$\rho_1 = (x_1\, x_1\sigma\, x_1\sigma^2\, \dots\, x_1\sigma^{m-1})$$

Aynı şekilde \tau_1 de x_1'i içeren bir döngü olduğu için, o da x_1'in \sigma altındaki aynı görüntülerinden oluşmak zorundadır. Yani:

$$\tau_1 = (x_1\, x_1\sigma\, x_1\sigma^2\, \dots\, x_1\sigma^{m-1})$$

olur. Buradan \rho_1 = \tau_1 elde edilir.

Eşitliğin her iki tarafından bu döngüler sadeleştirilirse:

$$\tau_2 \dots \tau_k = \rho_2 \dots \rho_l$$

kalır. Bu işlem, \sigma permütasyonunun sabitlemediği tüm elemanlar bitene kadar tekrarlanırsa, her i için \tau_i = \rho_i olduğu ve k = l olduğu görülür.

Sonuç olarak ayrık döngülere ayrışım biriciktir. \blacksquare

Tanım 6 (Döngü tipi). S, n elemanlı sonlu bir küme olsun. \sigma \in \mathrm{Sym}(S) permütasyonu, uzunlukları k_1, k_2, \dots, k_r olan ayrık döngülerin çarpımı olsun. k_1 \ge k_2 \ge \dots \ge k_r olmak üzere (k_1, k_2, \dots, k_r) dizisine \sigma'nın döngü tipi denir. Burada k_1 + k_2 + \dots + k_r = n olduğu açıktır.

Birkaç örnek yapalım: S = \{1,2,3,4,5\} kümesi üzerinde tanımlı iki permütasyon şu şekilde verilmiş olsun:

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix}, \quad \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 4 & 3 & 1 \end{pmatrix}$$

Bu permütasyonları ayrık döngülerin çarpımı olarak yazalım. Permütasyonların nereye gittiğini takip ederek döngüleri oluşturalım:

\sigma için: 1 \to 2 \to 4 \to 5 \to 3 \to 1

$$\sigma = (1\,2\,4\,5\,3)$$

\tau için: 1 \to 5 \to 1, 2 \to 2, 3 \to 4 \to 3

$$\tau = (1\,5)(3\,4)$$

Şimdi \sigma\tau çarpımını döngü gösterimini kullanarak hesaplayalım. İşlem sırası soldan sağa (x \xrightarrow{\sigma} y \xrightarrow{\tau} z) şeklinde olduğu için:

$$\sigma\tau = (1\,2\,4\,5\,3)(1\,5)(3\,4)$$

olur. Elemanları sırasıyla takip edelim: 1 \xrightarrow{\sigma} 2 \xrightarrow{\tau} 2 (Sonuç: 1 \to 2); 2 \xrightarrow{\sigma} 4 \xrightarrow{\tau} 3 (Sonuç: 2 \to 3); 3 \xrightarrow{\sigma} 1 \xrightarrow{\tau} 5 (Sonuç: 3 \to 5); 5 \xrightarrow{\sigma} 3 \xrightarrow{\tau} 4 (Sonuç: 5 \to 4); 4 \xrightarrow{\sigma} 5 \xrightarrow{\tau} 1 (Sonuç: 4 \to 1).

Döngü 1 \to 2 \to 3 \to 5 \to 4 \to 1 olur. Sonuç olarak:

$$\sigma\tau = (1\,2\,3\,5\,4)$$

olur. \sigma ve \tau'nun döngü tipini belirleyelim. \sigma için döngü tipi (5), \tau için (2,2,1) olur.

Yazarın Notu: Şu ana kadar bir S kümesinin permütasyonlarını ifade etmek için iki farklı gösterim inceledik. Bu konseptleri bilgisayarda programlarken, elemanlara erişim hızı açısından array tabanlı gösterimi kullanmak çok daha verimlidir. Çünkü S kümesinin elemanlarını bir dizinin indislerine eşleyerek, permütasyonun görüntüsünü O(1) zaman karmaşıklığında bulabiliriz.

Alternatif olarak döngüler, dairesel bağlı liste (circular linked list) veri yapısıyla da ifade edilebilir; ancak bu yapıda belirli bir elemanın görüntüsünü bulmak O(n) zaman karmaşıklığına sebep olabilir. Ben enigmayı simüle eden bilgisayar programımı C ile kodlarken permütasyonlar için array kullandım. S kümesi alfabedeki harflerden oluştuğu için, harflerin ASCII değerlerini kullanarak indisledim.

Bu array yapısını ayrık döngülerin çarpımı formatına dönüştüren algoritma yazmak, okuyucu için güzel bir programlama alıştırmasıdır. Ayrıca iki permütasyonun çarpımını hesaplayan veya bir permütasyonun tersini bulan fonksiyonları kodlamayı da alıştırma olarak deneyebilirsiniz.

Alıştırma 4. S_n kümesinde döngü tipi uzunluğu l_1 olan k_1 tane döngü, uzunluğu l_2 olan k_2 tane döngü, ..., uzunluğu l_r olan k_r tane döngü içeren permütasyon sayısını bulun. Burada k_1l_1 + k_2l_2 + \dots + k_rl_r = n'dir. (İpucu: Alıştırmayı çözerken problemi n kişiyi sıralaması önemsiz olan yuvarlak masalara yerleştirmek olarak düşünebilirsiniz.)

Eşlenik Permütasyonlar

Şimdi enigmanın bazı özelliklerini anlamak için gerekli olan oldukça önemli olan eşlenik permütasyonlara geçelim.

Tanım 7 (Eşlenik Permütasyonlar). S, bir küme olsun. \sigma, \tau \in \mathrm{Sym}(S) olmak üzere, eğer bir \rho \in \mathrm{Sym}(S) için;
$$\sigma = \rho^{-1}\tau\rho$$
eşitliği sağlanıyorsa, \sigma ve \tau'ya eşlenik permütasyonlar denir.

Şimdi kanıtlayacağımız teoremler, Enigma'nın kriptanalizi açısından çok önemlidir. Eğer bu teoremleri tam olarak kavrayamazsanız, ileride Enigma kısmındaki mantığı anlamakta zorluk çekebilirsiniz.

Teorem 4. S, sonlu bir küme olsun. \sigma = (a_1\,a_2\,\dots\,a_k) \in \mathrm{Sym}(S) bir döngü ve \rho \in \mathrm{Sym}(S) olmak üzere;
$$\rho^{-1}(a_1\,a_2\,\dots\,a_k)\rho = (a_1\rho\, a_2\rho\, \dots\, a_k\rho)$$
eşitliği sağlanır.
Kanıt 4.

Tanımlanan permütasyonun etkisini incelemek için S kümesinden keyfi bir x elemanı seçelim ve \rho^{-1}\sigma\rho ifadesinin x\rho elemanı üzerindeki etkisine bakalım. Üç durum söz konusudur:

Durum 1: x \in \{a_1, a_2, \dots, a_{k-1}\} olsun. Bu durumda bir i indisi için x = a_i diyebiliriz. İşlemi takip edelim:

$$(x\rho)[\rho^{-1}(a_1 \dots a_k)\rho] = (a_i\rho)\rho^{-1}(a_1 \dots a_k)\rho = a_i(a_1 \dots a_k)\rho = a_{i+1}\rho$$

Bu sonuç, \rho^{-1}\sigma\rho ifadesinin a_i\rho'yi a_{i+1}\rho'ya götürdüğünü gösterir.

Durum 2: x = a_k olsun.

$$(a_k\rho)[\rho^{-1}(a_1 \dots a_k)\rho] = a_k(a_1 \dots a_k)\rho = a_1\rho$$

Bu da \rho^{-1}\sigma\rho ifadesinin a_k\rho'yu a_1\rho'ya yani başa götürdüğünü gösterir.

Durum 3: x \notin \{a_1, \dots, a_k\} olsun. Bu durumda x, \sigma döngüsünde yoktur, yani x\sigma = x olur.

$$(x\rho)[\rho^{-1}(a_1 \dots a_k)\rho] = x(a_1 \dots a_k)\rho = x\rho$$

Yani x\rho elemanı, oluşan yeni döngüde de sabit kalır.

Sonuç olarak,

$$\rho^{-1}(a_1 \dots a_k)\rho = (a_1\rho\, a_2\rho\, \dots\, a_k\rho)$$

olur. \blacksquare

Teorem 5. S, sonlu bir küme olsun. \sigma, \tau \in \mathrm{Sym}(S) permütasyonlarının eşlenik olması için gerek ve yeter şart, \sigma ve \tau'nun aynı döngü tipine sahip olmasıdır.
Kanıt 5.

S, sonlu bir küme olmak üzere \sigma, \tau \in \mathrm{Sym}(S) olsun. Eşlenik olmanın tanımından dolayı öyle \rho \in \mathrm{Sym}(S) için \tau = \rho^{-1}\sigma\rho olur. Teorem 3'e göre \sigma ayrık döngülerin çarpımı şeklinde yazılabilir. \sigma_1, \sigma_2, \dots, \sigma_n ayrık döngüler olmak üzere:

$$\sigma = \sigma_1\sigma_2 \dots \sigma_n$$

olsun. İşlemleri takip ederek:

$$\tau = \rho^{-1}\sigma\rho = \rho^{-1}\sigma_1\sigma_2 \dots \sigma_n\rho = (\rho^{-1}\sigma_1\rho)(\rho^{-1}\sigma_2\rho) \dots (\rho^{-1}\sigma_n\rho)$$

elde ederiz. Teorem 4'ten dolayı \rho^{-1}\sigma_i\rho ile \sigma_i aynı uzunlukta döngülerdir. Sonuç olarak \sigma ve \rho^{-1}\sigma\rho aynı döngü tipine sahiptir.

Teoremin diğer yönünü kanıtlayalım. \sigma, \tau \in \mathrm{Sym}(S) aynı döngü tipine sahip olsun. Bu iki permütasyonu, uzunlukları eşleşecek şekilde uzunluğu 1 olan döngüleri de dahil ederek ayrık döngülerin çarpımı olarak yazalım:

$$\sigma = (\alpha_{1,1}\,\alpha_{1,2}\,\dots\,\alpha_{1,k_1}) \dots (\alpha_{r,1}\,\alpha_{r,2}\,\dots\,\alpha_{r,k_r})$$
$$\tau = (\beta_{1,1}\,\beta_{1,2}\,\dots\,\beta_{1,k_1}) \dots (\beta_{r,1}\,\beta_{r,2}\,\dots\,\beta_{r,k_r})$$

Döngü tipleri aynı olduğu için her iki ifadede de r tane döngü vardır ve karşılıklı döngü uzunlukları (k_1, k_2, \dots, k_r) birbirine eşittir.

Şimdi \rho \in \mathrm{Sym}(S) permütasyonunu, \sigma'daki elemanları \tau'daki aynı konumdaki elemanlara eşleyecek şekilde tanımlayalım:

$$\alpha_{i,j}\rho = \beta_{i,j} \qquad (1 \le i \le r,\ 1 \le j \le k_i)$$

Bu tanım, \rho'nun tersinin de \beta_{i,j}\rho^{-1} = \alpha_{i,j} olduğunu gösterir.

Şimdi \rho^{-1}\sigma\rho = \tau eşitliğini kanıtlayalım. \rho^{-1}\sigma\rho ifadesinin herhangi bir \beta_{i,j} elemanı üzerindeki etkisine bakalım:

$$\beta_{i,j}(\rho^{-1}\sigma\rho) = (\alpha_{i,j}\sigma)\rho = \alpha_{i,j+1}\rho = \beta_{i,j+1} \qquad (1 \le i \le r,\ 1 \le j < k_i)$$
$$\beta_{i,k_i}(\rho^{-1}\sigma\rho) = (\alpha_{i,k_i}\sigma)\rho = \alpha_{i,1}\rho = \beta_{i,1}$$

Bu da

$$\rho^{-1}\sigma\rho = \tau$$

olduğunu gösterir. Dolayısıyla \sigma ve \tau eşleniktir. \blacksquare

Alıştırma 5. S bir küme olsun. \sigma, \tau \in \mathrm{Sym}(S) olmak üzere;
$$\sigma \sim \tau \iff \exists \rho \in \mathrm{Sym}(S) \text{ için } \sigma = \rho^{-1}\tau\rho$$
şeklinde tanımlanan \sim bağıntısının, \mathrm{Sym}(S) üzerine bir denklik bağıntısı olduğunu kanıtlayın.

Transpozisyonlar ve İnvolüsyonlar

Bu kısım, doğru anahtara sahip bir alıcının Enigma ile şifrelenmiş mesajın nasıl deşifre edildiğini anlamak açısından önemlidir.

Tanım 8 (Transpozisyon). Uzunluğu iki olan döngülere transpozisyon denir.
Teorem 6. S, sonlu bir küme olsun. Her \sigma \in \mathrm{Sym}(S), transpozisyonların çarpımı olarak yazılabilir.
Kanıt 6.

Her permütasyon ayrık döngülerin çarpımı olarak yazılabildiğinden, sadece döngülerin transpozisyonların çarpımı olarak yazılabildiğini göstermek yeterlidir.

(x_1\,x_2\,\dots\,x_k) döngüsünü ele alalım. Bu döngünün şu şekilde transpozisyonlara ayrılabileceğini iddia ediyoruz:

$$(x_1\,x_2\,\dots\,x_k) = (x_1\,x_2)(x_1\,x_3)\dots(x_1\,x_k)$$

Eşitliğin sağ tarafındaki işlemi kontrol edelim. Toplam üç duruma sahibiz.

Durum 1: x_1 için: İlk transpozisyon (x_1\,x_2) ile x_2'ye dönüşür. Diğerlerinde x_2 yoktur. Bundan dolayı x_1 \to x_2 olur.

Durum 2: x_i için (1 < i < k): x_i elemanı (x_1\,x_i) gelene kadar sabitlenir. Bu adımda x_i \to x_1 olur. Hemen sonraki (x_1\,x_{i+1}) adımında ise x_1 \to x_{i+1} olur. Bileşkesini aldığımızda x_i \to x_{i+1} elde ederiz.

Durum 3: x_k için: x_k sadece (x_1\,x_k)'da bulunur ve x_1'e dönüşür. Bundan dolayı x_k \to x_1 olur.

Dolayısıyla (x_1\,x_2)(x_1\,x_3)\dots(x_1\,x_k) = (x_1\,x_2\,\dots\,x_k) olur. \blacksquare

Tanım 9 (İnvolüsyon). S bir küme olsun. \sigma \in \mathrm{Sym}(S), \sigma^{-1} = \sigma şartını sağlıyorsa \sigma'ya involüsyon denir.
Teorem 7. S, sonlu bir küme olsun. Birimden farklı \sigma \in \mathrm{Sym}(S)'nin involüsyon olmasının gerek ve yeter koşulu, \sigma'nın ayrık transpozisyonların çarpımı olarak yazılabilmesidir.
Kanıt 7.

S sonlu bir küme olsun ve birimden farklı \sigma \in \mathrm{Sym}(S) ayrık transpozisyonların çarpımı olarak şöyle yazılsın:

$$\sigma = (x_1\,x_2)(x_3\,x_4)\dots(x_{2k-1}\,x_{2k})$$

Şimdi \sigma^2 ifadesine bakalım:

$$\sigma\sigma = [(x_1\,x_2)\dots(x_{2k-1}\,x_{2k})][(x_1\,x_2)\dots(x_{2k-1}\,x_{2k})]$$

Verilen transpozisyonlar ayrık olduğu için birbirleriyle değişmelidirler. Bu özelliği kullanarak aynı transpozisyonları yan yana getirebiliriz:

$$\sigma^2 = (x_1\,x_2)(x_1\,x_2)(x_3\,x_4)(x_3\,x_4)\dots(x_{2k-1}\,x_{2k})(x_{2k-1}\,x_{2k})$$

Her transpozisyonun karesinin birim permütasyon olduğunu kanıtlayalım. Tüm elemanlara \sigma^2'yi uygulayarak:

$$x_1 \xrightarrow{(x_1\,x_2)} x_2 \xrightarrow{(x_1\,x_2)} x_1$$

elde ederiz, yani elemanlar sabitlenir. Dolayısıyla:

$$\sigma^2 = e \cdot e \dots e = e$$

olur. \sigma^2 = e eşitliğinin her iki tarafını \sigma^{-1} ile çarparsak \sigma = \sigma^{-1} elde edilir.

Teoremin diğer yönünü kanıtlayalım. \sigma \in \mathrm{Sym}(S) birimden farklı bir involüsyon olsun. \sigma'nın ayrık transpozisyonların çarpımı olarak yazılamayacağını, yani uzunluğu n \ge 3 olan en az bir (x_1\,x_2\,\dots\,x_n) döngüsü içerdiğini varsayalım.

Bu döngüdeki x_1 elemanı için \sigma^2 etkisine bakalım:

$$x_1\sigma^2 = (x_1\sigma)\sigma = x_2\sigma = x_3$$

\sigma bir involüsyon olduğundan x_1\sigma^2 = x_1e = x_1 olmalıdır. Bu durumda x_1 = x_3 sonucu çıkar. Ancak döngü uzunluğu n \ge 3 olduğu için, döngü tanımı gereği x_1, x_2 ve x_3 birbirinden farklı elemanlardır. Yani x_1 \neq x_3 olur.

Bu bir çelişkidir. Dolayısıyla \sigma, uzunluğu 3 veya daha büyük olan bir döngü içeremez. \sigma birimden farklı bir eleman olduğu için tüm elemanlar sabitlenemez. Dolayısıyla \sigma, ayrık transpozisyonların çarpımıdır. \blacksquare

Bir sonraki bölümde, burada kurduğumuz matematiksel çerçeveyi kullanarak Enigma'nın bileşenlerini (rotorlar, yansıtıcı, fiş panosu) ve makinenin şifreleme/deşifreleme mantığını inceleyeceğiz.

Okumaya devam

Enigma dizisi · 1 / 3

Sonraki: Enigma Bölüm 2: Enigmanın Çalışma Prensibi →

Konular: Kriptografi · Kombinatorik

Bunları da okuyun

  1. Enigma Bölüm 3: Enigmanın Çözülmesi · 07.02.2026
  2. Knuth’un Kitabından Bir Soru (III) · 05.10.2026
  3. Knuth’un Kitabından Bir Soru (II) · 02.12.2025

Yorumlar

Beğenmek ya da yorum yazmak için GitHub hesabıyla giriş yapmanız gerekir.