HesapHanem

Fermat Çarpanlara Ayırma Hesaplama

Fermat yöntemiyle çarpanlara ayırmak için tek bir sayı girin.

Nasıl hesaplanır?

Fermat yöntemi tek bir sayıyı iki karenin farkı olarak yazar: N = a² − b² = (a − b)(a + b). Araç a = ⌈√N⌉ değerinden başlar ve her a için a² − N değerinin tam kare b² olup olmadığına bakar. İşe yarayan ilk a, a − b ve a + b çarpanlarını verir; denenen a değerlerinin sayısı adım olarak gösterilir. Tek bir çarpan çifti döner, tam asal çarpanlara ayırma değildir; 7 × 15 gibi bir çiftte bileşik sayılar da bulunabilir. Çift sayılar aranmaz: 2 × N/2 ve 0 adım döner. Asal sayı yaklaşık N ÷ 2 adım sonra 1 × N olarak gelir. Döngü 2.000.000 adımda durur; bu yüzden çok büyük asallar ya da çarpanları birbirinden uzak sayılarda sonuç çıkmayabilir.

Örnek hesaplama

N = 5959 sayısını ayıralım. √5959 ≈ 77,2 olduğundan a = 78'den başlanır. 1. adım: 78² − 5959 = 125, kare değil. 2. adım: 79² − 5959 = 282, kare değil. 3. adım: 80² − 5959 = 6400 − 5959 = 441 = 21², tam kare; yani b = 21. Çarpanlar 80 − 21 = 59 ve 80 + 21 = 101 olur, 3 adımda bulunur. Kontrol: 59 × 101 = 5.959.

Bu örneği dene →

Sık yapılan hatalar

  • Çift sayı girip Fermat aramasını beklemek. Araç yalnızca 2'yi ayırır ve adım sayısı 0 olur; yöntemin kalanda çalışmasını istiyorsanız önce 2'nin kuvvetlerini bölün.
  • 1 × N sonucunu hata sanmak. Başka çarpan çifti olmadığı, yani N'nin asal (ya da 1) olduğu anlamına gelir.
  • Gösterilen iki çarpanın her zaman asal olduğunu varsaymak. Çarpım N'yi verir ama çarpanlardan biri bileşik olabilir ve ayrıca bölünmesi gerekir.
  • Çarpanları birbirinden çok uzak sayıları denemek, örneğin 3 ile büyük bir asalın çarpımı. Fermat yöntemi yüz binlerce adım ister ve araç 2.000.000'da vazgeçer.
  • Ondalıklı sayı girmek. Girdi en yakın tam sayıya yuvarlanır.

Bu hesaplama hakkında

Fermat'nın çarpanlara ayırma yöntemi, tek bir N tam sayısının her zaman iki karenin farkı olarak yazılabileceği gerçeğinden faydalanır: N = a² − b² = (a−b)(a+b). Algoritma a = ⌈√N⌉ ile başlar ve her adımda a'yı 1 artırarak a² − N değerinin tam kare (b²) olup olmadığını kontrol eder; olduğu an N, (a−b)(a+b) şeklinde anında çarpanlarına ayrılır. Bu hesaplayıcı bu döngüyü çalıştırır; bulduğu iki çarpanı ve bunun için kaç adım attığını gösterir.

Yöntem, N'nin iki çarpanı birbirine yakın olduğunda çok az adımda sonuca ulaşır — bu aynı zamanda en önemli gerçek dünya kullanımını da açıklar: kriptografi öğrencileri ve güvenlik araştırmacıları Fermat çarpanlara ayırmayı, RSA modüllerinin neden birbirinden uzak asal sayılardan oluşturulması gerektiğini göstermek için kullanır; çünkü birbirine çok yakın seçilen asal sayılar modülü kolayca kırılabilir hale getirir. Aynı zamanda sayılar teorisi derslerinde kareler farkı mantığını göstermek için standart bir alıştırmadır.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar (1)

  • Editör ekibi

    İlginç çıktı adım sayısıdır. 59 çarpı 101 olan 5959, 3 adımda bulunur; asal olan 1000003'te ise arama 1 çarpı 1.000.003 sonucunu vermeden önce 499.002 adım sürer. Yakın çarpanlar ucuz, uzak çarpanlar ve asallar pahalıdır; döngü 2.000.000 adımdan sonra vazgeçer. Araç her adımı değil, kaç adım attığını bildirir. Siz hangi sayıları denediniz ve kaç adım sürdü?

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