Hesapstan tarafından hazırlanan Fermat'ın Küçük Teoremi Hesaplama aracı, asal modül altında teorem kontrolü, üs indirgeme ve modüler ters işlemlerini adım adım açıklar.
Fermat'ın Küçük Teoremi asal modülde tekrar eden güçleri açıklar
Fermat'ın Küçük Teoremi, p asal sayı ve a sayısı p ile aralarında asal olduğunda a^(p-1) ≡ 1 (mod p) olduğunu söyler. Aynı fikir, a^p ≡ a (mod p) biçiminde de kullanılabilir.
Bu teorem özellikle büyük üslerin kalanı istendiğinde işe yarar. Örneğin doğrudan 2^100 hesaplamak yerine, asal modül 7 için üs döngüsünü p-1 = 6 üzerinden sadeleştirmek mümkündür.
Fermat'ın Küçük Teoremi, asal modül altında bazı üslerin düzenli biçimde tekrar ettiğini gösteren temel bir modüler aritmetik teoremidir.
Hesaplayıcı üç farklı Fermat uygulaması sunar
Teorem kontrolü modunda araç a^p mod p değerini a mod p ile karşılaştırır. Burada p asal olmalıdır; asal olmayan modül girildiğinde hesaplama teoremin varsayımını sağlamaz ve reddedilir.
Üs indirgeme modunda amaç a^n mod p sonucunu Fermat döngüsünden yararlanarak bulmaktır. Modüler ters modunda ise a^(-1) mod p değeri a^(p-2) mod p olarak hesaplanır.
Araç RSA anahtarı üretmez, şifreleme yapmaz ve güvenlik iddiasında bulunmaz. İçerik yalnızca Fermat'ın Küçük Teoremi kapsamındaki eğitim amaçlı modüler hesaplamaları açıklar.
p asal değilse Fermat'ın Küçük Teoremi uygulanmaz
Teoremin klasik biçiminde modül p asal sayıdır. Bu nedenle p = 7 gibi asal bir modülde teorem güvenle uygulanırken, p = 8 veya p = 9 için aynı kuralı otomatik olarak kullanmak doğru değildir.
Ayrıca a^(p-1) ≡ 1 (mod p) biçimini kullanırken a ile p'nin aralarında asal olması gerekir. Eğer a, p'nin katıysa kalan davranışı farklıdır ve hesaplama teoremin varsayımıyla yorumlanmalıdır.
Runtime p değerinin asal olup olmadığını kontrol eder. Bu kontrol teoremin koşulunu korumak içindir; araç Miller-Rabin gibi genel bir asal sayı test aracı olarak sunulmaz.
Büyük üsler p−1 döngüsüyle küçültülür
p asal ve a, p ile aralarında asal ise a^(p-1) ≡ 1 (mod p) olur. Bu nedenle üs n, p−1'e göre sadeleştirilebilir ve büyük üs problemi daha küçük bir kalan problemine dönüşür.
Örnek olarak 2^100 mod 7 için p−1 = 6 olur. 100 sayısının 6'ya göre kalanı 4 olduğu için sonuç 2^4 mod 7 üzerinden bulunur.
Üs indirgeme, asal modül ve uygun taban koşullarıyla anlamlıdır. Bu araç Euler teoremini veya asal olmayan modüller için genel modüler üs teorisini vaat etmez.
Modüler ters a^(p−2) ile bulunur
Modüler ters, a × x ≡ 1 (mod p) eşitliğini sağlayan x değeridir. p asal ve a, p'nin katı değilse Fermat'ın Küçük Teoremi bu tersin a^(p-2) mod p olarak bulunmasını sağlar.
Örneğin 3'ün 7 modülündeki tersi için 3^(7-2) = 3^5 hesaplanır. 3^5 mod 7 = 5 olduğu için 3 × 5 = 15 ≡ 1 (mod 7) olur.
Modüler ters, normal anlamdaki 1/a kesri değildir. 3'ün çarpma tersi 1/3 iken, 7 modülünde modüler tersi 5'tir.
Örnekler teorem kontrolü, üs indirgeme ve modüler tersi ayırır
Teorem kontrolü örneği: a = 3 ve p = 7 için 3^7 mod 7 = 3 olur; bu da a^p ≡ a (mod p) biçimini doğrular.
Üs indirgeme örneği: 2^100 mod 7 için 100 ≡ 4 (mod 6), dolayısıyla 2^100 ≡ 2^4 ≡ 16 ≡ 2 (mod 7) olur.
Modüler ters örneği: 3^5 mod 7 = 5 sonucuyla 3'ün mod 7'deki tersi 5 bulunur. Kontrol: 3 × 5 = 15 ve 15 mod 7 = 1.
Sık Sorulan Sorular
Fermat'ın Küçük Teoremi nedir?
p asal ve a, p ile aralarında asal ise a^(p-1) ≡ 1 (mod p) olur. Eşdeğer biçimde a^p ≡ a (mod p) yazılabilir.
Bu hesaplayıcı neden p değerinin asal olmasını ister?
Çünkü Fermat'ın Küçük Teoremi asal modül için geçerlidir. Asal olmayan modüller için Euler teoremi gibi farklı araçlar gerekir.
Modüler ters nedir?
a sayısının mod p altındaki modüler tersi, a × x ≡ 1 (mod p) eşitliğini sağlayan x değeridir.
Modüler ters normal çarpma tersiyle aynı mı?
Hayır. Normal çarpma tersi 1/a biçimindedir; modüler ters ise belirli bir modül altında çarpınca kalan 1 veren tam sayıdır.
Bu araç RSA veya kriptografi hesaplar mı?
Hayır. Araç eğitim amaçlı Fermat teoremi hesaplamaları yapar; RSA, anahtar üretimi veya güvenlik analizi sunmaz.
Fermat'ın Küçük Teoremi ile Euler teoremi aynı şey mi?
Hayır. Fermat'ın Küçük Teoremi asal modüller için özel bir sonuçtur. Euler teoremi daha genel modüller için farklı bir çerçeve kullanır.