HesapHanem

Tonelli-Shanks Modüler Karekök Hesaplayıcı

Modüler karekökü bulmak için n ve bir asal p girin.

Nasıl hesaplanır?

Amaç, r² ≡ n (mod p) koşulunu sağlayan bir r bulmaktır. Araç önce n'yi p'ye göre indirger ve p'nin asal olduğunu (deneme bölmesiyle) doğrular. Ardından Euler kriterini uygular: kök ancak n^((p-1)/2) ≡ 1 (mod p) ise vardır; değilse sonuç çıkmaz. Sonra p - 1 = Q × 2^S yazar. S = 1 ise (p ≡ 3 mod 4) kök doğrudan n^((p+1)/4) mod p olur. Aksi halde, aramayla bulunan bir karesel kalan olmayan sayı kullanılarak düzeltme terimi 1 olana kadar Tonelli-Shanks döngüsü çalışır.

r bir kökse p - r de köktür; araç ikisini küçük olan önce gelecek şekilde ve r² mod p kontrol satırıyla birlikte gösterir. Negatif ya da p'den büyük n önce mod p'ye indirilir. n, p'nin katıysa tek kök 0'dır. p = 2 özel durum olarak ele alınır. Bileşik p, karesel kalan olmayan n ya da 2'den küçük p sonuç vermez.

Örnek hesaplama

10'un mod 13'teki karekökünü bulalım. Euler kriteri: 10^6 mod 13 = 1, yani kök vardır. Burada 13 - 1 = 12 = 3 × 2² olduğundan S = 2'dir ve kısayol yerine Tonelli-Shanks döngüsü kullanılır. Sonuç 6 (and 7) çıkar. Kontrol: 6² = 36 ve 36 - 2 × 13 = 10, yani 6² mod 13 = 10. İkinci kök 13 - 6 = 7'dir; 7² = 49 ve 49 - 3 × 13 = 10 olur.

Bu örneği dene →

Sık yapılan hatalar

  • 15 gibi bileşik bir modül kullanmak. Yöntem asal p ister; mod 15'te karekökler olsa bile araç 15 için sonuç vermez.
  • Her n için kök beklemek. Yalnızca karesel kalanların kökü vardır; n = 5 ve p = 13 için kök yoktur ve araç sonuç vermez.
  • Cevabı tek sanmak. n ≡ 0 (mod p) dışında her zaman iki kök vardır: r ve p - r.
  • Modüler kökü sıradan karekökle karıştırmak. 10'un sıradan karekökü 3,16'dır; ama mod 13'te 10'un kökü 6'dır, çünkü 6² = 36'nın 13'e bölümünden kalan 10'dur.
  • n'nin zaten indirgendiğini unutup farklı değerler denemek. Mod 13'te n = 23 ile n = 10 aynı sonucu verir.

Bu hesaplama hakkında

Tonelli-Shanks algoritması, hesaplamalı sayılar teorisinin temel işlemlerinden biri olan, verilen bir n sayısı ve tek asal modül p için r² ≡ n (mod p) koşulunu sağlayan bir modüler karekök — yani r değerini — bulur. Ana algoritmayı çalıştırmadan önce Euler kriterini denetler: n’nin mod p’de bir karesel kalan olması (yani bir karekökün var olması), tam olarak n^((p−1)/2) ≡ 1 (mod p) olduğunda gerçekleşir. p ≡ 3 (mod 4) olduğunda karekök için doğrudan kapalı formda bir kısayol vardır, ancak p ≡ 1 (mod 4) olan daha zor genel durum için, p−1’den 2 çarpanlarını ayıklamak amacıyla karesel kalan olmayan bir sayıya karşı tekrarlanan karesini alma işlemi kullanan Tonelli-Shanks gerekir.

Bu işlem, pratik kriptografinin temelini oluşturur — özellikle ECDSA ve Bitcoin’in kullandığı sıkıştırılmış açık anahtar biçimlerinde, x-koordinatından bir eliptik eğri noktasının çözülmesinde; burada y-koordinatının, eğri denkleminden türetilen bir değerin modüler karekökü olarak geri kazanılması gerekir.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    Bu araç, elle yaptığınız hesabı doğrulayabileceğiniz ya da kendi uygulamanızı sınayabileceğiniz küçük asallar için en uygunudur. Sıradan makine tamsayılarıyla çalışır ve modülün asal olup olmadığını deneme bölmesiyle sınar; gerçek eliptik eğrilerde kullanılan 256 bitlik asallar kapsamının çok dışındadır. Bir deneme örneği: 101 modunda 56'nın karekökü 37 ve 64 çıkar. Tonelli-Shanks'i hangi dilde yazıyorsunuz ve hangi durumlar sizi zorladı?

Popüler hesaplayıcılar

Kredi Hesaplama

Aylık taksit, toplam faiz ve ödeme planını hesaplayın.

Yüzde Hesaplama

Yüzde değişim, indirim ve oran hesaplamaları.

İndirim Hesaplama

İndirimli fiyatı, kazancı ve indirim tutarını hesaplayın.

Vücut Kitle Endeksi (VKİ)

Boy ve kiloya göre vücut kitle endeksini hesaplayın.

Yaş Hesaplama

Doğum tarihinden bugüne tam yıl, ay ve gün cinsinden yaşınızı hesaplayın.

Bileşik Faiz Hesaplama

Ana para, faiz oranı ve süreye göre bileşik faizle nihai tutarı hesaplayın.

Tüm Hesaplayıcılar