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

Tonelli-Shanks algoritmasıyla r² ≡ n (mod p) denklemini sağlayan iki modüler karekökü bulur ve sonucu doğrular.

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 (ve 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 deneyin →

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.

Kaynaklar

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.

Editörlerden not

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ı?

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Tüm Hesaplayıcılar