Euler Totient Fonksiyonu φ(n): RSA Şifrelemenin Arkasındaki Sayım

Bir sayma oyunu

Bir öğretmen tahtaya yazıyor: $n = 12$. "12'den küçük ve 12 ile aralarında asal ($\gcd = 1$) olan pozitif tam sayılar?"

Sayalım: $1, 5, 7, 11$. Dört tane. Yani $\varphi(12) = 4$.

$n = 10$: $1, 3, 7, 9$ → $\varphi(10) = 4$.
$n = 7$ (asal): $1, 2, 3, 4, 5, 6$ → $\varphi(7) = 6$. (Aslında her asal $p$ için $\varphi(p) = p - 1$.)

Bu fonksiyon Euler totient fonksiyonu ya da kısaca phi fonksiyonu: $\varphi(n) = |\{k : 1 \leq k \leq n, \gcd(k, n) = 1\}|$.

Tanım son derece basit. Ama bu basit fonksiyon modern internet güvenliğinin matematik kalbidir.

İlk değerler

$n$	$\varphi(n)$
1	1
2	1
3	2
4	2
5	4
6	2
7	6
8	4
9	6
10	4
11	10
12	4

İlk gözlem: $\varphi(n)$ asallarda maksimum ($n - 1$); küçük asal çarpanları olan sayılarda küçük. Çünkü çok faktör → çok eleman silinir.

Asal kuvvet formülü

$p$ asal, $k \geq 1$:

$\varphi(p^k) = p^k - p^{k-1} = p^k\left(1 - \frac{1}{p}\right)$

Sezgi: $p^k$ küçük pozitif tam sayıların arasında $p$'nin katları olanlar $p, 2p, 3p, \ldots, p^{k-1} \cdot p = p^k$. Sayıları $p^{k-1}$. Geriye $p^k - p^{k-1}$ tane aralarında asal.

Örnek: $\varphi(8) = 8 - 4 = 4$. ($8 = 2^3$, $2^2 = 4$.)
$\varphi(27) = 27 - 9 = 18$.

Çarpımsallık (multiplicative property)

Kritik özellik: Eğer $\gcd(m, n) = 1$ ise:

$\varphi(mn) = \varphi(m) \cdot \varphi(n)$

İspat: Çin kalan teoremi (CRT) ile $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$. Bu bijection EBOB-1 elemanları korur.

Örnek: $\varphi(12) = \varphi(4) \cdot \varphi(3) = 2 \cdot 2 = 4$. ✓

Genel formül

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ ise:

$\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$

Yani $n$'nin asal çarpanlarına bakmak yeter.

Örnek: $n = 360 = 2^3 \cdot 3^2 \cdot 5$.

$\varphi(360) = 360 \cdot (1 - 1/2) \cdot (1 - 1/3) \cdot (1 - 1/5) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96$

Yani 360'tan küçük 96 tane EBOB-1 sayı vardır.

Euler teoremi — totient ile

Önceki yazılarımızda Fermat'nın küçük teoremine değindik: $p$ asal, $\gcd(a, p) = 1$ ⟹ $a^{p-1} \equiv 1 \pmod{p}$.

Euler bunu bileşik modüller için genelleştirdi:

$\gcd(a, n) = 1$ ⟹ $a^{\varphi(n)} \equiv 1 \pmod{n}$.

Euler teoremi. Asal halinde $\varphi(p) = p - 1$, yani Fermat'nın küçük teoremi bunun özel hali.

Örnek: $n = 12$, $a = 5$. $\varphi(12) = 4$. Beklenti: $5^4 \equiv 1 \pmod{12}$. Test: $5^4 = 625 = 12 \cdot 52 + 1$. ✓

RSA şifreleme — totient kalbinde

RSA açık anahtarlı şifreleme nasıl çalışır?

1. İki büyük asal seç: $p$ ve $q$.
2. $n = pq$. Açık (herkese verilir).
3. $\varphi(n) = (p-1)(q-1)$. Gizli (sadece sahip bilir).
4. Açık üs $e$ seç ($\gcd(e, \varphi(n)) = 1$).
5. Gizli üs $d = e^{-1} \pmod{\varphi(n)}$ (modüler ters; Bézout).
6. Şifreleme: $c = m^e \bmod n$. Çözme: $m = c^d \bmod n$.

Neden çalışır? $c^d = m^{ed} \pmod{n}$. $ed \equiv 1 \pmod{\varphi(n)}$ olduğundan $ed = 1 + k\varphi(n)$. Euler teoremi:

$m^{ed} = m \cdot m^{k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k = m \pmod{n}$

İşte. Euler totient olmasa RSA olmazdı. RSA olmasa modern internet bankacılığı olmazdı.

Toplam formülü — Gauss

Sevimli bir özdeşlik (Gauss):

$\sum_{d \mid n} \varphi(d) = n$

Yani $n$'nin tüm bölenleri için $\varphi$ değerlerini toplarsanız tam $n$ çıkar.

Örnek: $n = 12$. Bölenleri: $1, 2, 3, 4, 6, 12$. $\varphi$ değerleri: $1, 1, 2, 2, 2, 4$. Toplam: $1+1+2+2+2+4 = 12$. ✓

Bu özdeşlik Möbius dönüşümü ve klasik aritmetik fonksiyon analizinin temel taşı.

Asimptotik davranış

Büyük $n$ için ortalama:

$\frac{1}{N} \sum_{n \leq N} \varphi(n) \sim \frac{3N}{\pi^2}$

Yani rastgele bir $n$ için $\varphi(n) \approx (3/\pi^2) \cdot n \approx 0.304 \cdot n$. Diğer bir deyişle, iki rastgele tam sayının aralarında asal olma olasılığı $6/\pi^2 \approx 0.608$. $\pi$ neden ortaya çıktı? Riemann zeta fonksiyonu $\zeta(2) = \pi^2/6$ sayesinde — sayı teorisi ile analiz buluşur.

Lehmer'in totient problemi (1932)

D.H. Lehmer sordu: "Bileşik bir $n$ var mı ki $\varphi(n) \mid n - 1$ olsun?"

Asal $p$ için bu trivially doğru ($\varphi(p) = p-1$, ve $p-1 \mid p-1$). Ama bileşik bir örnek?

90 yıldan fazla geçti. Hiçbir bileşik örnek bulunamadı. Yoksa yok mu? Açık problem. Sonsuz tane bilemediğimiz şey olduğu kanıtlanmış sınırlar var.

Totient fonksiyonu ne kadar küçük olabilir?

Ufuk problemi: $\varphi(n)/n$ ne kadar küçük olabilir? Cevap: keyfi olarak küçük. $n = p_1 p_2 \cdots p_k$ (ilk $k$ asal) için:

$\frac{\varphi(n)}{n} = \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) \to 0 \text{ as } k \to \infty$

Yavaş ama gider. Mertens teoremi: $\frac{\varphi(n)}{n} \gtrsim \frac{1}{e^\gamma \ln \ln n}$ ($\gamma$ Euler-Mascheroni sabiti).

Mirası

Euler totient fonksiyonu:

• Modüler aritmetik: her tersinir elemanın grup düzeni bölünür.
• RSA: ed $\equiv 1 \pmod{\varphi(n)}$ kalbi.
• Asal sayı dağılımı: ortalama davranışı $\pi^2/6$ ile ilişkili.
• Açık problemler: Lehmer'in totient problemi gibi.

Euler 1763'te bu fonksiyonu tanıttı. 270 yıl sonra hâlâ:

• Her gün, milyarlarca işlemde kullanılır (her RSA imzası).
• Sayı teorisi araştırmasının merkezindedir.
• Olimpiyat matematiğinin klasik konularıdır.

Bir tek küçük sayma fonksiyonu. Onsuz internet güvenliği olmazdı. Matematiğin en sade ama en yararlı icatlarından biri.