BÖLÜM 3
3 KRİPTOGRAFİDE KULLANILAN ALGORİTMALAR
3.1 Euclidean Algoritması (İki sayının En Büyük
Ortak Bölenini bulmak için)
Girdi: a³b
olmak üzere a ve b-negatif olmayan tamsayılar.
Çıktı: a ve b-nin En Büyük Ortak Böleni.
1)
b¹0
olduğu sürece : r¬a
mod b, a¬b,
b¬r
2)
return (a)
Bu algoritmanın karmaşıklığı O((log n)2)-dir.
3.2 Genişletilmiş Euclidean Algoritması
Girdi: a³b
olmak üzere a ve b-negatif olmayan tamsayılar.
Çıktı: d=gcd(a,b) ve ax+by=d olacak şekilde x ve
y-tamsayıları.
1)
Eğer b=o ise d¬a,
x¬1,y¬0
ve return(d,x,y)
2)
X2¬1,x1¬0,y2¬0,y1¬0
3)
While(b>0) do
3.1) q¬[a/b],
r¬a-qb
,x¬x2-qx1,y¬y2-qy
3.2) a¬b,b¬r,x2¬x1,y2¬y1
ve y1¬y
4)
d¬a,
x¬x2,y¬y2
ve return(d,x,y).
Bu algoritmanın karmaşıklığı O((log n)2)-dir.
3.3 Zn-nin Bir Elemanının Çarpımsal
Tersini Hesaplama Algoritması
Girdi: aÎZn.
Çıktı: a-1 mod n.
1)
Genişletilmiş Euclidean Algoritması yardımıyla d=gcd(a,n) iken
ax+ny=d-yi sağlayan x ve y-tamsayılarını bul.
2)
Eğer d>1 o zaman a-1 mod n yoktur. Aksi halde return(x).
3.4 Zn-de Üslü Hesaplama Yapmak için
Tekrarlı Kare Alma ve Çarpma Algoritması
Girdi: aÎZn
0£k<n
olacak şekilde bir k-tamsayısı ve k=
ki2i
ki2i
Çıktı: ak mod n.
1)
b¬1.
eğer k=0 o zaman return(0)
2)
A¬a.
3)
Eğer k0=1 o zaman b¬a.
4)
For i¬1
to t do
4.1) A¬A2
mod n.
4.2) Eğer ki=1 o zaman b¬Ab
mod n.
5)
return(b)
3.5 Bir p-modülüne Göre Karekök Bulma Algoritması
Girdi: p-asal sayısı ve 1£a£p-1
olacak şekilde a-tamsayısı
Çıktı: a-nın p-modülüne göre iki karekökü
1)
(a/p) Legendre Sembolülü hesapla. Eğer (a/p)=-1 o zaman Print “a-nın p-ye
göre karekökü yok”. Bitir.
2)
(b/p)=-1 olacak şekilde ,1£b£p-1,
rasgele b-tamsayıları seç (b ,p-modülüne göre quadratik non-residue-dir).
3)
Devamlı 2-ile bölerek ,t tek bir tamsayı olmak üzere, p-1=2st
şeklinde yaz.
4)
a-1 mod p-yi Euclidean Algoritmasıyla hesapla.
5)
c¬bt
mod p ve r¬a(t+1)/2
mod p.
6)
For i¬1
to (s-1) do
6.1) dº(r2a-1)2^(s-i-1)
(mod p).
6.2) Eğer dº-1
(mod p) ise o zaman r¬rc
(mod p)
6.3) c¬c2
(mod p)
7)
Return(r,-r)
3.6 pº3
(mod 4) Asal Sayı Modülüne Göre Karekök Bulma Algoritması
Girdi: pº3
olacak şekilde bir p-asalı ve aÎQp.
Çıktı: a-nın p-modülüne göre iki karekökü.
1)
rºa(p+1)/4
(mod p)-yı hesapla.
2)
Return(r,-r)
3.7 pº5
(mod 8) Asal Sayı Modülüne Göre Karekök Bulma Algoritması
Girdi: pº5
olacak şekilde bir p-asalı ve aÎQp.
Çıktı: a-nın p-modülüne göre iki karekökü.
1)
dºa(p-1)/4
(mod p)-yi hesapla.
2)
Eğer d=1 o zaman rº(p+3)/8
(mod p).
3)
Eğer dºp-1
o zaman rº2a(4a)(p-5)/8
(mod p)
4)
Return(r,-r)
3.8 Bir p-asal Sayı Modülüne Göre Karekök Bulma
Girdi: Bir p-asalı ve aÎQp.
Çıktı: a-nın p-modülüne göre iki karekökü.
1)
b2-4a ,p-modülüne göre quadratik non-residue olana kadar
rasgele bÎZp
sayılarını seç .
2)
f=x2-bx+a ÎZp[x]
olsun.
3)
R bir tamsayı olacak şeklide ,rºx(p+1)/2
(mod f)-yi hesapla.
4)
Return(r,-r)
Bu algoritmanın karmaşıklığı O((log p)3)-tür.
3.9 Asal Çarpanları p ve q olan n-Bileşik Sayı
Modülüne Göre Karekök Bulma Algoritması
Girdi: Bir n-bileşik sayısı n-nin asal q ve q
çarpanları ve aÎQn.
Çıktı: a-nın n-modülüne göre dört karekökü.
1)
3.8 algoritması yardımıyla a-nın p-modülüne göre r ve –r kareköklerini
hesapla
2)
3.8 algoritması yardımıyla a-nın q-modülüne göre s ve –s kareköklerini
hesapla.
3)
Genişletilmiş Euclidean Algoritması yardımıyla cp+dq=1 olacak şekilde c
ve d-tamsayılarını hesapla.
4)
x¬(rdp+scp)
(mod n) ve y¬(rdp-scp)
(mod n).
5)
Return(x,-x,y,-y).
Bu algoritmanın karmaşıklığı O((log p)3)-tür
burada da bilgi var: http://www.wardom.org/kok-alma-denklemini-bilen-var-mi-ya-da-oyle-birsey-var-mi-t52445.html
Hiç yorum yok:
Yorum Gönder