Bir küme, herhangi iki elemandan eşsiz bir üçüncü elemanı türetmek için bir ikili işleme (binary operation) sahip bir takım küme elemanlarıdır. Eğer küme işlemini # işareti ile gösterecek olursak, yukarıda söylenen herhangi bir küme elemanı olan a ve b için, a#b tanımlıdır ve hatta bir kümenin elemanıdır. Ayrıca kümeler çağrışımsaldır yani a, b ve c kümenin herhangi birer elemanı olsun, a#(b#c) = (a#b)#c'dir. Kümenin herhangi bir elemanı olan a için bir adet birim (etkisiz) eleman (e) olmalıdır, a#e = e#a = a. Son olarak herhangi bir eleman olan a'nın bir tane tersi (a') olmalıdır, a#a' = a'#a = e.
Kümenin tüm elemanları olabilen a ve b için eğer a#b = b#a ise bu küme değişme özelliğine sahiptir. Aksi halde değişme özelliği yoktur. Şu noktaya dikkat çekelim, değişme özelliğine sahip olmayan bir küme için bazı durumlarda a#b = b#a eşitliği doğru olabilir - örneğin a ya da b birim eleman olursa.
Sınırlı sayıda eleman içeren kümeye sınırlı küme, aski durumda sınırsızdır denir.
Örnekler:
1. Tam sayılar (tüm sayılar, 0 ve negatif sayılar) adi toplama işlemiyle bir küme oluştursunlar. Birim eleman 0 olur ve a'nın tersi -a olur. Bu sınırsız ve değişebilen bir kümedir.
2. Pozitif rasyonel sayılar (tüm pozitif tam sayılar da dahil olmak üzere tüm pozitif kesirler) adi çarpma işlem olarak bir küme oluştursun. Birim eleman 1 sayısı ve r'nin tersi 1/r = r^-1. Bu da diğer bir sınırsız değişebilen kümedir.
3. Tam sayıların n ile modu, n > 0 herhangi bir tam sayı olmak üzere bir küme oluştursun. Bu küme genelde Z(n) (Çevirmenin yorumu: asal belgede n, Z'nin sağ altında gösterilmektedir, bu çeviride parantez içerisinde gösterilecektir.) şeklinde gösterilir. Elemanlar 0, 1, 2, ..., n-1 ve işlem toplamanın n ile bölümünden kalan şeklindedir:
Birim eleman 0 sayısıdır ve a'nın tersi n-a'dır (tersi kendisi olan 0 sayısı hariç).
4. Değişemeyen kümeye örnek olarak, 2'ye 2 tekil olmayan gerçek (reel) sayılardan (ya da rasyonel sayılardan) oluşan matrisler düşünelim, işlem matris çarpmasıdır:
Buradaki a, b, c ve d gerçek sayılardır (ya da rasyonel) ve ad-bc sıfır değildir. İşlem matris çarpmasıdır. Yukarıdaki matrisin tersi
ve birim elemanı
Bu bir sınırsız değişemeyen bir kümedir.
5. Ondalıklı sayıların bir bölümü sınırlı değişemez kümelere ilginç ve faydalı bir örnek olarak verilebilir: on elemanlı dihedral (Çevirmenin yorumu: kelime aslı gibidir, kısaca uçak kanatlarının yatay düzlemle yaptığı açıya denir, detaylı bilgi için bkz: [1] http://en.wikipedia.org/wiki/Dihedral_group, [2] http://tr.wikipedia.org/wiki/Dihedral) kümesi.
KANUN KÜME-1: Şifrecilerin gözde kümesi, tam sayıları n ile mod alandır, Z(n).
n = 10'a özel olarak, Z(10)'da toplama işlemi (x+y) mod 10 şeklinde tanımlanabilir, bu, 10'a böl ve kalanını al demektir. Tablo 1.3 nasıl olduğunu göstermektedir ve ayrıca 10 sayısı ile mod alınan tam sayıların toplama tablosu olarak da kullanılabilir.
1.4 Alanlar
Bir alan içerisinde bir çok yapıyı bulunduran bir nesnedir ki bu bölüm yalnızca bir özet niteliğindedir. Bir alan iki işleme sahiptir, bunları + ve * (adi toplama ve çarpma olmak zorunda olmamasına rağmen) olarak adlandıralım. +'yı kullanırsak, alanın tüm elemanları değişebilen bir küme kuracaktır. Bu kümenin birim elemanını 0 olarak ve a'nın tersini -a olarak gösterelim. *'yı kullanırsak, 0 hariç alanın tüm elemanları, birim elemanı 1 ile ve a'nın tersi a^-1 ile gösterilen başka bir değişebilen küme oluşturacaktır. (0 elemanının * işlemi altında tersi yoktur.) Ayrıca bir de dağılma özelliğine sahiptir, + ya da * ile bağlandığında: a*(b+c) = (a*b) + (a*c), a,b ve c tüm elemanlar için. Son olarak birşeyi hariç tutmalıyız, sıfıra bölünenler, bunlar sıfır üreten sıfır olamayan elemanlardır. Bu aşağıdaki fesih neteliğine eşdeğerdir:
eğer c sıfır değilse ve a*c = b*c ise a = b 'dir.
Örnekler:
1. Rasyonel sayıları (kesirler) Q olarak düşünelim, ya da gerçek sayıları R olarak, ya da karmaşık sayıları C olarak, bunlarda adi toplama ve çarpma işlemi kullanmak ( son durumda karmaşık sayılar dahil edilmiştir). Bunların tümü sınırsız alanlardır.
2. Tam sayıların p ile mod alındığını düşünelim, Z(p) olarak gösterilsin, p bir asal sayı olsun (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...). Bunu + kullanan bir küme olarak görelim (adi toplamanın ardından p'ye bölümünden kalandır). 0 olan elemanlar * altıda bulunmadığı bir küme oluşacaktır (p'ye bölümünden kalanın ardıdan yapılan adi çarpmadır). Burada birim eleman belirgin olarak 1'dir, ama sıfır olmayan a elemanının tersi açık değildir. Java'da tersi, (x*a)%p==1 olan bir x elemanı olmalıdır. Sayılar teorisinde genişletilmiş Öklit Algotirması olarak bilinen bir algoritma kullanılarak eşsiz bir x elemanı bulmak her zaman mümkündür. Bir sonraki bölümün bu başlığında, özet olarak: p'nin asal sayı olması ve a'nın sıfırdan farklı olması sebebiyle, p ve a'nın en büyük ortak bölenleri 1'dir. Şimdi genişletilmiş Öklit algoritması, x*a + y*p = 1 ya da x*a = 1 - y*p sağlayan x ve y sıradan tam sayılarını verecektir, ve bu bize eğer x*a'yı p'ye bölersen 1 kalanını alırsın demektedir, böylece bu x, a'nın tersi olur. ( Bir tam sayı olarak, x negatif olabilir, ve bu durumda Z(p)'nin bir elemanını alabilmesi için ona p eklenmelidir.)
KANUN ALAN-1: Şifrecilerin gözde alanı p'nin asal olduğu Z(p) ile gösterilen tamsayıların p ile modunu alandır.
Yukarıdaki alan p elemanlı olarak tektir. Diğer bir değişle, alan elemanlarının yeniden adlandırılmasıyla eşsizdir, yani alanın elemanları her zaman için bir başka işaret takımıyla gösterilebilir, fakat temel olarak aynıdır.
Ayrıca GF(p^n) şeklinde gösterilen, p^n'in elemanlarından herhangi birisi için n>1 geçerli olan eşsiz sınırlı bir alan daha vardır. Bilhassa şifrelemede p=2 özel durumu çok işe yarar. Bu durumda, n>1 olamak üzere 2^n adet eleman vardır. 2^8 = 256 durumu, örnek olarak, yeni Birleşmiş Milletler Gelişmiş Şifreleme Ölçünü'nünde (U.S. Advanced Encryption Standart - AES) kullanılmıştır. Bunu anlatmak Z(p) alanını anlatmaktan daha zordur. AES için çarma işlemi hakkındaki bölüm bu alanı daha detaylı anlatacaktır, fakat burada bazı özelliklerini özetlemek gerekirse: 256 tane elemanı vardır, 8-bitlik olası tüm katarları ifade eder. Bu alanda toplama bitsel özel veya (XOR) ya da yine bitsel olarak toplamanın mod 2 işlemiyle aynıdır. Sıfır elemanı 00000000'dır, ve birim eleman 00000001'dır. Şimdiye kadar iyi gittik, fakat çarma yapmak daha bir sorunlu: bir eleman, Z(p) alanında katsayılar içeren 7. dereceden bir polinomu ifade etmelidir (bir 0 ya da 1)ve bu polinomların özel bir çarpma hali kullanımalıdır. Ayrıntılar AES üzerine olan sonraki bölümde gelecektir.
KANUN ALAN-2: Şifrecilerin diğer bir gözde alanı GF(2^n)'dır.
Hiç yorum yok:
Yorum Gönder