Número suave - Smooth number

Em teoria número , um n -Smooth (ou n -friable ) número é um número inteiro cujo factores primos são tudo menos do que ou igual a n . Por exemplo, um número 7-smooth é um número em que cada fator primo é no máximo 7, então 49 = 7 ² e 15750 = 2 × 3 ² × 5 ³ × 7 são ambos 7-smooth, enquanto 11 e 702 = 2 × 3 ³ × 13 não são 7-suaves. O termo parece ter sido cunhado por Leonard Adleman . Números suaves são especialmente importantes na criptografia , que depende da fatoração de inteiros. Os números de 2 suaves são apenas potências de 2 , enquanto os números de 5 suaves são conhecidos como números regulares .

Definição

A positivo inteiro é chamado B - suavizar se nenhum de seus fatores primos é maior que B . Por exemplo, 1.620 tem fatoração principal 2 ² × 3 ⁴ × 5; portanto, 1.620 é 5-smooth porque nenhum de seus fatores primos é maior que 5. Essa definição inclui números que não possuem alguns dos fatores primos menores; por exemplo, tanto 10 quanto 12 são 5-smooth, embora eles deixem de lado os fatores primos 3 e 5, respectivamente. Todos os números suaves de 5 têm a forma 2 ^a × 3 ^b × 5 ^c , onde a , b e c são inteiros não negativos.

Números lisos de 5 também são chamados de números regulares ou números de Hamming; Números lisos também são chamados de números humildes e às vezes chamados de altamente compostos , embora isso entre em conflito com outro significado de números altamente compostos .

Aqui, observe que o próprio B não precisa aparecer entre os fatores de um número B- suave. Se o maior fator primo de um número for p, então o número é B- suave para qualquer B ≥ p . Em muitos cenários, B é primo , mas números compostos também são permitidos. Um número é B -Smooth se e somente se é p -Smooth, onde p é o maior primo menor ou igual a B .

Formulários

Uma importante aplicação prática de números suaves são os algoritmos de transformada rápida de Fourier (FFT) (como o algoritmo Cooley – Tukey FFT ), que opera quebrando recursivamente um problema de um determinado tamanho n em problemas do tamanho de seus fatores. Ao usar números B- suaves, garante-se que os casos-base dessa recursão sejam pequenos primos, para os quais existem algoritmos eficientes. (Grandes tamanhos primos requerem algoritmos menos eficientes, como o algoritmo FFT de Bluestein .)

Os números 5-suaves ou regulares desempenham um papel especial na matemática babilônica . Eles também são importantes na teoria musical (consulte Limite (música) ), e o problema de gerar esses números de forma eficiente foi usado como um problema de teste para a programação funcional .

Números suaves têm várias aplicações para criptografia. Enquanto a maioria das aplicações gira em torno da criptoanálise (por exemplo, os algoritmos de fatoração de inteiros mais rápidos conhecidos , por exemplo: Algoritmo de peneira de campo numérico geral ), a função hash VSH é outro exemplo de um uso construtivo de suavidade para obter um design comprovadamente seguro .

Distribuição

Deixe denotar o número de y- inteiros suaves menores ou iguais a x (a função de Bruijn). ${\ displaystyle \ Psi (x, y)}$

Se o limite de suavidade B for fixo e pequeno, há uma boa estimativa para : ${\ displaystyle \ Psi (x, B)}$

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

onde denota o número de primos menor ou igual a . ${\ displaystyle \ pi (B)}$ ${\ displaystyle B}$

Caso contrário, defina o parâmetro u como u  = log  x  / log  y : ou seja, x  =  y ^u . Então,

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

onde está a função Dickman . ${\ displaystyle \ rho (u)}$

O tamanho médio da parte lisa de um número de determinado tamanho é conhecido como e decai muito mais lentamente do que . ${\ displaystyle \ zeta (u)}$${\ displaystyle \ rho (u)}$

Para qualquer k , quase todos os números naturais não serão k- suaves.

Números poderosos

Além disso, m é chamado de B - powersmooth (ou B - ultrafriável ) se todas as potências primárias dividindo m satisfizerem: ${\ displaystyle p ^ {\ nu}}$

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

Por exemplo, 720 (2 ⁴ × 3 ² × 5 ¹ ) é 5-smooth, mas não 5-powersmooth (porque há várias potências principais maiores que 5, por exemplo , e ). É 16-powersmooth, pois sua maior potência do fator primo é 2 ⁴  = 16. O número também é 17-powersmooth, 18-powersmooth, etc. ${\ displaystyle 3 ^ {2} = 9 \ nleq 5}$${\ displaystyle 2 ^ {4} = 16 \ nleq 5}$

B -Smooth e B números -powersmooth têm aplicações em teoria número, tais como em de Pollard p  - 1 algoritmo e ECM . Freqüentemente, diz-se que tais aplicativos funcionam com "números suaves", sem B especificado; isto significa que os números envolvidos devem ser B -powermooth, para algum número pequeno não especificado B. A s B aumenta, o desempenho do algoritmo ou método em questão degrada rapidamente. Por exemplo, o algoritmo Pohlig-Hellman para calcular logaritmos discretos tem um tempo de execução de O ( B ^1/2 ) - para grupos de ordem B- suave .

Suavizar sobre um conjunto A

Além disso, m é dito para ser lisa ao longo de um conjunto Um caso de existir um fatoração de m em que os factores são potências de elementos em um . Por exemplo, uma vez que 12 = 4 × 3, 12 é suave sobre os conjuntos A ₁ = {4, 3}, A ₂ = {2, 3} e , no entanto, não seria suave sobre o conjunto A ₃ = {3 , 5}, pois 12 contém o fator 4 = 2 ² , que não está em A ₃ . ${\ displaystyle \ mathbb {Z}}$

Observe que o conjunto A não precisa ser um conjunto de fatores primos, mas é tipicamente um subconjunto adequado dos primos, conforme visto na base do fator do método de fatoração de Dixon e na peneira quadrática . Da mesma forma, é o que a peneira de campo numérico geral utiliza para construir sua noção de suavidade, sob o homomorfismo . ${\ displaystyle \ phi: \ mathbb {Z} [\ theta] \ to \ mathbb {Z} / n \ mathbb {Z}}$

Veja também

• Número altamente composto
• Número aproximado
• Número redondo
• Teorema de Størmer
• Número incomum

Notas e referências

Bibliografia

• G. Tenenbaum, Introdução à teoria analítica e probabilística dos números , (AMS, 2015) ISBN   978-0821898543
• A. Granville , Smooth numbers: Computational number theory and beyond , Proc. do workshop MSRI, 2008

links externos

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

A Enciclopédia On-Line de Sequências Inteiras (OEIS) lista números B- suaves para B s pequenos :

• Números suaves de 2: A000079 (2 ⁱ )
• Números lisos: A003586 (2 ⁱ 3 ^j )
• Números lisos de 5: A051037 (2 ⁱ 3 ^j 5 ^k )
• Números de 7 lisos: A002473 (2 ⁱ 3 ^j 5 ^k 7 ^l )
• 11 números suaves: A051038 (etc ...)
• 13 números suaves: A080197
• 17 números suaves: A080681
• 19 números suaves: A080682
• 23 números suaves: A080683