Question

$7^x\equiv-49\;(\mod 997)$ saglayan $x$ degerini varsa bulunuz.

$997$ asal oldugundan ve $997\nmid7$ oldugundan, Fermat'in Kucuk Teoremi sunu soyler.

$7^{997}\equiv7\;(\mod 997)$  veya $7^{996}\equiv1\;(\mod 997)$. Devaminda birsey getiremedim.

Bu arada cevap $x=500$ dur.

Comments

Wikipedia: https://en.00wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm

Bu algoritmayı kullanan bir site: https://asecuritysite.com/encryption/log_poh?val1=50&val2=11&val3=997

---

$7^{ 996} \equiv 1$. Yani $7^{498} \equiv \pm1$. Bu da bir başlangıç olabilir. 

---

Bir de quadratic reciprocity kullanınca iş çözülür. 

---

Neden $7^{ 996} \equiv 1\implies7^{ 498} \equiv \pm1$, boyle bir kural mi var?

---

$(7^{498})^2\equiv1$ ve $\mathbb{Z}_{997}$ bir cisim ($x^2-1$ in kökleri $\pm1$) olduğundan $7^{498}\equiv\pm1$ olmak zorundadır.

---

Anladim ama notasyon kafa karistiriyor. $7^{ 498} \equiv 1$ veya $7^{ 498} \equiv -1$ olmali, aksi halde her ikisi de saglanir gibi algiladim..

---

İkisi aynı anda sadece mod2de denk olabilir. Standart bir kullanım. Mesela ikinci dereden polinomların kökleri için $\frac{-b\pm\sqrt\Delta}{2a}$ yazmak gibi...

Answer 1

$p$ asal bir sayi olsun. Fermat'in kucuk teoremi geregi $(a,p)=1$ tam sayilari icin $$a^{p-1}\equiv 1 \mod p$$ saglanir. 

$p$ asal oldugundan (Dogan Donmez'in de dedigi gibi) $$x^2\equiv 1 \mod p$$ cozumleri $$x\equiv 1 \mod p \ \ \ \text{ ya da } \ \ \ x \equiv -1 \mod p$$ olur. (Bunun basit sayilar teorisinden ispati mevcut).

Bu da  $(a,p)=1$ tam sayilari icin $$a^{\frac{p-1}{2}}\equiv 1 \mod p \ \ \ \text{ ya da } \ \ \ a^{\frac{p-1}{2}} \equiv -1 \mod p$$ olur.

              _______________________________________

Eger $a$ tam sayisi $\mod p$ altinda bir kare ise $$a^{\frac{p-1}{2}}\equiv 1 \mod p$$ bir kare degilse de $$a^{\frac{p-1}{2}}\equiv -1 \mod p$$  saglanir. Bu ilgi cekici ve bircok yerde karsimiz cikan bir durum. $\mod p$ altinda bir sayinin tam kare olup olmadigini test etmek uzere algoritmalar vardir. Detayli bilgi icin [1]deki ilgili bolume bakabilirsiniz.

Eger sayi $\mod p$ altinda bir sayinin tam kare olup olmamasini $$\left(\frac{a}{p}\right)$$ ile belirtip kare ise $1$ kare degilse $-1$ diyecegiz. Kisacasi $$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right) \mod p$$ saglanir.

             _______________________________________

Bu soru icin kullanacagimiz ve genel konsepte dekullanisli olan bir esitlik var: $p$ ve $q$ tek asallar olmak uzere $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}$$ esitligi saglanir.

Bu aslinda sayilari kucultmek icin kullaniliyor. $\left(\frac{7}{977}\right)$ yerine $\left(\frac{997}{7}\right)=\left(\frac{3}{7}\right)$ degerine bakmak, hatta (cok gerekmese de) $\left(\frac{7}{3}\right)=\left(\frac{1}{3}\right)$ degerine bakmak daha kolaydir. 

Gordugunun gibi $7^{498} \mod 977$ denkliginin $1$ ya da $-1$ degerlerinden hangisini alacagini bulmak icin tek tek kuvvet almak ya da iki tabanli kuvvet algoritmalarina benzer bir algoritma kullanmak durumunda degiliz. Bunun yerine su basit soru cevabi veriyor: $1$ tam sayisi $\mod 3$ altinda tam kare mi? Evet $1^2=1$ zaten. 

Elimide $$\left(\frac{7}{977}\right)=\left(\frac{977}{7}\right)=\left(\frac{3}{7}\right)=-\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1$$ var. Bu da $$7^{498} \equiv -1 \mod 977$$ oldugunu verir.

                  _____________________________________

Peki $7$nin daha kucuk bir (pozitif) kuvveti $\mod 977$ altinda $-1$ olabilir mi?





Ek kaynaklar:
[1] Neal Koblitz, A Course in Number Theory and Cryptography, (web baglantisi)

Comments

Quadratic reciprocity'nin kaç tane kanıtını biliyorsun?

---

Neden mod 3? Ledengre gosterimlerine bakmam lazim.

---

@Ozgur, birkac, cok degil ama. 

@Okkes, `Bu aslinda sayilari kucultmek icin kullaniliyor.'  dedigim paragrafin oncesi ve sonrasinda birkac kere aciklamis oluyorum aslinda. 

---

Burada 246 tane var.

---

247ye bi Ozgur&Sercan mi eklesek :)

Bu arada link icin tesekkurler.