A
B
C
Ç
D
E
F
G
Ğ
H
I
İ
J
K
L
M
N
O
P
R
S
Ş
T
U
Ü
V
Y
Z
Q
W
X
+ Ekle
Asallık Testi

Asallık Testi

  Bir sayının asal olup olmadığını anlamanın bir kaç güzel ve basit yolu var.

Asal Sayı Testi

I]  P asal ise, √P den küçük hiçbir asal sayı P ile tam bölünmez.

  Böylece bir sayının asal olup olmadığını anlamak için karekökünden küçük asal sayılara bölünüp bölünmediğine bakmak yeterlidir. Çünkü eğer asal değil ise asal çarpanlarından biri mutlaka karekökünden küçüktür.

II]  P asal ise P sayısı (P-1)!+1 sayısını tam böler.

    Örneğin 5 için ,(5-1)!+1=25 ve 25/5=5   ,  6 için (6-1)!+1=121 ve 121≡1 (mod6), 1 kalanını verir.

III]  P asal ise,  A(P-1) -1 sayısı P ile kalansız bölünür. Burada A sayısı P ile tam bölünmeyen bir doğal sayıdır.

    Örneğin 2 (4) -1 =15  ve  15 /5 = 3 ,  6 4 -1 =1295

 

2.1 Asal Sayılar ve Özellikleri

2.1.1 Tanım: Eğer aşağıdaki koşullar sağlanırsa; negatif olmayan bir d-tamsayısı a ve

b-tamsayılarının en büyük ortak bölenidir ve d=gcd(a,b) ile gösterilir.

  • d-sayısı a ve b-nin bir böleni; ve
  • eğer c\a ve c\b ise o zaman c\d olmalıdır.

Yukarıda ki tanıma denk olarak ; gcd(a,b)-pozitif tamsayısı hem a-yı hem de b-yi bölen en büyük tamsayıdır. Burada gcd(0,0)=0 kabul edilmiştir.

 

2.1.2 Tanım: Eğer aşağıdaki koşullar sağlanırsa;negatif olmayan bir d-tamsayısı, a ve               b-tamsayılarının en küçük ortak katıdır ve d=lcm(a,b) ile gösterilir.

  • a\d b\d ;ve
  • eğer a\c b\c ise o zaman d\c olmalıdır.

Yukarıda ki tanıma denk olarak; lcm(a,b)-negatif olmayan tamsayısı hem a-ya hem de                b-ye bölünebilen en küçük tamsayıdır.

 

2.1.3 Tanım: Eğer a ve b-pozitif tamsayılar ise  o zaman lcm(a,b)=(a*b)/gcd(a,b)-dir.

 

2.1.4 Tanım: Eğer gcd(a,b)=1 ise o zaman a ve b-tamsayılarına aralarında asal (coprime) denir.

 

2.1.5 Tanım: p³2 tamsayısına asal sayı (prime) denir; ancak ve ancak p-tamsayısının bölenleri yalnız 1 ve kendisi ise. Diğer durumda p-tamsayısına bileşik sayı (composite)  denir.

 

2.1.6 Asal Sayı Teoremi:  p(x) , x-e eşit ve x-ten küçük asal sayıların sayısını göstersin. O zaman                p(x)/(x / ln x)1-dir. Bunun anlamı x-in çok büyük değerleri için p(x)-in x/(ln x)-değerine yaklaştığıdır. Örneğin x=1010 için p(x)=455.052.511 dir.  [x/ (lnx)]=434.294.481 olmaktadır.

2.1.7 Önerme: x³17 için p (x)>  ve x>1 için ise p (x)<1,25506* -dir.

 

2.1.8 Aritmetiğin Temel Teoremi: n³2 olmak üzere her n-tamsayısı farklı asal sayıların çarpımı şeklinde tek türlü yazılır;  n=p1e1p2 e2…pk ek , burada pi-ler farklı asallar ve ei-ler ise pozitif  tamsayılardır.

 

2.1.9 Tanım: n³1 için j(n) , [1,n] aralığında n-ile aralarında asal olan sayıların sayısını göstermektedir. j-fonksiyonu Euler Fi Fonksiyonu (Euler Totient Function) olarak adlandırılır.

 

2.1.10 Euler Fonksiyonunun Özellikleri:

6.            Eğer p-asal ise j(p)=p-1

6.            Euler Fi Fonksiyonu çarpımsaldır; yani eğer gcd(m,n)=1 ise o zaman j(m*n)=j(m)*j(n)-dir.

iii)                 pi-ler farklı asallar olmak üzere ,                                                                                                           n=p1e1p2 e2…pk ek  ise ; j(n=n(1-)(1-)…(1-) dır.

 

2.1.11 Tanım: p ve q farklı asallar ve qº3 (mod 4) pº3 (mod 4) olmak üzere n=pq bileşik sayısına Blum Sayısı denir.

 

2.1.12 Önerme: n=pq bir Blum Sayı ve aÎQn olsun. O zaman a-nın, tam olarak dört karekökü vardır ve bunlardan bir tanesi Qn-nin elemanıdır.

 

2.1.13 Tanım: n=pq bir Blum Sayı ve aÎQn olsun. A-nın Qn-deki kareköküne esas karekök denir.

 

2.1.14 Önerme: Eğer n=pq bir Blum Sayı ise o zaman f:Qn®Qn fonksiyonu                        f(x)=x2 (mod n) şeklinde tanımlıdır ve bir permütasyondur. F-nin ters  fonksiyonu                    f-1(x)=x((p-1)(q-1)+4)/8 (mod n) şeklinde bulunur.                                                                                                                                                                 

2.1.15 Asallık Testleri

            Asal sayıları bileşik sayılardan ayırt etmek , aritmetiğin en temel ve en önemli konularından biri olmuştur. Bu konu günümüzde hala geçerliliğini korumaktadır.

            Asallık tanımından yola çıkarsak  bir n-tamsayısının asal olması için 2 ile  arasında hiç böleni olmaması gerekir. Bu yöntemi küçük sayılar için uygulamak mümkün olmaktadır. 100 basamaklı bir tamsayının bu yöntemle asal olup olmadığını ölçmek pratik değildir.

 

            Bunu bir örnekle açıklayalım: 101 basamaklı ilk sayı olan 10100-ün asal olup olmadığını bu yöntemle hesaplarken 2 ile  arasındaki her sayıya bölmek gerekecektir. Her bölme işlemi 1 milisecond(ms) alındığında bu işlemler 1050-1 ms sürecekir. Bu da işlemlerin yaklaşık 1,9*1041 yıl sürmesi demektir.

            Büyük sayıların asal olup olmadıklarını anlamak için daha gelişmiş asallık testleri gerekmektedir. Asallık testlerini iki ana gruba ayırabiliriz.

  • Kesin (deterministik) Asallık Testleri
  • Olası (Probabilistic) Asallık Testleri

 

2.1.15.1 Kesin Asallık Testleri

            Bu tür asallık testleriyle kesin olarak bir sayının asal olup olmadığını belirlemek mümkündür. Şu an kullanımda olan en geçerli yöntemler aşağıda belirtilmiştir.

  1. Cyclotomic Ring Test
  2. Elliptic Curve Test

            Bu yöntemler o kadar karmaşıktır ki ,uygulamada bir hata yapma olasılığı ,olası asallık testinde hata yapma olasılığından daha fazladır. Çarpanlara ayırmaya dayalı yöntemle  geliştirilmekle birlikte bu konuda henüz bir standarttan bahsetmek mümkün değildir.

            Mersenne Asallarının bulmak için tasarlanan ve kullanılan Lucas-Lehmer testide deterministik bir asallık testidir ve mersenne sayılarını bulmada çok iyi sonuçlar vermektedir.

 

2.1.15.2 Olası Asallık Testleri

            Asallık  testi bir sayının asal olup olmadığını kanıtlama sürecidir. Olası asallık testleri ise bir sayının yüksek olasılıkla asal olduğunu kanıtlama sürecidir.

            Olası asallık testlerinde , asal sayı üretmek için ilk önce n-bitlik bir rastsal sayı üretilir ve asallık testine tabi tutularak istenildiği kadar küçültülen bir hata payı ile sayının asal olup olmadığı belirlenir; asal olanlar seçilir ve kullanılır. Kesin yöntemlere göre daha hızlı olduğu gerçekte bir sayının asal olup olmadığı ufak hata payları ile kanıtlayabildiği için Olası Asallık Testlerinin kullanılması önerilmektedir. 2-100-den daha küçük bir hata payı ile bir sayının asal olduğu belirlenir. Asal sayı testlerini gerçekleştirirken dikkat edilmesi gereken hususlar şunlardır.                                    

 

1)      Çift sayıları test etmeye gerek yoktur.

2)      Asallığı test edilen sayıların ;3,5,7,11,... gibi küçük asal sayılara bölünüp bölünmediği test edilerek bir çok sayı elenebilir.

Örneğin 23 sayısına kadar olan sayılar alınırsa asal sayı olmayanların en azından 2/3-ü elenir ve üç kat daha hızlı sonuca ulaşılır.

            Dikkat etmemiz gereken temel kriter ,hata oranının 2-100  -den daha büyük olmaması gerektiğidir. Aşağıda bazı Olası Asalık Testlerinin adları yer almaktadır.

  • Fermat Testi
  • Slovay-Strassen Testi
  • Lehmann Testi
  • Miller-Rabin Testi
  • Frobenios Testi
  • Bileşik Testler

 

2.1.15.2.1 Fermat Testi

            Fermat Teoremine göre herhangi bir n-sayısının asal olması için [1,n-1] aralığından taban olarak alınan herhangi bir a-sayısı ile;

 

                                                            an-1º1 (mod n)      

 

eşitliğini sağlamak gerekmektedir.

 

 

 

 

2.1.15.2.2 Lehmann Testi

            n-sayısının asal olup olmadığını test etmek için rasgele seçilen a-sayılarıyla ,b-değeri;

 

                                                            bºa(n-1)/2 (mod n)   

 

formülü ile bulunur. Eğer b-değerleri 1 veya –1 ise ,fakat yalnız 1 veya yalnız –1 değilse, n asal olarak kabul edilir.

                               

2.1.15.2.3 Slovay-Strassen Testi

            Açık-Anahtar Kriptografisinde kullanılmış ilk testtir. Kendisinden daha hızlı ve en az onun kadar doğru olan Miller-Rabin ‘nin kullanılması önerilmektedir.

            Slovay-Strassen Algoritmasında n-sayısının asallığını bulmak için Jacobi Semboli kullanılmaktadır. Jacobi Sembolü n asal ise Legendre Sembolüne eşit olmaktadır.  Algoritmanın aşamaları aşağıdaki gibidir.

1)      n-den daha küçük rasgele a-sayısı seçilir.

2)      Eğer gcd(a,n)¹1 ise o zaman n asal değildir ve testi geçemez.

3)      jºa(n-1)/2 (mod n) hesaplanır.

4)      J(a,n) hesaplanır.

5)      Eğer j¹J(a,n) ise n kesin olarak asal değildir ve testi geçemez.

6)      Eğer j=J(a,n) ise n-nin asal olma olasılığı %50 den fazla olamaz.

 

2.1.15.2.4 Miller-Rabin Testi

         Miller-Rabin Testi güçlü asallık testi olarak bilinir. Miller-Rabin Testinde , n-sayısının asal olup olmadığını tets etmek için önce ;

 

                                                       n-1=2sr

 

formülünü sağlayan s ve r-değerleri hesaplanır. [1,n-1] aralığında taban olarak kullanılacak bir a-değeri seçilir. Arº1 (mod n) ve a(2^j) rº1 (mod n)  (0£j£s-1) denklikleri sağlanıyorsa n-sayısının a-tabanına göre güçlü asal olduğunu kabul edilir.

 

 

2.1.15.2.5 Frobenius Testi

            Frobenius sözde asalı Sonlu Alan Kuramına dayanmaktadır. Ayrıca bu kurama dayanan Frobenius Testinin diğer testlerin genelleştirilmesi ve güçlendirilmesi ile oluştuğu belirtilmektedir. Frobenius Testi ile bir bileşik sayıyı asal olarak belirleme hata oranının 1/7710 olduğu ölçülmüştür. Frobenius Testinin Miller-Rabin Testinden üç kat daha yavaş çalıştığı ama 3 aşamalı Miller-Rabin Testinin hata oranının en fazla (1/4)3=1/64 olduğu belirtilmştir. Bu da Frobenius Testinin aynı zaman aralığında Miller-Rabin Testinden daha az hata oranı ile çalıştığını göstermektedir.

 

 

2.1.15.2.6 Bileşik Testler

            Miller-Rabin Testini uyguladıktan sonra Lucas Testi ve t-defa Frobenius Testi  uygulanarak asallı testinin daha iyi sonuçlar vermesi sağlanabilir. Miller-Rabin Testinden sonra t-defa Frobenius Testi kullanıldığında 512-bitlik bir asal sayının hatalı olma

(bileşik sayı olma) olasılığı 1,5*10-17*(1/1770)t-den az olmaktadır.

            Miler-Rabin Testinin ,Lucas testi ile birlikte kullanılması önerilmektedir. Şu ana kadar bu iki testi birlikte geçen bir bieşik sayı bulunamamıştır.  Bu iki test birlikte kullanıldığında ulaşılacak hata olasılığının matematiksel olarak hesaplayan bir formül bulunmamaktadır.

 

2.2 Quadratik Residue&Esas Karakök

            P bir tek asal sayı ve u ise p ile bölünemeyen bir tamsayı olsun. O zaman, eğer x2=u (mod n) denkleminin sadece bir çözümü varsa  u’ya quadratik residue denir. Diğer durumlarda ise u quadratik non-residue olarak adlandırılır.QR tüm quadratik residue ve QNR ise tüm quadratik non-residuelerin kümesini göstersin.Burada p asalı için toplam (p-1)/2 tane quadratik residue

ve aynı sayıda quadratik non-residue vardır. Fermat Teoreminden ve yukarıdaki verilen bilgilerden aşağıdaki denklemi çıkarabiliriz.

 

X(p-1)/2-1=                (1)

Eğer u,  p modülüne göre quadratik residue ise o zaman u’nun tam olarak iki tane karakökü vardır ve bu kareköklerden biri 0 ve (p-1)/2 aralığında diğeri ise (p-1)/2 ve                (p-1) aralığındadır.

Bu kareköklerden biri aynı zamanda u-modülüne göre de quadratik residue’dir ve esas karekök olarak adlandırılır. Eğer n bir bileşik sayı ise n modülüne göre quadratik residue olan u aynı zamanda n’nin tüm asal çarpan modülüne göre de quadratik residue olmak zorundadır. Rabin kriptosistemi pve q asal olmak üzere n=pq sayısını kullanılır. Bu çerçevede o zaman n modülüne göre tam olarak (p-1))q-1)/4 tane quadratik residue vardır. Bir quadratik residue’nin normal olarak 4 tane farklı karekökü vardır. Yinede gerçek quadratik residue’lerin bölenleri ya p yada q dur. Böyle quadratik residue’lerin sadece iki karekökleri vardır. Aşağıda basit bir örnek olarak n=2*7 nin quadratik residue’leri verilmiştir.

 

                                      Z21=2*7

Quadratik residue

Karekökler

Quadratik residue

Karakökler

1

4

1,8,13,20

2,5,16,9

15

16

6,15

4,10,1117

7

7,14

18

9,12

9

3,18

 

 

              Tablo1: Z21 deki Quadratik Residue’ler

            Tablo 1 de sadece iki karekökü bulunan çok sayıda quadratik residue’ler görünmektedir (7,9,15,18 gibi). P ve q-asal olmak üzere n=pq da ise sadece iki karekökü bulunan  ((p-1)/2)-1=O(p+q)  tane quadratik residue vardır. Bunun anlamı ise quadratik residue’lerin ihmal edilebilir sayıda olanının iki karekökü vardır. Böyle bir durumla karşılaşma ihtimali azdır ve ihmal edilebilir. Böylelikle Rabin Kriptosisteminde büyük asallar kullanıldığı zaman  her quadratik residue tam olarak iki kareköke sahiptir.

 

2.3 Legendre ve Jacobi Sembolleri

            Legendre sembolü bir u sayısının bir p-asalına göre quadratik residue olması durumunu göstermek için kullanılır. Jacobi semboli ise bir u sayısının bir n bileşik sayısına göre quadratik residue olması durumunu göstermek için kullanılır.

 

 

 

 

 

2.3.1 Legendre sembolü

            Legendre sembolü u, herhangi bir tamsayı ve p bir tek asal sayı olduğu zaman kullanılır ve L(u,p) şeklinde gösterilir.

 

·        L(u,p)=0    ;                         eğer p böler u ise

·        J(u,n)=L(u,n) ;                     eğer a, p modülüne göre quadratik residue ise

·        J(u,n)=J(u,p1)*...*J(u,pn);    eğer n=p1*...*pn  ise

 

2.3.2 Jacobi Semboli

            Jacobi sembolü, Legendre sembolünün bileşik sayılar için türetilmiş şeklidir.  Herhangi bir u tamsayısı ve herhangi bir n tamsayısı, öyleki n=2k+1 kÎN, için ;

 

·        J(0,n)=0 ;

·        J(u,n)=L(u,n) ;                 eğer n bir asal sayı ise

·        J(u,n)=j(u,p1)*...J(u,pn) ; eğer  n=p1*...*pn

 

2.4 Çin Kalan Teoremi

Bu teorem farklı modül kullanan denklemleri birleştirmek için kullanılır.

 

Teorem:  x≡y (mod p)

                 x≡y (mod q)  p ve q aal sayı olmak uzere;

x≡y (mod p*q)

 

İspat:       x≡y (mod p)

x=y+kp ,kÎN      

x-y=kp

p böler (x-y) 

 

                 x≡y (mod q)

x=y+mq ,mÎN      

x-y=mq  ,mÎN

q böler (x-y) 

p ve q-asal olduklarında p*q böler (x-y).

x-y=n(pq) , nÎN

x=y+kp ,kÎN      

x-y=kp

x≡y (mod  pq)

Böylece  ispat tamamlanmıştır.

 

 

2.5 Fermat Teoremi

Bu teorem modüler aritmetikle üslü sayılar arasında ilişki kuran şaşırtıcı bir teoremdir.

 

Teorem :  Eğer p bir asal sayı ve x0 (mod p) ise o zaman xp-1º1 (mod p) dir.

 

İspat  :  p asal sayı olmak üzere Q ={1,2,…,p-1} kümesini ele alalım. P-asal sayı    

             olduğundan Q’nun tüm elemanları p  ile aralarında asal olacaktır.

=>Q , p ile aralarında asal olan ve p-modülüne göre kalan sınıfını oluşturan 

      tüm  sayılarından oluşur.

 

             Şimdi ise Q’nun her elemanını (mod p) de x ile çarparak elde edilen 

             elemanlardan  oluşan  U kümesini ele alalım. Hem x hemde  Q’nun her elemanı

             p ile aralarında asal olduğundan;

U’nun her elemanı p ile aralarında asaldır.

             İ≠j  iken Xqi≡Xqj (mod p) olduğunu kabul edelim. X≠0 olduğundan kısalma

            özelliği   kullanılarak Qi≡Qj (mod p) bulunur. Burada Q’nun her elemanı farklı

            olduğundan  çelişki oluşur. U’nun elemalarını aynı aldığımızdan oluşmaktadır.

             =>O zaman U’nun  her elemanı farklıdır.

           =>Yani U ,Q’nun bir permütasyonudur.

            

 

             =>U1*U2*…*Up-1≡ Q1*Q2*…*Qp-1  (mod p)

             =>Xq1*Xq2*…*Xqp-1≡ Q1*Q2*…*Qp-1  (mod p)

             ve  Qi’lerin  kısaltılmasıyla ,iÎ[1,p-1], xp-1≡1 (mod p) bulunur. Buda teoremin           

            ispatıdır.

           

2.6 RSA’nın Doğrulanması

Burada RSA kriptosisteminde şifreleme ve deşifreleme için kullanılan teoremden

bahsedilmiştir.

 

Teorem:  (d,e,n) RSA kriptosistemi üyeleri,p ve q farklı asal sayılar,de≡1 (mod j(n)), n=pq ve 0<m<min{p,q} olmak üzere;

 

                c≡me (mod n)

                M≡cd (mod n)

M≡m (mod n)  dir. 

 

İspat:  M≡cd≡(me) d≡med≡mkj(n)+1≡mk(p-1)(q-1)+1 (mod n) ,kÎN, olur.

M≡m*mk(p-1)(q-1) ≡m*(m(p-1)) k(q-1) (mod n) olur. (*)

Burada x≡(m(p-1)) k(q-1) (mod n) diyelim.   

P ve q asal olduğundan Fermat Teoremi gereği hem m(p-1)≡1 (mod p) hemde

m(q-1)≡1 (mod q) olur. Dolayısıyla (m(p-1)) k(q-1)≡1 (mod p) ve                                      (m(p-1)) k(q-1)≡1 (mod q) olur. Çin Kalan Teoremi gereği (m(p-1)) k(q-1)≡1 (mod p*q) bunu (*) da yerine koyarak

M≡m*1≡m (mod n) elde edilir. Buda teoremin ispatıdır. 

 

2.7 Modüler Aritmetik ve Cebir

 

2.7.1 Tanım: a ve b-tamsayılar ve n-pozitif bir tamsayı olmak üzere eğer n böler (a-b) ise;

 n-modülüne göre a denktir (congruent) b denir ve  aºb (mod n) şeklinde yazılır. N-sayısına işlemin modülü denir.

 

2.7.2 Tanım: Zn-kümesi n-modülüne göre en küçük pozitif kalanların kümesini gösterir.

Yani Zn={0,1,...,n-1}-dir.

 

2.7.3 Tanım: aÎZn olsun. A-nın n-modülüne göre tersi, axº1 (mod n) olacak şekilde, xÎZn-dir. Eğer böyle bir x-sayısı varsa bu tektir ve a tersinirdir denir. A-1=x şeklinde gösterilir.

 

2.7.4  Önerme: aÎZn olsun. A-tersinirdir ancak ve ancak gcd(a,n)=1 ise.

 

2.7.5  Tanım: Zn-nin çarpım grubu Zn* ile gösterilir ve Zn*={aÎZn | gcd(a,n)=1}-dir. Eğer n-sayısı asal ise o zaman Zn*={ a | 1£a£n-1 }.

 

2.7.6  Tanım: Zn*-nin derecesi , Zn*-nin eleman sayısı olarak tanımlıdır ve | Zn*|-ile gösterilir. Euler Fi Fonksiyonu tanımından | Zn*|=j(n)-dir.

 

2.7.7  Tanım: aΠZn* olsun. A-nın derecesi ,ord(a)-ile gösterilir,atº1 (mod n) olacak şekildeki en küçük pozitif t-tamsayısıdır.

 

2.7.8  Tanım:  Zn* olsun. Eğer a-nın dececesi j(n) ise o zaman a-ya Zn*-nin üreticisi denir. Eğer Zn*-nin bir üreticisi varsa , Zn* döner (cyclic) grup adını alır. Eğer n bir asal sayı ise Zn*-nin bir üreticisi vardır dolayısıyla döner gruptur.

 

2.7.9  Önerme: n, iki farklı p ve q-asallarının çarpımı olsun. O zaman aΠZn* bir quadratik residuedir ancak ve ancak aÎQp ve aÎQq ise.

 

2.7.10    anım: aÎQn olsun. Eğer x2ºa (mod n) olacak şekilde bir xΠZn* varsa o zaman x-e ,a-nın n-modülüne göre karekökü denir.

 

2.7.11    Önerme:

i)           Eğer  p-bir asal sayı ve aÎQp ise o zaman a-nın tam olarak iki karekökü vardır.

ii) n=p1e1p2 e1...pk ek , pi-ler farklı asal sayılar ve 0 £ei olsun. O zaman ;

1)      Eğer aÎQn ise a-nın tam olarak  2k farklı karekökü vardır.

 

 

 

 

 

  Ad Soyad
  Yorum