Euler Totient Hesaplama

Herhangi bir pozitif tam sayının Euler totientini bulun.

Nasıl hesaplanır?

Euler'in φ(n) fonksiyonu, 1 ile n arasında n ile 1'den başka ortak böleni olmayan tam sayıların adedidir. Araç her sayıyı tek tek denemez. n'yi asal çarpanlarına ayırır ve n'yi bölen her farklı asal p için φ(n) = n × ∏(1 − 1/p) çarpım formülünü yalnızca tam sayı adımlarıyla uygular. Asal bir p için φ(p) = p − 1'dir. Girdi 1 ile 1.000.000.000 arasında bir tam sayı olmalıdır; 36,5 gibi ondalıklı bir değer sonuç vermez. İki sonuç alanı da aynı sayıyı gösterir.

Örnek hesaplama

n = 36 alalım. Asal çarpanları 2 ve 3'tür, çünkü 36 = 2² × 3². 36 ile başlanır. Asal 2 için 36 / 2 = 18 çıkarılır, 18 kalır. Asal 3 için 18 / 3 = 6 çıkarılır, 12 kalır. Yani φ(36) = 12: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 ve 35 sayılarının 36 ile ortak böleni yoktur.

Bu örneği deneyin →

Sık yapılan hatalar

  • Her asal çarpanı kuvvetiyle birlikte saymak. 36 = 2 × 2 × 3 × 3 olsa da formülde yalnızca farklı asallar 2 ve 3 kullanılır.
  • Her n için φ(n) = n − 1 sanmak. Bu yalnızca asallar için geçerlidir; 36 için sonuç 35 değil 12'dir.
  • Ortak çarpanı olan sayıların φ değerlerini çarpmak. φ(a × b) = φ(a) × φ(b) yalnızca a ile b aralarında asalsa geçerlidir.
  • Ondalıklı ya da bir milyardan büyük sayı girmek. Ondalıklı bir sayıda da daha büyük bir değerde de sonuç çıkmaz.

Kaynaklar

Bu hesaplama hakkında

Bu hesaplayıcı, 1'den n'e kadar n ile aralarında asal olan (n ile 1 dışında ortak böleni olmayan) pozitif tam sayıların sayısı olan Euler totientini φ(n) bulur. Değer, n'in asal çarpanlarına ayrılmasından φ(n) = n·∏(1 − 1/p) çarpım formülüyle hesaplanır (p, n'in her farklı asal çarpanı üzerinden); bir asal sayı p için ise φ(p) = p − 1'dir.

Totient fonksiyonu sayılar teorisinin merkezinde yer alır ve RSA açık anahtarlı şifreleme sisteminin matematiksel temelini oluşturur; burada iki büyük gizli asal sayıdan hesaplanan φ(n), özel anahtarı açık anahtardan türetmek için kullanılır. Ayrıca modüler aritmetikte sıkça kullanılan Fermat'nın küçük teoreminin genellemesi olan Euler teoremini de yönetir.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Editörlerden not

İki farklı asal sayının çarpımı olan bir modül için, n = p × q ise totient (p − 1)(q − 1) değerine eşit olmalıdır; elle kontrol için kullanışlıdır: 77 = 7 × 11 için 6 × 10 = 60 çıkmalıdır. Bu aracın üst sınırının bir milyar olduğunu, gerçek RSA modüllerinin boyutunun çok altında kaldığını unutmayın; yani öğrenme ve ödev için uygundur, anahtar üretimi için değil. Modüler aritmetik sorusu mu çözüyorsunuz? Takıldığınız n değerini ve beklediğiniz sonucu paylaşın.

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Tüm Hesaplayıcılar