Sima számok
A számelmélet területén a sima számok (smooth or friable numbers) olyan egész számok, melyek prímtényezői mind kis prímszámok. A kifejezést valószínűleg Leonard Adleman alkotta meg. 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
Egy 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, 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
A 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. Fontosak továbbá a zeneelméletben. az ilyen számok hatékony előállítása pedig gyakori tesztfeladat a funkcionális programozásban.

A sima számoknak van néhány alkalmazásuk a kriptográfia területén is. 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
Jelö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
Tová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 (243251) 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
Durva számok
Størmer-tétel
Erősen összetett számok

Jegyzetek

Irodalom
 G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015) 
 A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008

További információk
 
Az On-Line Encyclopedia of Integer Sequences (OEIS) listázza a B-sima számokat néhány kis B értékre:
 2-sima számok: A000079 (2i)
 3-sima számok: A003586 (2i3j)
 5-sima számok: A051037 (2i3j5k)
 7-sima számok: A002473 (2i3j5k7l)
 11-sima számok: A051038 (etc...)
 13-sima számok: A080197
 17-sima számok: A080681
 19-sima számok: A080682
 23-sima számok: A080683

Analitikus számelmélet
Nevezetes számsorozatok
A számelmélet területén a sima számok ( smooth or friable numbers ) olyan egész számok , melyek prímtényezői mind kis prímszámok . A kifejezést valószínűleg Leonard Adleman alkotta meg . A sima számok különösen fontosak a kriptográfia faktorizációval kapcsolatos alkalmazásaiban . Asima számok egyszerűen kettő hatványai . Meghatározás Egy pozitív egész szám B-sima , ha egyetlen prímtényezője sem nagyobb B-nél . Például azprímtényezős felbontása · · ezért5-sima , mivel egyetlen prímtényezője sem nagyobbnél . A definíció megengedi , hogy a sima számból egyes kisebb prímtényezők hiányozzanak ; például aés aissima szám , pedig hiányzik belőlük a illetve azmint prímtényező . Azsima számokat reguláris számoknak vagy Hamming-számoknak is hívják ; asima számokat szerény számoknak is hívják , néha pedig erősen összetettnek , 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 A 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 . ) Azsima vagy szabályos számok különleges szerepet játszanak a babiloni matematikában . Fontosak továbbá a zeneelméletben . az ilyen számok hatékony előállítása pedig gyakori tesztfeladat a funkcionális programozásban . A sima számoknak van néhány alkalmazásuk a kriptográfia területén is . 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 Jelö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 Tová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( 243251) sima , de nemhatványsima ( mert több prímhatvány-osztó is nagyobbnél , például vagy ) . Elmondható viszont , hogyhatványsima , mivellegnagyobb prímhatványosztója= Természetesen szinténhatványsima ,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 −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 Durva számok Størmer-tétel Erősen összetett számok Jegyzetek Irodalom G. Tenenbaum , Introduction to analytic and probabilistic number theory , ( AMS , A . Granville , Smooth numbers : Computational number theory and beyond , Proc. of MSRI workshop , További információk Az On-Line Encyclopedia of Integer Sequences ( OEIS ) listázza a B-sima számokat néhány kis B értékre : sima számok : A000079 ) sima számok : A0035863j ) sima számok : A0510373j5k ) sima számok : A0024733j5k7l ) sima számok : A051038 ( etc... ) sima számok : A080197 sima számok : A080681 sima számok : A080682 sima számok : A080683 Analitikus számelmélet Nevezetes számsorozatok