$q=1+k256$ ve q asal sayı olmak şartı ile $q|2^{k}+1$ mümkün müdür.

Question

Arkadaşlar,

$q=1+k256$ ve q asal sayı olmak şartı ile $q|2^{k}+1$ mümkün müdür. Pek bir ilerleme sağlayamadık. Yardım ederseniz sevinirim.

Answer 1

Euler teoremi kullanirsan 

$(2^k)^{Q(x)}$denktir 1mod(q)$

$Q(x)= q-1=k256+1-1=k.256$

$Ebob(256k,256k+1)=1$        $2^{Q(x)}$  =$2^{8k}$ denktirr  $1mod(p)$      $2^{q-1}$ denk1(modp)   o halde   modq  da kAlan 2dir tam bÖlünmüyor diye düünüyorm

Comments

Özür diliyorum şimdiden,

Cevabınızın ilk satırını anladım, $(2^{k})^{q-1}$ denktir 1 mod q (Fermat nın küçük teoreminden),

$2^{q-1}=2^{8k}$ denktir 1 mod (p) kısmını kavrayamadım.(q yerine p yazmış olabilirmisiniz?)

Eğer kastınız $2^{q-1}=2^{256k}$ denktir 1 mod (q) ise $x=2^{k} $ olmak üzere $x^{256}\equiv1mod(q)$ in çözümü, 1,-1 veya başka bir değer olabilir. Buda $2^k+1 mod q$ yü 0,2 yada başka bir değer yapmaz mı?

Aydınlatırsanız sevinirim. Teşekkürler 

---

Euler teoremi : $ ebob(2,256k+1)=1 $ $256k+1 $ $asalolmak uzere 2^{Q(x)} denk 1(modq) $ise   $2^{256k}denk1 (modq)$  Q(x)=q-1     q asal  olduğu için birde $Q(x^n)=x^n-x^{n-1}$ xasal 

---

$x^{256}$=$1mod(q) $dur $<=> $ ebob(x,q)=1 ise 

---

Bu durumda açıkça $2^{256k}\equiv 1 mod q $ görülmekte. Fakat $2^{k} mod q $ nedir?

Answer 2

$k >=2^8$ icin deger saglanmaz 256dn kucuk degerler icn bakmak  lazm