Glat antal - Smooth number

I talteori er et n- glat (eller n- frit ) tal et heltal, hvis primære faktorer alle er mindre end eller lig med n . For eksempel er et 7-glat tal et tal, hvis hver primfaktor højst er 7, så 49 = 7 ² og 15750 = 2 × 3 ² × 5 ³ × 7 er begge 7-glatte, mens 11 og 702 = 2 × 3 ³ × 13 er ikke 7-glatte. Udtrykket ser ud til at være opfundet af Leonard Adleman . Glatte tal er især vigtige i kryptografi , som er afhængig af faktorisering af heltal. De 2-glatte tal er kun kræfterne på 2 , mens 5-glatte tal er kendt som almindelige tal .

Definition

Et positivt heltal kaldes B - glat , hvis ingen af de vigtigste faktorer er større end B . For eksempel har 1.620 primfaktorisering 2 ² × 3 ⁴ × 5; derfor er 1.620 5 glat, fordi ingen af ​​dens primfaktorer er større end 5. Denne definition inkluderer tal, der mangler nogle af de mindre primfaktorer; for eksempel er både 10 og 12 5-glatte, selvom de går glip af de primære faktorer henholdsvis 3 og 5. Alle 5-glatte tal har formen 2 ^a × 3 ^b × 5 ^c , hvor a , b og c er ikke-negative heltal.

5-glatte tal kaldes også almindelige tal eller Hamming-numre; 7-glatte tal kaldes også ydmyge tal og undertiden kaldes meget sammensatte , selv om dette er i konflikt med en anden betydning af stærkt sammensatte tal .

Her skal du bemærke, at B i sig selv ikke er påkrævet at vises blandt faktorerne i et B- glat tal. Hvis den største primfaktor for et tal er p, er tallet B- glat for ethvert B ≥ p . I mange scenarier B er primtal , men sammensatte tal er tilladt så godt. En række er B -glat hvis og kun hvis det er p -glat, hvor p er den største primtal mindre end eller lig med B .

Ansøgninger

En vigtig praktisk anvendelse af glatte tal er de hurtige Fourier-transformeringsalgoritmer (såsom Cooley – Tukey FFT-algoritmen ), som fungerer ved rekursivt at nedbryde et problem af en given størrelse n til problemer på størrelse med dens faktorer. Ved at bruge B- glatte tal sikrer man, at basissagerne for denne rekursion er små primtal, for hvilke der findes effektive algoritmer. (Store primstørrelser kræver mindre effektive algoritmer som f.eks. Bluesteins FFT-algoritme .)

5-glatte eller regelmæssige tal spiller en særlig rolle i babylonisk matematik . De er også vigtige inden for musikteori (se Limit (musik) ), og problemet med at generere disse tal effektivt er blevet brugt som et testproblem til funktionel programmering .

Glatte tal har et antal applikationer til kryptografi. Mens de fleste applikationer er centreret omkring kryptanalyse (f.eks. Den hurtigste kendte heltal-faktoriseringsalgoritmer , for eksempel: Generelt nummerfelt-sigte- algoritme), er VSH- hash-funktionen et andet eksempel på en konstruktiv brug af glathed for at opnå et beviseligt sikkert design .

Fordeling

Lad angive antallet af y- glatte heltal mindre end eller lig med x (de Bruijn-funktionen). ${\ displaystyle \ Psi (x, y)}$

Hvis glathedsgrænsen B er fast og lille, er der et godt skøn for : ${\ displaystyle \ Psi (x, B)}$

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

hvor angiver antallet af primtal, der er mindre end eller lig med . ${\ displaystyle \ pi (B)}$ ${\ displaystyle B}$

Ellers definerer du parameter u som u  = log  x  / log  y : det vil sige x  =  y ^u . Derefter,

${\ displaystyle \ Psi (x, y) = x \ cdot \ rho (u) + O \ left ({\ frac {x} {\ log y}} \ right)}$

hvor er Dickman-funktionen . ${\ displaystyle \ rho (u)}$

Den gennemsnitlige størrelse af den glatte del af et antal af en given størrelse er kendt som , og det vides at henfalde meget langsommere end . ${\ displaystyle \ zeta (u)}$${\ displaystyle \ rho (u)}$

For enhver k vil næsten alle naturlige tal ikke være k- glatte.

Powersmooth tal

Yderligere kaldes m B - powersmooth (eller B - ultrafriable ), hvis alle primære kræfter, der deler m, opfylder: ${\ displaystyle p ^ {\ nu}}$

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

For eksempel er 720 (2 ⁴ × 3 ² × 5 ¹ ) 5-glat, men ikke 5-powersmooth (fordi der er flere primære kræfter større end 5, fx og ). Det er 16-powersmooth, da dets største primfaktor power er 2 ⁴  = 16. Nummeret er også 17-powersmooth, 18-powersmooth osv. ${\ displaystyle 3 ^ {2} = 9 \ nleq 5}$${\ displaystyle 2 ^ {4} = 16 \ nleq 5}$

B -smooth- og B -powersmooth-numre har applikationer i talteori, såsom i Pollards p  -1-algoritme og ECM . Sådanne applikationer siges ofte at arbejde med "glatte tal" uden B angivet; dette betyder, at de involverede tal skal være B- powermooth, for noget uspecificeret lille antal B. A s B stiger, udførelsen af ​​den pågældende algoritme eller metode nedbrydes hurtigt. For eksempel har Pohlig – Hellman-algoritmen til beregning af diskrete logaritmer en kørselstid på O ( B ^1/2 ) - for grupper af B- glat rækkefølge .

Glat over et sæt A

Desuden m siges at være glatte over et sæt A , hvis der findes en faktorisering af m , hvor faktorerne er potenser af elementer i A . Da f.eks. 12 = 4 × 3, er 12 glat over sæt A ₁ = {4, 3}, A ₂ = {2, 3}, og det ville dog ikke være glat over sæt A ₃ = {3 , 5}, som 12 indeholder faktoren 4 = 2 ² , som ikke er i A ₃ . ${\ displaystyle \ mathbb {Z}}$

Bemærk, at sæt A ikke behøver at være et sæt primfaktorer, men det er typisk en ordentlig delmængde af primtalerne set i faktorbasen af Dixons faktoriseringsmetode og den kvadratiske sigte . Ligeledes er det, hvad det generelle talfelt sigter bruger til at opbygge sin forestilling om glathed under homomorfismen . ${\ displaystyle \ phi: \ mathbb {Z} [\ theta] \ to \ mathbb {Z} / n \ mathbb {Z}}$

Se også

• Meget sammensat tal
• Groft antal
• Runde nummer
• Størmers sætning
• Usædvanligt nummer

Noter og referencer

Bibliografi

• G. Tenenbaum, Introduktion til analytisk og sandsynlig talteori , (AMS, 2015) ISBN   978-0821898543
• A. Granville , glatte tal: Computational number theory and beyond , Proc. af MSRI-workshop, 2008

eksterne links

• Weisstein, Eric W. "Smooth Number" . MathWorld .

Den oeis (OEIS) lister B -glat numre for små B s:

• 2-glatte tal: A000079 (2 ⁱ )
• 3-glatte tal: A003586 (2 ⁱ 3 ^j )
• 5-glatte tal: A051037 (2 ⁱ 3 ^j 5 ^k )
• 7-glatte tal: A002473 (2 ⁱ 3 ^j 5 ^k 7 ^l )
• 11-glatte tal: A051038 (osv ...)
• 13-glatte tal: A080197
• 17 glatte tal: A080681
• 19 glatte tal: A080682
• 23 glatte tal: A080683