Düzgün numara - Smooth number

İçinde sayı teorisi, bir n-pürüzsüz (veya ngevrek) numara bir tamsayı kimin asal faktörler hepsi daha küçük veya eşit n.^[1]^[2]^[3] Örneğin, 7-düz sayı, asal çarpanlarının tümü en fazla 7 olan bir sayıdır, dolayısıyla 49 = 7² ve 15750 = 2 × 3² × 5³ × 7'nin her ikisi de 7 pürüzsüzdür, 11 ve 702 = 2 × 3³ × 13, 7-düzgün değil. Terim tarafından icat edilmiş gibi görünüyor Leonard Adleman.^[4] Düzgün sayılar özellikle kriptografi, tamsayıların çarpanlara ayrılmasına dayanır. 2 düz sayı sadece 2'nin kuvvetleri 5 düz sayılar olarak bilinirken normal sayılar.

Tanım

Bir pozitif tamsayı denir B-pürüzsüz hiçbiri değilse asal faktörler daha büyüktür B. Örneğin, 1,620'de asal çarpanlara ayırma 2 vardır² × 3⁴ × 5; bu nedenle 1,620, 5-pürüzsüzdür çünkü asal çarpanlarından hiçbiri 5'ten büyük değildir. Bu tanım, bazı küçük asal çarpanlardan yoksun sayıları içerir; örneğin, hem 10 hem de 12, sırasıyla 3 ve 5 asal çarpanları atlasalar bile 5-düzgündür. Tüm 5 düz sayılar 2 biçimindedir^a × 3^b × 5^c, nerede a, b ve c negatif olmayan tam sayılardır.

5-düz sayılar da denir normal sayılar veya Hamming sayıları;^[5] 7-düz sayılar da denir mütevazı sayılar,^[6] ve bazen aradı oldukça kompozit,^[7] bu, başka bir anlamla çelişse de oldukça bileşik sayılar.

Burada, şunu unutmayın B kendisinin bir faktörün arasında görünmesi gerekli değildir B-düzgün numara. Bir sayının en büyük asal çarpanı p o zaman numara Bherhangi biri için pürüzsüz B ≥ p. Birçok senaryoda B dır-dir önemli, fakat bileşik sayılar izin verilir. Bir sayı B-pürüzsüz ancak ve ancak bu p-düzgün, nerede p en büyük asal küçüktür veya eşittir B.

Başvurular

Düz sayıların önemli bir pratik uygulaması, hızlı Fourier dönüşümü (FFT) algoritmaları (örneğin Cooley – Tukey FFT algoritması ), belirli bir boyuttaki bir problemi yinelemeli olarak parçalayarak çalışır n faktörlerinin boyutu problemlere dönüşür. Kullanarak B-düzgün sayılar, biri bu özyinelemenin temel durumlarının, verimli algoritmaların var olduğu küçük asal sayılar olmasını sağlar. (Büyük birincil boyutlar, daha az verimli algoritmalar gerektirir. Bluestein'in FFT algoritması.)

5-pürüzsüz veya normal sayılar özel bir rol oynamak Babil matematiği.^[8] Onlar da önemlidir müzik Teorisi (görmek Limit (müzik) ),^[9] ve bu sayıları verimli bir şekilde üretme problemi, bir test problemi olarak kullanılmıştır. fonksiyonel programlama.^[10]

Düzgün sayıların kriptografi için birçok uygulaması vardır.^[11] Çoğu uygulama odaklanırken kriptanaliz (ör. bilinen en hızlı tamsayı çarpanlara ayırma algoritmalar, örneğin: Genel numara alanı eleği algoritması), VSH karma işlevi, düzgünlüğün yapıcı kullanımının bir başka örneğidir. kanıtlanabilir güvenli tasarım.

Dağıtım

İzin Vermek ${ displaystyle Psi (x, y)}$ sayısını belirtmek y-düz veya daha küçük tamsayılar x (de Bruijn işlevi).

Pürüzsüzlük bağlıysa B sabit ve küçük, için iyi bir tahmin var ${ displaystyle Psi (x, B)}$ :

{ displaystyle Psi (x, B) sim { frac {1} { pi (B)!}} prod _ {p leq B} { frac { log x} { log p}} .}

nerede ${ displaystyle pi (B)}$ gösterir küçük veya eşit asal sayısı ${ displaystyle B}$ .

Aksi takdirde, parametreyi tanımlayın sen gibi sen = günlükx / logy: yani, x = y^sen. Sonra,

{ displaystyle Psi (x, y) = x cdot rho (u) + O sol ({ frac {x} { log y}} sağ)}

nerede ${ displaystyle rho (u)}$ ... Dickman işlevi.

Belirli bir boyuttaki düz kısmın ortalama boyutu olarak bilinir ${ displaystyle zeta (u)}$ ve çok daha yavaş bozunduğu bilinmektedir. ${ displaystyle rho (u)}$ .^[12]

Herhangi k, Neredeyse hepsi doğal sayılar olmayacak k-düzgün.

Powersmooth sayılar

Daha ileri, m denir B-Pürüzsüz (veya B-aşırıya kaçılabilir) hepsi asalsa güçler ${ displaystyle p ^ { nu}}$ bölme m tatmin etmek:

{ displaystyle p ^ { nu} leq B. ,}

Örneğin 720 (2⁴ × 3² × 5¹) 5 pürüzsüzdür ancak 5 üssü pürüzsüz değildir (çünkü 5'ten büyük birkaç asal güç vardır, Örneğin. ${ displaystyle 3 ^ {2} = 9 nleq 5}$ ve ${ displaystyle 2 ^ {4} = 16 nleq 5}$ ). En büyük asal faktör gücü 2 olduğu için 16 güç pürüzsüz⁴ = 16. Sayı ayrıca 17-powersmooth, 18-powersmooth, vs.'dir.

B-pürüzsüz ve B-powersmooth sayıların sayı teorisinde uygulamaları vardır, örneğin Pollard's p - 1 algoritma ve ECM. Bu tür uygulamaların genellikle "düz sayılarla" çalıştığı söylenir, B belirtildi; bu, ilgili sayıların olması gerektiği anlamına gelir B-powersmooth, bazı belirtilmemiş küçük sayılar için B. As B arttıkça, söz konusu algoritma veya yöntemin performansı hızla düşer. Örneğin, Pohlig – Hellman algoritması bilgi işlem için ayrık logaritmalar çalışma süresine sahip Ö (B^1/2)-için grupları nın-nin B-pürüzsüz sipariş.

Bir sette pürüzsüz hale getirin Bir

Dahası, m üzerinde pürüzsüz olduğu söyleniyor Ayarlamak Bir bir çarpanlara ayırma varsa m faktörlerin elementlerin güçleri olduğu Bir. Örneğin, 12 = 4 × 3 olduğundan, 12 setler üzerinde pürüzsüzdür Bir₁ = {4, 3}, Bir₂ = {2, 3} ve ${ displaystyle mathbb {Z}}$ ancak set boyunca düzgün olmaz Bir₃ = {3, 5}, 12 faktör 4 = 2 faktörünü içerdiğinden²içinde olmayan Bir₃.

Seti not edin Bir bir dizi asal faktör olmak zorunda değildir, ancak tipik olarak uygun bir alt küme asal sayıların faktör tabanı nın-nin Dixon'ın çarpanlara ayırma yöntemi ve ikinci dereceden elek. Aynı şekilde, genel sayı alanı eleği pürüzsüzlük kavramını oluşturmak için kullanır. homomorfizm ${ displaystyle phi: mathbb {Z} [ theta] - mathbb {Z} / n mathbb {Z}}$ .^[13]

Ayrıca bakınız

Notlar ve referanslar

^ "Yüksek Matematik Jargonunun Kesin Sözlüğü - Düzgün". Matematik Kasası. 2019-08-01. Alındı 2019-12-12.
^ "P-Düzgün Sayılar veya P-kırılgan Sayı". GeeksforGeeks. 2018-02-12. Alındı 2019-12-12.
^ Weisstein, Eric W. "Düzgün Sayı". mathworld.wolfram.com. Alındı 2019-12-12.
^ Hellman, M. E.; Reyneri, J.M. (1983). Ayrık logaritmaların hızlı hesaplanması GF (q). Kriptolojide Gelişmeler: CRYPTO '82 Proceedings (Ed. D. Chaum, R. Rivest, A. Sherman). sayfa 3–13. doi:10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
^ "Python: Belirli bir sayıya kadar Hamming sayılarını alın ayrıca belirli bir sayının bir Hamming sayısı olup olmadığını kontrol edin". w3resource. Alındı 2019-12-12.
^ "Sorun H: Mütevazı Sayılar". www.eecs.qmul.ac.uk. Alındı 2019-12-12.
^ Sloane, N.J.A. (ed.). "Dizi A002473 (7 düz sayı)". Tam Sayı Dizilerinin Çevrimiçi Ansiklopedisi. OEIS Vakfı.
^ Aaboe, Asger (1965), "Bazı Seleukos matematik tabloları (genişletilmiş karşılıklılar ve normal sayıların kareleri)", Çivi Yazısı Çalışmaları Dergisi, 19 (3): 79–86, doi:10.2307/1359089, JSTOR 1359089, BAY 0191779, S2CID 164195082.
^ Longuet-Higgins, H. C. (1962), "Bir müzik arkadaşına mektup", Müzik İncelemesi (Ağustos): 244–248.
^ Dijkstra, Edsger W. (1981), Hamming'in SASL'deki alıştırması (PDF), Rapor EWD792. Başlangıçta özel olarak dağıtılan el yazısı bir not.
^ Naccache, David; Shparlinski, Igor (17 Ekim 2008). "Bölünebilirlik, Düzgünlük ve Kriptografik Uygulamalar" (PDF). eprint.iacr.org. Alındı 26 Temmuz 2017.f
^ Tanaka, Keisuke; Suga, Yuji (20 Ağustos 2015). Bilgi ve Bilgisayar Güvenliğindeki Gelişmeler: 10. Uluslararası Güvenlik Çalıştayı, IWSEC 2015, Nara, Japonya, 26-28 Ağustos 2015, Bildiriler. Springer. s. 49–51. ISBN 9783319224251.
^ Briggs, Matthew E. (17 Nisan 1998). "Genel Numara Alanı Eleğine Giriş" (PDF). math.vt.edu. Blacksburg, Virginia: Virginia Politeknik Enstitüsü ve Eyalet Üniversitesi. Alındı 26 Temmuz 2017.

Kaynakça

G. Tenenbaum, Analitik ve olasılıklı sayı teorisine giriş, (AMS, 2015) ISBN 978-0821898543
A. Granville, Düzgün sayılar: Hesaplamalı sayı teorisi ve ötesi, Proc. MSRI atölye çalışması, 2008

Dış bağlantılar

Weisstein, Eric W. "Düzgün Sayı". MathWorld.

Tam Sayı Dizilerinin Çevrimiçi Ansiklopedisi (OEIS) listeleri B-küçük için düzgün sayılar Bs:

2 düz sayı: A000079 (2^ben)
3-düzgün sayılar: A003586 (2^ben3^j)
5-düzgün sayılar: A051037 (2^ben3^j5^k)
7 düz sayılar: A002473 (2^ben3^j5^k7^l)
11 düz sayılar: A051038 (vb...)
13 düzgün sayılar: A080197
17 düz sayı: A080681
19-düz sayılar: A080682
23-düzgün sayılar: A080683

[1] "Yüksek Matematik Jargonunun Kesin Sözlüğü - Düzgün". Matematik Kasası. 2019-08-01. Alındı 2019-12-12.

[2] "P-Düzgün Sayılar veya P-kırılgan Sayı". GeeksforGeeks. 2018-02-12. Alındı 2019-12-12.

[3] Weisstein, Eric W. "Düzgün Sayı". mathworld.wolfram.com. Alındı 2019-12-12.

[4] Hellman, M. E.; Reyneri, J.M. (1983). Ayrık logaritmaların hızlı hesaplanması GF (q). Kriptolojide Gelişmeler: CRYPTO '82 Proceedings (Ed. D. Chaum, R. Rivest, A. Sherman). sayfa 3–13. doi:10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.

[5] "Python: Belirli bir sayıya kadar Hamming sayılarını alın ayrıca belirli bir sayının bir Hamming sayısı olup olmadığını kontrol edin". w3resource. Alındı 2019-12-12.

[6] "Sorun H: Mütevazı Sayılar". www.eecs.qmul.ac.uk. Alındı 2019-12-12.

[7] Sloane, N.J.A. (ed.). "Dizi A002473 (7 düz sayı)". Tam Sayı Dizilerinin Çevrimiçi Ansiklopedisi. OEIS Vakfı.

[8] Aaboe, Asger (1965), "Bazı Seleukos matematik tabloları (genişletilmiş karşılıklılar ve normal sayıların kareleri)", Çivi Yazısı Çalışmaları Dergisi, 19 (3): 79–86, doi:10.2307/1359089, JSTOR 1359089, BAY 0191779, S2CID 164195082.

[9] Longuet-Higgins, H. C. (1962), "Bir müzik arkadaşına mektup", Müzik İncelemesi (Ağustos): 244–248.

[10] Dijkstra, Edsger W. (1981), Hamming'in SASL'deki alıştırması (PDF), Rapor EWD792. Başlangıçta özel olarak dağıtılan el yazısı bir not.

[11] Naccache, David; Shparlinski, Igor (17 Ekim 2008). "Bölünebilirlik, Düzgünlük ve Kriptografik Uygulamalar" (PDF). eprint.iacr.org. Alındı 26 Temmuz 2017.f

[12] Tanaka, Keisuke; Suga, Yuji (20 Ağustos 2015). Bilgi ve Bilgisayar Güvenliğindeki Gelişmeler: 10. Uluslararası Güvenlik Çalıştayı, IWSEC 2015, Nara, Japonya, 26-28 Ağustos 2015, Bildiriler. Springer. s. 49–51. ISBN 9783319224251.

[13] Briggs, Matthew E. (17 Nisan 1998). "Genel Numara Alanı Eleğine Giriş" (PDF). math.vt.edu. Blacksburg, Virginia: Virginia Politeknik Enstitüsü ve Eyalet Üniversitesi. Alındı 26 Temmuz 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Bölünebilirliğe dayalı tam sayı kümeleri
Genel Bakış	Tamsayı çarpanlara ayırma Bölen Üniter bölen Bölen işlevi Asal faktör Aritmetiğin temel teoremi
Faktorizasyon formları	önemli Bileşik Yarı suçlu Pronic Sfenik Karesiz Güçlü Mükemmel güç Aşil Pürüzsüz Düzenli Kaba Olağandışı
Sınırlandırılmış bölen toplamları	Mükemmel Neredeyse mükemmel Quasiperfect Çarpma mükemmel Hemiperfect Hiper mükemmel Süper mükemmel Üniter mükemmel İki üniteli çarpma mükemmel Semiperfect Pratik Erdős – Nicolas
Birçok bölenle	Bol İlkel bol Oldukça bol Süper bol Muazzam derecede bol Son derece kompozit Üstün yüksek kompozit Tuhaf
Bölüm dizisi -ilişkili	Dokunulmaz Dostane Sosyal Evli
Baz bağımlı	Equidigital Savurgan Tutumlu Harshad Polidivize edilebilir Smith
Diğer setler	Aritmetik Yetersiz Arkadaş canlısı Yalnız Yüce Harmonik bölen Descartes Yeniden düzenlenebilir Süper mükemmel