Número pla
En teoria de números, un número pla és un sancer que pot factorizarse completament en número primer menuts. El terme sembla haver segut acunyat per Leonard Adleman.[1] Els números plans són d'especial importància en criptografia basada en factorisació.
Definició
Un sancer positiu es diu B-pla si cap dels seus factors primers és major que B. Per eixemple, 1,620 té la factorisació primera 22 × 34 × 5; per lo tant, 1,620 és 5-pla puix cap dels seus factors primers és major que 5. Val la pena notar que esta definició inclou números que carixen d'alguns dels cosins menors. Per eixemple, tant 10 com 12 són 5-pla, no obstant el fet que els falta els factors primers 3 i 5 respectivament. Els números 5-pla també es diuen números regulars o números Hamming; els números 7-pla a voltes es diuen[per] altament composts, encara que esta denominació es confon en número altament compost.
Note's que B no té que ser un factor primer. Si el major dels factors primers d'un número és p llavors el número és B-pla per a tot B ≥ p. Usualment B està donat com a primer, pero els número compost funcionen igualment. Un número és B-pla si i solament si és p-pla, a on p és el major cosí menor o igual a B.
Aplicacions
Una important aplicació pràctica dels números plans es dona en els algoritmes de la transformada ràpida de Fourier (FFT) com l'algoritme FFT Cooley–Tukey, que opera recursivamente descomponent un problema d'un tamany donat n en problemes del tamany dels seus factors. Utilisant números B-pla, s'assegura que els casos base d'esta recursió són primers menuts, per als quals existixen algoritmes eficients (cosins grans requerixen algoritmes menys-eficients com l'algoritme FFT Bluestein.)
Els números 5-pla o números regulars juguen un paper especial en la matemàtica babilònica.[2] També són importants en teoria musical,[3] (vore Llímit) i el problema de generar estos números eficientemente ha segut utilisat com a problema de prova en programació funcional.[4]
Els números plans tenen numeroses aplicacions en criptografia.[5] Encara que la majoria de les aplicacions involucren criptoanálisis, la funció hash VSH és un eixemple d'ús constructiu de suavitat per a obtindre un disseny segur provable.
Notes
- ↑ 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 es referix a sancers que es factorizan completament en chicotets cosins com a números "plans".
- ↑ .
- ↑ .
- ↑ .
- ↑ David Naccache, Igor Shparlinski, "Divisibility, lisoness and Cryptographic Applications", http://eprint.iacr.org/2008/437.pdf
Referències
- G. Tenenbaum, Introduction to analytic and probabilistic number theory, (CUP, 1995) ISBN 0-521-41261-7
- A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2004
- Este artícul conté una traducció derivada de «Número liso» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.