Karesel Elek Pürüzsüzlük Hesaplayıcı

Bir n tam sayısını asal çarpanlarına ayırarak her çarpanın B sınırını aşıp aşmadığını, yani n'nin B-pürüzsüz olup olmadığını ve en büyük asal çarpanını gösterir.

Sonuç

5.460 sayısı 10-pürüzsüz mü: hayır
2^2 x 3 x 5 x 7 x 13 (>B)
13

Nasıl hesaplanır?

n ve B tam sayı olmalıdır (n için 5.460,5 ya da B için 10,6 gibi ondalıklı bir değer sonuç vermez); ikisi de en az 2 olmalı ve 9.007.199.254.740.992 = 253 değerini aşmamalıdır. Araç n'yi tamamen çarpanlarına ayırır: sırayla 2, 3, 5, 7 ve diğerlerine böler, her böleni sığdığı kadar çok kez ayıklar; kalan büyük asal çarpanları hızla tanımak için kalan sayıya bir asallık testi uygular. Çarpanlara ayırma 2^3 x 3^2 x 5 biçiminde yazılır ve B'den büyük her asal çarpan "(>B)" ile işaretlenir. En büyük asal çarpanı en fazla B olan n, B-pürüzsüz (B-smooth) sayılır; en büyük asal çarpan ayrıca gösterilir. B çarpanlara ayırmayı sınırlamaz, yalnızca evet ya da hayır kararını belirler. n, hepsi yaklaşık altı milyonun üzerinde iki ya da daha çok asalın çarpımıysa arama çok uzun sürer ve sonuç gösterilmez.

Örnek hesaplama

n = 5460 sayısını B = 10 sınırıyla test edelim. 2 iki kez ayıklanır (5460 → 1365), 3 bir kez (→ 455), 5 bir kez (→ 91) ve 7 bir kez (→ 13). Kalan 13 asaldır ve 10'dan büyüktür. Araç 5.460 sayısı 10-pürüzsüz mü: hayır sonucunu, 2^2 x 3 x 5 x 7 x 13 (>B) çarpanlara ayrılışıyla ve en büyük asal çarpan 13 olarak gösterir. B = 13 olsaydı aynı n için "5.460 sayısı 13-pürüzsüz mü: evet" çıkardı, çünkü her asal çarpan en fazla 13'tür.

Bu örneği deneyin →

Sık yapılan hatalar

  • B-pürüzsüzlüğü az çarpanlı olmakla karıştırmak. 5460'ın beş farklı asal çarpanı vardır ve 13-pürüzsüzdür, ama 13 sınırın üstünde olduğu için 10-pürüzsüz değildir.
  • İstediğiniz test için B'yi çok düşük seçmek. 360 = 2^3 x 3^2 x 5 sayısı B = 5 ile geçer, ama 5 çarpanı yüzünden B = 3 ile geçmez.
  • "(>B)" işaretini sayının bileşik olduğunun belirtisi sanmak. İşaret, sınırı aşan her asalı gösterir; B = 50 iken 97 gibi asal bir n için sonuç yalnızca 97 (>B) olur.
  • n için 2,6 ya da B sınırı için 10,6 gibi ondalıklı bir sayı girmek: araç ikisinde de sonuç vermez, tam sayı girin.
  • Her büyük sayının çalışacağını beklemek. n, ikisi de yaklaşık altı milyonun üzerindeki iki asalın çarpımıysa araç çarpanlara ayırmak yerine sonuç göstermez; bu tür sayıların zor olmasının nedeni de budur.

Kaynaklar

  • A Tale of Two Sieves — Carl Pomerance, Notices of the American Mathematical Society 43(12), 1996

Bu hesaplama hakkında

Karesel elek pürüzsüzlük hesaplayıcı, bir n tam sayısını tamamen çarpanlarına ayırır (deneme bölmesi ve geriye kalan kısma uygulanan bir asallık testiyle), n'nin seçilen B pürüzsüzlük sınırına göre B-pürüzsüz olup olmadığını (yani tüm asal çarpanlarının B'ye eşit veya küçük olup olmadığını) bildirir ve B'nin üzerindeki her asalı işaretleyerek tam asal çarpanlara ayrılışı en büyük asal çarpanla birlikte döndürür. Asal çarpanlardan biri B'nin üzerindeyse n B-pürüzsüz değildir.

Pürüzsüzlük testi, karesel elek ve genel sayı alanı eleği gibi tam sayı çarpanlarına ayırma algoritmalarının temel tarama adımıdır; bu algoritmalar devasa bir bileşik n sayısını doğrudan çarpanlarına ayırmaya çalışmaz — bunun yerine n ile ilişkili, tesadüfen B-pürüzsüz olan çok sayıda sayı arar, sonra bu ilişkileri doğrusal cebirle birleştirerek bir çarpan çıkarır. Kriptograflar, sayı teorisi öğrencileri ve RSA anahtarı çarpanlara ayırma zorluğunu inceleyen araştırmacılar, tek tek adaylarda pürüzsüzlüğü kontrol etmek ve iyi seçilmiş bir anahtar boyutunun çarpanlara ayırmayı neden hesaplama açısından imkânsız kıldığını anlamak için bu hesaplayıcıyı kullanır.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Editörlerden not

Sınır yaklaşık 9 x 10^15'tir ve iki çok büyük asal çarpanı olan bir sayı burada bölünemeyecek kadar yavaş olup sonuç vermeyebilir. 7 x 11 x 13 olan 1001'i alın: B = 12 ile araç hayır, B = 13 ile evet der; yani kararı yalnızca sınır değiştirir. Hangi B sınırına karşı deniyorsunuz?

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Tüm Hesaplayıcılar