4 Legendre Sembolü ve Euler Kriteri
Bir önceki bölümde bir sayının kuadratik rezidü (KR) veya kuadratik non-rezidü (KNR) olma durumunu denklemler üzerinden tanımlamıştık. Ancak sayılar büyüdükçe her defasında “acaba modülo \(p\)’de karesi \(a\)’yı veren bir sayı var mıdır?” diye tek tek kare alarak kontrol etmek imkânsızlaşır.
Bu durumu çok daha kompakt ve işlevsel bir forma sokan gösterim Legendre sembolüdür.
4.1 1. Legendre Sembolünün Tanımı
Tanım 4.1 (Legendre Sembolü) \(p\) bir tek asal sayı ve \(a\) herhangi bir tam sayı olsun. \(a\)’nın modülo \(p\)’ye göre kuadratik karakterini belirten Legendre sembolü \(\left( \frac{a}{p} \right)\) ile gösterilir ve şöyle tanımlanır:
\[ \left( \frac{a}{p} \right) = \begin{cases} \hphantom{-}1, & a,\ \bmod p \text{'de kuadratik rezidü ise} \\[0.3em] -1, & a,\ \bmod p \text{'de kuadratik non-rezidü ise} \\[0.3em] \hphantom{-}0, & p \mid a \text{ ise} \end{cases} \]
Örnek 4.1 (Legendre Sembolü Değerleri) 1. Kuadratik rezidü örneği. \(x^2 \equiv 1 \pmod 7\) kongrüansının çözülebilir olduğu bariz (\(x = 1\)). Bu durumda \(1\), modülo \(7\)’ye göre bir KR olduğundan sembolün değeri \(1\)’dir:
\[\left( \frac{1}{7} \right) = 1\]
2. Kuadratik non-rezidü örneği. \(x^2 \equiv 3 \pmod 5\) kongrüansını inceleyelim. Modülo \(5\)’te kareler \(\{1, 4\}\) olduğundan \(3\) bir KNR’dir; dolayısıyla:
\[\left( \frac{3}{5} \right) = -1\]
Tanımı basit görünse de, Legendre sembolünün asıl gücü sahip olduğu çarpımsal özelliklerden ve Euler kriterinden gelir.
4.2 2. Euler Kriteri ve Sembolün Özellikleri
Aşağıdaki teorem, Legendre sembolü ile modüler üs alma işlemi arasında kusursuz bir köprü kurar. Kriptografide büyük asallarla çalışırken, bir sayının KR olup olmadığını tespit etmek için çözülebilirlik testleri yapmak yerine yalnızca Euler kriteri kullanılır.
Teorem 4.1 (Euler Kriteri ve Legendre Sembolünün Özellikleri) \(p\) bir tek asal sayı; \(a\) ve \(b\) tam sayılar ve \(\gcd(a, p) = \gcd(b, p) = 1\) olsun. Bu durumda aşağıdaki dört özellik geçerlidir:
- Euler kriteri: \(\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod p\)
- Çarpımsallık kuralı: \(\left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right)\)
- Periyodiklik: \(a \equiv b \pmod p \implies \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right)\)
- Özel değerler: \(\left( \frac{a^2}{p} \right) = 1\), \(\left( \frac{1}{p} \right) = 1\), \(\left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}\)
1) Euler kriterinin ispatı. Bu ispatı, daha önce işlediğimiz \(n\). kuvvetten kongrüanslar teoreminin \(n = 2\) olan özel durumu üzerinden yapacağız.
KR durumu. \(a\) modülo \(p\)’ye göre bir KR olsun; bu durumda kongrüansın çözümü vardır ve önceki teoremimiz gereği \(a^{(p-1)/2} \equiv 1 \pmod p\) olmalıdır. Legendre tanımı gereği \(\left( \frac{a}{p} \right) = 1\) olduğundan:
\[\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod p\]
KNR durumu. \(a\) modülo \(p\)’ye göre bir KNR olsun. Çözüm yoktur ve önceki teorem gereği \(a^{(p-1)/2} \not\equiv 1 \pmod p\)’dir.
Öte yandan Fermat’nın küçük teoreminden \(a^{p-1} \equiv 1 \pmod p\) olduğunu biliyoruz. İki kare farkı olarak açarsak:
\[\big(a^{(p-1)/2} - 1\big)\big(a^{(p-1)/2} + 1\big) \equiv 0 \pmod p\]
\(p\) asal olduğu için bu çarpanlardan birini tam bölmek zorundadır. \(a^{(p-1)/2} \not\equiv 1 \pmod p\) olduğunu bildiğimizden birinci çarpanı bölemez; o hâlde mecburen ikinciyi böler:
\[a^{(p-1)/2} \equiv -1 \pmod p\]
Legendre tanımı gereği KNR için \(\left( \frac{a}{p} \right) = -1\) olduğundan eşitlik yine sağlanır.
2) Çarpımsallık kuralının ispatı. Euler kriterini \(a\) yerine \(ab\) alarak yazalım:
\[\left( \frac{ab}{p} \right) \equiv (ab)^{(p-1)/2} \equiv a^{(p-1)/2} \cdot b^{(p-1)/2} \pmod p\]
Yine Euler kriterinden \(a^{(p-1)/2} \equiv \left( \frac{a}{p} \right)\) ve \(b^{(p-1)/2} \equiv \left( \frac{b}{p} \right)\) olduğunu biliyoruz; yerlerine yazarsak:
\[\left( \frac{ab}{p} \right) \equiv \left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right) \pmod p\]
Sembollerin alabileceği değerler yalnızca \(1\) ve \(-1\)’dir. \(p > 2\) tek asal olduğundan modülo \(p\)’de \(1 \not\equiv -1\)’dir; dolayısıyla denklik ancak tam eşitlikle mümkündür:
\[\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right)\]
3) Periyodikliğin ispatı. \(a \equiv b \pmod p\) olsun. Her iki tarafın \(\tfrac{p-1}{2}\). kuvvetini alırsak:
\[a^{(p-1)/2} \equiv b^{(p-1)/2} \pmod p\]
Euler kriteri gereği bu kuvvetler Legendre sembollerine denktir:
\[\left( \frac{a}{p} \right) \equiv \left( \frac{b}{p} \right) \pmod p\]
İkinci ispattaki mantıkla, yalnızca \(\pm 1\) olabilen bu sembollerin modülo \(p > 2\)’de denk olması birbirlerine eşit olduklarını kanıtlar.
4) Özel değerlerin ispatı.
- \(a = 1\) için Euler kriterini uygularsak: \[\left( \frac{1}{p} \right) \equiv 1^{(p-1)/2} = 1 \pmod p \implies \left( \frac{1}{p} \right) = 1\]
- Çarpımsallık özelliğini kullanarak: \[\left( \frac{a^2}{p} \right) = \left( \frac{a}{p} \right) \cdot \left( \frac{a}{p} \right) = (\pm 1)^2 = 1\]
- \(a = -1\) için Euler kriterini uygularsak, sayılar teorisinde ve soyut cebirde çok sık karşılaşacağımız meşhur özdeşliği elde ederiz: \[\left( \frac{-1}{p} \right) \equiv (-1)^{(p-1)/2} \pmod p\] Değerler \(\pm 1\) aralığında olduğu için eşitlik kesindir.
\(\blacksquare\)
Dördüncü özellik pratikte şu anlama gelir: \(-1\) sayısı, ancak ve ancak \(p \equiv 1 \pmod 4\) olduğunda modülo \(p\)’de bir kuadratik rezidüdür.
Çünkü \(p \equiv 1 \pmod 4\) iken \(\tfrac{p-1}{2}\) çifttir ve sembol \(+1\) olur; \(p \equiv 3 \pmod 4\) iken \(\tfrac{p-1}{2}\) tektir ve sembol \(-1\) olur.
4.3 3. İnteraktif Legendre Hesaplayıcısı
Legendre sembolünün tanımını ve özelliklerini öğrendikten sonra, farklı \(a\) ve \(p\) değerleri için sembolün nasıl davrandığını gözlemlemek faydalı olacaktır. Aşağıdaki araç, herhangi bir \(a\) ve tek asal \(p\) değeri için \(\left( \frac{a}{p} \right)\) değerini Euler kriteriyle hesaplar.