Divisão de teste - Trial division

A divisão experimental é o mais trabalhoso, mas mais fácil de entender dos algoritmos de fatoração de inteiros . A ideia essencial por trás dos testes de divisão experimental para ver se um inteiro n , o inteiro a ser fatorado, pode ser dividido por cada número que for menor que n . Por exemplo, para o inteiro n = 12 , os únicos números que o dividem são 1, 2, 3, 4, 6, 12. Selecionar apenas as maiores potências de primos nesta lista resulta em 12 = 3 × 4 = 3 × 2 ² .

A divisão experimental foi descrita pela primeira vez por Fibonacci em seu livro Liber Abaci (1202).

Método

Dado um inteiro n ( n refere-se a "o inteiro a ser fatorado"), a divisão experimental consiste em testar sistematicamente se n é divisível por qualquer número menor. Claramente, só vale a pena testar fatores candidatos menores que n , e em ordem de dois para cima, porque um n arbitrário tem mais probabilidade de ser divisível por dois do que por três, e assim por diante. Com esta ordenação, não há sentido em testar a divisibilidade por quatro se o número já tiver sido determinado como não divisível por dois, e assim por diante por três e qualquer múltiplo de três, etc. Portanto, o esforço pode ser reduzido selecionando apenas primos números como fatores candidatos. Além disso, os fatores de teste não precisam ir mais longe do que porque, se n é divisível por algum número p , então n = p × q e se q fosse menor que p , n teria sido detectado anteriormente como sendo divisível por q ou por um primo fator de q . ${\ displaystyle \ scriptstyle {\ sqrt {n}}}$

Um limite definido para os fatores primários é possível. Suponha que P _i seja o i 'ésimo primo, de modo que P ₁ = 2, P ₂ = 3, P ₃ = 5, etc. Então, o último número primo que vale a pena testar como um possível fator de n é P _i, onde P ² _{i  + 1} > n ; igualdade aqui significaria que P _{i  + 1} é um fator. Assim, testar com 2, 3 e 5 é suficiente até n = 48, não apenas 25, porque o quadrado do próximo primo é 49, e abaixo de n = 25 apenas 2 e 3 são suficientes. Se a raiz quadrada de n for integral, então é um fator en é um quadrado perfeito .

Um exemplo do algoritmo de divisão de teste, usando números inteiros sucessivos como fatores de teste, é o seguinte (em Python ):

def trial_division(n: int) -> List[int]:
    """Return a list of the prime factors for a natural number."""
    a = []               # Prepare an empty list.
    f = 2                # The first possible factor.    
    while n > 1:         # While n still has remaining factors...
        if n % f == 0:   # The remainder of n divided by f might be zero.        
            a.append(f)  # If so, it divides n. Add f to the list.
            n //= f       # Divide that factor out of n.
        else:            # But if f is not a factor of n,
            f += 1       # Add one to f and try again.
    return a             # Prime factors may be repeated: 12 factors to 2,2,3.

Ou 2x mais eficiente:

def trial_division(n: int) -> List[int]:
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
    # Only odd number is possible
    return a

Essas versões de divisão experimental têm a garantia de encontrar um fator de n se houver um, uma vez que verificam todos os fatores possíveis de n - e se n for um número primo, isso significa fatores de tentativa até n . Assim, se o algoritmo encontrar apenas um fator, n, é prova de que n é primo . Se mais de um fator for encontrado, então n é um número inteiro composto . Uma maneira computacionalmente mais vantajosa de dizer isso é, se qualquer primo cujo quadrado não exceda n o divide sem um resto, então n não é primo.

Abaixo está a versão C ++ (sem quadratura de f)

template <class T, class U>
vector<T> TrialDivision(U n)
{
    vector<T> v; T f;
    f = 2;
    while (n % 2 == 0) { v.push_back(f); n /= 2; }
    f = 3;
    while (n % 3 == 0) { v.push_back(f); n /= 3; }
    f = 5;
    T ac = 9, temp = 16;
    do {
        ac += temp; // Assume addition does not cause overflow with U type
        if (ac > n) break; 
        if (n % f == 0) {
            v.push_back(f);
            n /= f;
            ac -= temp;
        }
        else { 
            f += 2;
            temp += 8;
        }
    } while (1);
    if (n != 1) v.push_back(n);
    return v;
}

Velocidade

No pior caso , a divisão experimental é um algoritmo trabalhoso. Para um número de base de 2 n dígitos a , se começar de dois e chegar apenas à raiz quadrada de a , o algoritmo requer

${\ displaystyle \ pi (2 ^ {n / 2}) \ approx {2 ^ {n / 2} \ over \ left ({\ frac {n} {2}} \ right) \ ln 2}}$

divisões de teste, onde denota a função de contagem de primos, o número de primos menor que x . Isso não leva em consideração a sobrecarga do teste de primalidade para obter os números primos como fatores candidatos. Uma tabela útil não precisa ser grande: P (3512) = 32749, o último primo que se encaixa em um inteiro com sinal de dezesseis bits e P (6542) = 65521 para inteiros de dezesseis bits sem sinal. Isso seria suficiente para testar a primalidade para números até 65537 ² = 4.295.098.369. Preparar tal mesa (geralmente por meio do Crivo de Eratóstenes ) só valeria a pena se muitos números fossem testados. Se, em vez disso, uma variante for usada sem o teste de primalidade, mas simplesmente dividindo por cada número ímpar menor que a raiz quadrada o número de base 2 n dígitos a , primo ou não, pode levar até cerca de: ${\ displaystyle \ scriptstyle \ pi (x)}$

${\ displaystyle 2 ^ {n / 2}}$

Em ambos os casos, o tempo necessário aumenta exponencialmente com os dígitos do número.

Mesmo assim, este é um método bastante satisfatório, considerando que mesmo os algoritmos mais conhecidos possuem crescimento exponencial no tempo. Para um escolhido uniformemente ao acaso a partir de inteiros de um determinado comprimento, há 50% de chance de que 2 seja um fator de a e 33% de chance de que 3 seja um fator de a , e assim por diante. Pode ser mostrado que 88% de todos os inteiros positivos têm um factor abaixo de 100 e que 92% têm um factor sob 1000. Assim, quando confrontados com uma grande arbitrário um , ele é útil para verificar a existência de divisibilidade por os pequenos números primos, uma vez que para , na base 2 . ${\ displaystyle a = 1000}$${\ displaystyle n = 10}$

No entanto, os números de muitos dígitos que não têm fatores nos primos pequenos podem levar dias ou meses para serem considerados na divisão de teste. Nesses casos, outros métodos são usados, como a peneira quadrática e a peneira de campo de número geral (GNFS). Como esses métodos também têm crescimento de tempo superpolinomial, um limite prático de n dígitos é alcançado muito rapidamente. Por esta razão, na criptografia de chave pública , os valores de a são escolhidos para ter grandes fatores primos de tamanho semelhante, de modo que não possam ser fatorados por qualquer método conhecido publicamente em um período de tempo útil em qualquer sistema de computador disponível ou cluster de computador, como supercomputadores e grades de computador . O maior número de grau de criptografia fatorado é RSA-250 , um número de 250 dígitos, usando o GNFS e recursos de vários supercomputadores. O tempo de execução foi de 2.700 anos centrais.

Referências

• Childs, Lindsay N. (2009). Uma introdução concreta à álgebra superior . Textos de Graduação em Matemática (3ª ed.). New York, NY: Springer-Verlag . ISBN 978-0-387-74527-5. Zbl  1165.00002 .
• Crandall, Richard ; Pomerance, Carl (2005). Números primos. Uma perspectiva computacional (2ª ed.). New York, NY: Springer-Verlag . ISBN 0-387-25282-7. Zbl  1088.11001 .

links externos

• Calculadora rápida de fatores primários de JavaScript usando divisão de teste . Pode lidar com números até cerca de 2 ⁵³
• Divisão de testes em Java, C e JavaScript (em português)