Sima számok
A számelmélet területén a sima számok (smooth or friable numbers) vagy n-sima számok olyan egész számok, melyek prímtényezői mind egy megadott számnál (n-nél) kisebb prímszámok. A kifejezést valószínűleg Leonard Adleman alkotta meg.[1] A sima számok különösen fontosak a kriptográfia faktorizációval kapcsolatos alkalmazásaiban. A 2-sima számok egyszerűen kettő hatványai.
Meghatározás
szerkesztésEgy pozitív egész szám B-sima, ha egyetlen prímtényezője sem nagyobb B-nél. Például az 1620 prímtényezős felbontása 22 · 34 · 5; ezért 1620 5-sima, mivel egyetlen prímtényezője sem nagyobb 5-nél. A definíció megengedi, hogy a sima számból egyes kisebb prímtényezők hiányozzanak; például a 10 és a 12 is 5-sima szám, pedig hiányzik belőlük a 3, illetve az 5 mint prímtényező. Az 5-sima számokat reguláris számoknak vagy Hamming-számoknak is hívják; a 7-sima számokat szerény számoknak is hívják, néha pedig erősen összetettnek,[2] bár ez ütközik az erősen összetett számok általánosan elfogadott definíciójával.
Vegyük észre, hogy B nem feltétlenül prím. Ha egy szám legnagyobb prímtényezője p, akkor a szám B-sima bármely B ≥ p esetben. Általában a megadott B prímszám, de összetett szám is lehet. Egy szám akkor és csak akkor B-sima, ha p-sima, ahol p a B-nél nem nagyobb prímszámok közül a legnagyobb.
Alkalmazásai
szerkesztésA sima számok fontos gyakorlati alkalmazást nyernek a különböző gyors Fourier-transzformációs (FFT) algoritmusokban, mint amilyen a Cooley–Tukey-algoritmus, ami egy n nagyságú problémát rekurzívan a prímtényezőinak megfelelő méretű problémákra bont fel. B-sima számok használatával be lehet biztosítani, hogy a rekurzív algoritmus kis prímekre bontja fel a számot, amikre már léteznek hatékony algoritmusok. (A nagy prímszámok kevésbé hatékony algoritmusokat igényelnek, mint amilyen a Bluestein-algoritmus.)
Az 5-sima vagy szabályos számok különleges szerepet játszanak a babiloni matematikában.[3] Fontosak továbbá a zeneelméletben.[4] az ilyen számok hatékony előállítása pedig gyakori tesztfeladat a funkcionális programozásban.[5]
A sima számoknak van néhány alkalmazásuk a kriptográfia területén is.[6] Bár ezek főleg a kriptoanalízist szolgálják (pl. a leggyorsabb ismert faktorizációs algoritmusok), a VSH (very smooth hash) függvény a simaság konstruktív használatára példa, melynek segítségével bizonyíthatóan biztonságos hash függvényt terveztek.
Eloszlásuk
szerkesztésJelölje az x-nél nem nagyobb y-sima egészek számát (De Bruijn-függvény).
Ha a B simasági korlát kicsi és állandó, akkor létezik jó becslés -re:
ahol a -nél nem nagyobb prímek számát jelöli.
Máskülönben, vezessük be az u paramétert, ahol u = log x / log y: tehát, x = yu. Ekkor,
ahol a Dickman-függvény.
Hatványsima számok
szerkesztésTovábbá, az m szám B-hatványsima (B-powersmooth), ha minden m-et osztó prímhatványára igaz, hogy:
- .
Például a 720 (= 24 · 32 · 51) 5-sima, de nem 5-hatványsima (mert több prímhatvány-osztó is nagyobb 5-nél, például vagy ). Elmondható viszont, hogy 16-hatványsima, mivel 720 legnagyobb prímhatványosztója 24 = 16. Természetesen szintén 17-hatványsima, 18-hatványsima, stb.
A B-sima és B-hatványsima számok számelméleti jelentősége például a Pollard-féle p − 1 algoritmusban van. Az ilyen jellegű alkalmazások gyakran „sima számokkal” működnek B specifikálása nélkül; ez úgy értendő, hogy a számok B-hatványsimák valamely nem meghatározott kicsi B számra; ahogy B növekszik, az algoritmus vagy módszer hatékonysága gyors ütemben csökken. Például a diszkrét logaritmus számítására használt Pohlig–Hellman-algoritmus futási ideje B-sima rendű csoportokra O(B1/2).
Kapcsolódó szócikkek
szerkesztésJegyzetek
szerkesztés- ↑ M. E. Hellman, J. M. Reyneri, "Fast computation of discrete logarithms in GF (q)", in Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman), New York: Plenum Press, 1983, p. 3–13, online quote at Google Scholar: "Adleman refers to integers which factor completely into small primes as “smooth” numbers."
- ↑ Sloane's A002473: 7-smooth numbers
- ↑ Aaboe, Asger (1965), "Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)", Journal of Cuneiform Studies 19 (3): 79–86, DOI 10.2307/1359089.
- ↑ Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (no. August): 244–248.
- ↑ Dijkstra, Edsger W. (1981), Hamming's exercise in SASL, Report EWD792. Originally a privately circulated handwitten note, <http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF>.
- ↑ David Naccache, Igor Shparlinski, "Divisibility, Smoothness and Cryptographic Applications", http://eprint.iacr.org/2008/437.pdf
Irodalom
szerkesztés- G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015) ISBN 978-0821898543
- A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008
További információk
szerkesztés- Weisstein, Eric W.: Smooth Number (angol nyelven). Wolfram MathWorld
Az On-Line Encyclopedia of Integer Sequences (OEIS) listázza a B-sima számokat néhány kis B értékre: