euler fonksiyonu

• phi(n) olarak gösterilir. 1 ile n arasında n ile aralarında asal olan sayıların sayısını verir
• cok muhim bir fonksiyondur. rsa sifreleme sistemi de kullanır bunu
• düz mantiktan buyrun, eğer n asalsa, phi(n) = n -1 olacaktir elbette... "tabii ki" demeyin, önemli bi detay bu...
• eğer n sayısını asal çarpanlarına ayırırsak, o zaman
  phi(n)= n (1-1/p1) (1-1/p2).... olur, p1, p2 vs. n'in asal çarpanları elbette...
  ya da
  (p1^b - p1^b-1)(p2^c-p2^c-1)... şeklinde de hesaplanabilir... b, c vs. asal çarpanların üsleri olarak...
• n pozitif tam sayi icin 1<=a<=n ve a ve n aralarinda asal olmak uzere a tam sayilarinin sayisi ve euler fonksiyonu phi(n)'dir.
  
  phi(n)=n pi^*(1-1/p) seklinde formuluze edebiliriz. p n'nin asal bolenleridir.
  
  ornegin, phi(144)=?
  
  144'nin asal bolenleri 2 ve 3'tur.
  
  144*(1-1/2)*(1-1/3)=48.
• üç temel özelliği vardır ve soyut cebir'in uygulama alanında çok kolaylık sağlar.
  
  1. p asal ise phi(p)=p-1 dir.
  2. phi(p^n) = p^n (1-1/p) dir.
  3. (m,n)=1 ise phi(m,n) = phi(m) . phi(n) dir
• sayıdan küçük ve o sayı ile aralarında asal olan pozitif tam sayıların sayısını verir. hesaplamanın yolu sayıyı asal çarpanlarına ayırmak, onların belirlenen sayıya kadar katlarının ayrı ayrı kaç adet olduğunu bulmak ve bu sayıları çarpmaktır.
  örneğin
  143 ün euler phi fonksiyonu için değeri 143=11*13
  11,22,33,44,55,66,77,88,99,110,121,132=>12 tane
  13,26,39,52,65,78,91,104,117,130=>10 tane
  12*10=120
  tüm asal çarpanlar bulunduktan sonra onların 1er eksikleri alınıp hepsi çarpılırsa da bu sonuca ulaşılabilir. (ancak bu euler fonksiyonunun bir sonucu olarak görülmemelidir.)
  
  asal bir sayının euler phi fonksiyonu altındaki görüntüsü hep o asal sayının bir eksiğine eşittir. (çünkü asal sayının 1 hariç kendisinden başka böleni yoktur. 1 ile her şey arasında asaldır ve 1 her şeyi böler. biraz değişik bir arkadaş.)
  
  asal olmayan ancak asal bir sayının karesi olan sayıların euler phi fonksiyonu altındaki görüntüsü (o sayının kendisi) - (o sayının üssünün bir eksik hali)
  örneğin: 27 nin euler phi fonksiyonu altındaki görüntüsü 3^(3)-3^(2) = 24 olmaktadır.
  
  ilk 100 değeri için hiç bir zaman sonuç sayının 15te birinin 4 katını geçemez.
  maksimum değer ise tüm pozitif tam sayılar için sayının bir eksiğidir.
  x in (0,100)
  min(phi(x))=4*x/15
  max(phi(x))=x-1
• rsa şifrelemesindeki rolü şu şekildedir:
  
  * iki adet asal sayı alırız: p ve q
  * n = p * q değerini hesaplarız
  * phi(n) aslında phi(p * q)'dur. p ve q asal oldukları için her ikisinin de p-1 ve q-1 tane aralarında asal sayıları vardır. şimdi bunu p * q olarak düşündüğümüzde p ve q sayılarıın ikisi de asal oldukları için zaten hiç bölenleri yok yani p'nin p-1 tane ve q'nun q-1 tane aralarında asal sayıları birbirleriyle de aralarında asallar ve n = p * q sayısının aralarında asal oldukları sayıların toplam sayısı bu durumda "phi(n = p * q) = (p - 1) * (q - 1)" olarak hesaplanabilir çünkü n sayısı p * q olarak ifade edilebilir ve bu çarpanların ikisi de asal; bu çarpımın değerine kadar olan, çarpanların kendilerine ait aralarında asal sayıların her biri p ve q ile de aralarında asal oldukları için ikisini de bölemezler ve sonucunda p * q'yu da bölemeyecekleri anlamına gelir bu tabii ki n = p * q sayısını p ve q'nun kendileri böleceği için (çünkü ikisinin çarpımı) n sayısının "phi(n = p * q) = (p - 1) * (q - 1)" adet aralarında asal sayısı var demek oluyo.
  * phi(n) değerini bulduktan sonra her şey public exponent e, n ve e^-1 (mod phi(n))` (yani e'nin phi(n) tabanında tersi) değerleri arasındaki bağlantıya kalıyo:
  
  şöyle bişi:
  * "d = e^-1 (mod phi(n))"
  * d'nin sahibine mesajımız m olsun, bu mesajı c = m^e % n yaptığımızda şifreli mesajı elde ediyoruz.
  * bu c'yi m = c^d % n şeklinde şey ettiğimizde orjinal mesajı tekrar elde ediyoruz.
  
  burda aslında m = c^d % n'daki d aslında e^-1 (mod phi(n)) ve e ve n'yi ztn biliyoruz (e, n) şeklinde dağıtıyoruz hatta public key olarak ama n aslında n = p * q ve "phi(n) = (p-1) * (q-1)" yani şifreyi kırmak için phi(n) değeri, onun için de n'i oluşturan p ve q sayılarını bulmak lazım ama bu sayılar asal oldukları için, çok büyük olduklarında n'in hangi iki asal sayının çarpımından oluştuğunu bulmak zor çünkü deneme yanılma yaparak bunu bulmaya çalışan bi döngü, en iyi ihtimalle kendi şifrelediği çok küçük bi mesajı sürekli olarak iterative p ve q değerleriyle tekrar elde etmeyi denemli; bu da çok uzun zaman alan bişi.
  
  ama e, n ve e^-1 (mod phi(n))` değerleri arasında niye bu bağlantı var? diye sorarsanız, bilmiyorum. leonhard euler manyağına sormak lazım.