Question

Ayrık logaritma problemi $a, b, n$ tamsayıları verildiğinde $a^x=b$ mod $n$ denklemini çözmek olarak ifade edilirse, problemin çözümünü olabildiğince zorlaştırmak için $a,b,n$ sayılarını nasıl seçmek gerekir?

Comments

En son bildiklerim: $n=2p+1$ olacak sekilde $n$ ve $p$ asal. Sebebi carpim grubunun asiri derecede  indirgenmesini engellemek. Bir de $x$ ile $b$ arasinda bir Legendre sembolu iliskisi vardi da, ondan net emin degilim, arastirmalarini takip etmiyorum. ama galiba su an icin $n$ kosulu boyle. Belki $p$'nin de nasil olmasi gerektigi hakkinda da bir bilgi vardir...

Answer 1

Öncelikli olarak $n$ sayısının asal sayı seçilmesi gerekir. Çünkü asal olmayan herhangi bir $n$ sayısı için, $n$ sayısını asal çarpanlarına ayırıp, ardından Çin Kalan Teoremi'ni kullanarak problemi kolayca çözebiliriz. Ondan dolayı ilk şart, $n$ sayısının asal sayı olarak seçilmesi.

Fermat'nın Küçük Teoremi'nden (Fermat's Little Theorem) biz biliyoruz ki, herhangi bir $a\in\mathbb{Z}^*_p$ sayısı için $a^{p-1}\equiv 1\mbox{ mod }p$ denkliği sağlanır. Buradan, bölme algoritmasından, herhangi bir $s$ tamsayısı için, $0\leq r<p-1$ eşitsizliğini sağlayan biricik $q$ ve $r$ sayıları için $s=q(p-1)+r$ eşitliğini yazabiliriz. Bu da bize

$a^s\mbox{ mod }p=a^{q(p-1)+r}\mbox{ mod }p=(a^{p-1})^qa^r\mbox{ mod }p=a^r\mbox{ mod }p$ eşitliğini verir. Yani, $r\equiv s\mbox{ mod } p-1$ olduğundan, eğer Ayrık Logaritma Problemi'ni $\mbox{ mod }p$ için düşünürsek, $x$ sayısını her zaman $x\in\mathbb{Z}_{p-1}$ şeklinde alabiliriz.

Buraya kadar yazdıklarımızı toparlarsak eğer, problemimiz şu hali almış oldu aslında: 

Herhangi bir $x\in\mathbb{Z}_{p-1}$ sayısı, verilen $p$ tek asal sayısı (2 çok küçük olduğundan almıyoruz) ve $a,b\in\mathbb{Z}^*_p$ için

$b\equiv a^x\mbox{ mod }p$ denkliğini sağlayan $x$ sayısı nedir?

Yukarıda dedik ki, $n$ sayısı asal olarak seçilmeli, ve seçtik de. Ancak, sadece asal sayı olarak seçmemiz de yetmiyor. Problemi yeteri kadar zorlaştırmak için, $p$ asal sayısının yeterince büyük bir asal sayı olması gereklidir. Peki bu $p$ asal sayısı ne kadar büyük olmalıdır? 

Bir örnek ele alalım:

$p=23423429$ ($p$ asal) ve $\alpha=2$ olarak alalım ve şu probleme bakalım:

$b=a^x\equiv 19556038\mbox{ mod } p$.

Burada $x$'i bulmak zor mudur? diye sorduğumuz zaman, aslında $x$ sayısını bulmanın nispeten kolay olduğunu görürüz. Çünkü, buradaki $p$ asal sayısına baktığımız zaman, yaklaşık olarak $p\approx2^{25}$ olduğunu görürüz (ki işlemleri bilgisayar ortamında yaptığımız için $2^{25}$ sayısı çok küçük bir sayıdır). $x$ sayısı için, $x=0$, $x=1\cdots$, diye $x$'in doğru değerini bulana kadar devam ederiz ki, $x$ için de test etmek için yaklaşık olarak $p$ ile aynı sayıda olasılık vardır. Bugün, $p$ asal sayısı için tavsiye edilen, en az $768$-bit olması gerektiğidir, yani $p>2^{767}$ seçilmelidir.

Problemin zor olması için, 2.şart olarak $p-1$ sayısının en az bir tane büyük bir asal böleni olması gerektiğidir. Nedenini bir örnekle görelim:

$p=884605080699835339776196609$ asal sayısı için, $\mbox{ mod }p$ üzerinde alınan Ayrık Logaritma Problemi zor mudur? diye sorduğumuz zaman, ilk dikkatimizi çekmesi gereken şey, bu $p$ asal sayısının yukarıda tavsiye ettiğimiz $768$-bit boyutundan daha az olmasına rağmen, $x$ sayısının bütün olası değerlerini test etmenin o kadar da kolay olmaması. Ancak, problemi çözmenin başka kolay bir yolu var ki, bunun nedeni de $p-1$ sayısının küçük asal bölenlere sahip olması. Baktığımız zaman, $p-1=2^{34}3^{12}7^{13}$ olduğunu görüyoruz. Pohlig ve Hellman'ın vermiş olduğu ispata bakarsak eğer, (Pohlig-Hellman algorithm olarak geçer) http://cacr.uwaterloo.ca/hac/about/chap3.pdf (sayfa 107 3.6.4'ten itibaren sayfa 109 3.67'ye kadar) $p-1$ sayısı sadece küçük asal çarpanlara sahipse, ayrık logaritma problemini hesaplamak kolaydır demişlerdir. Ki yukarıdaki örnekte, ilk olarak $x\mbox{ mod }2$'yi buluruz. Daha sonra, $x\mbox{ mod }2^2$'ni hesaplarız ve bu şekilde devam ederek $x\mbox{ mod }2^{34}$'ü elde ederiz. Yine aynı şekilde, $x\mbox{ mod }3^{12}$ ve $x\mbox{ mod }7^{13}$ sayılarını da hesapladıktan sonra, Çin Kalan Teoremi'ni kullanarak $x\mbox{ mod }p-1$ i hesaplarız. Bu metodun zaman karmaşıklığı (time complexity)(veya işletim süresi), $p-1$ sayısının en büyük asal bölenine bağlıdır. Ondan dolayı da, $p$ asal sayısı için, $p-1$ sayısının en az 1 tane büyük asal böleni olması gerektiği tavsiye edilir. Buradan da, $q$ asal sayısı için, $p$ asal sayısını $p=2q+1$ şeklinde üretirsek eğer, $p-1$ sayısı en az bir büyük asal bölene sahiptir diyebiliriz.

Son şart olarak da, $a^m\equiv 1\mbox{ mod }p$ denkliğini sağlayan en küçük $m$ tamsayı değerinin, büyük olması gerekmektedir. Nedenini bir örnek üzerinde görelim yine:

$p$ sayısı, $p=589640540809904183368339807$ asalı olsun. Burada, $p-1$ sayısı, $q=98273423468317363894723301$ asalı olmak üzere $p-1=2\cdot3\cdot q$ dur. Yani $p-1$ sayısı yukarıda belirttiğimiz 2.şartı sağlar. $a$ sayısı, $a=151369338077029664651937484$ ve $b$ sayısı, $b=438271202732874518716402322\mbox{ mod }p$ olsun. Yine aynı soruyu soralım:

Yukarıda verilenler için, $b=a^x\mbox{ mod }p$ denkliğini sağlayan $x$ değerini bulmak zor mudur?

Aslında kolaydır. Nedeni ise, $a^3\equiv 1\mbox{ mod }p$ denkliğinin sağlanmasıdır. Bundan dolayı, $a^x\equiv a^{x\mbox{ mod }3}\mbox{ mod }p$ denkliği sağlanır ve $b$ değeri, denklemi sağlayan yalnızca 3 olasılıktan biridir burada. Yani kısaca, $a$ sayısının mertebesi ne kadar büyükse, problemi çözmek bir o kadar zorlaşır burada. (Ve biliyoruz ki, $a$ ilkel (primitive) sayısı için, mertebesi en fazla $p-1$ olabilir.)

Comments

Bu kadar güzel anlatılır. Teşekkürler.

---

Ben teşekkür ederim, böyle güzel bir site kurup, bizlere böyle olanaklar sağladığınız için.