Qual é o algoritmo de fatoração mais rápido?

Eu escrevi um programa que tenta encontrar Pares Amigáveis. Isso requer encontrar as sums dos divisores de números apropriados.

Aqui está o meu método sumOfDivisors() atual:

 int sumOfDivisors(int n) { int sum = 1; int bound = (int) sqrt(n); for(int i = 2; i <= 1 + bound; i++) { if (n % i == 0) sum = sum + i + n / i; } return sum; } 

Então eu preciso fazer muita fatoração e isso está começando a se tornar o verdadeiro gargalo no meu aplicativo. Eu digitei um número enorme no MAPLE e o considerei insanamente rápido.

Qual é um dos algoritmos de fatoração mais rápidos?

Puxado diretamente da minha resposta para esta outra pergunta .

O método funcionará, mas será lento. “Qual é o tamanho dos seus números?” determina o método a usar:

  • Menos de 2 ^ 16 ou mais: Tabela de consulta.
  • Menos de 2 ^ 70 ou mais: modificação de Richard Brent do algoritmo rho de Pollard .
  • Menos que 10 ^ 50: fatoração da curva elíptica de Lenstra
  • Menos de 10 ^ 100: peneira quadrática
  • Mais de 10 ^ 100: Peneira de campo com número geral

A questão do título (e da última linha) parece ter pouco a ver com o corpo real da questão. Se você está tentando encontrar pares amigáveis, ou calcular a sum de divisores para muitos números, então fatorar separadamente cada número (mesmo com o algoritmo mais rápido possível) é uma maneira absolutamente ineficiente de fazê-lo.

A function sum dos divisores , σ(n) = (sum of divisors of n) , é uma function multiplicativa : para relativamente primos m e n, temos σ(mn) = σ(m)σ(n) , então

σ (p 1 k 1 … p r k r ) = [(p 1 k 1 +1 -1) / (p 1 -1)]… [(p r k r +1 -1) / (p r -1 )].

Assim, você usaria qualquer peneira simples (por exemplo, uma versão aumentada da peneira de Eratóstenes ) para encontrar os primos até n e, no processo, a fatoração de todos os números até n. (Por exemplo, ao fazer sua peneira, armazene o menor fator primo de cada n. Então, você poderá fatorizar qualquer número n por iteração.) Isso seria mais rápido (geral) do que usar qualquer algoritmo de fatoração separado várias vezes.

BTW: várias listas conhecidas de pares amigáveis ​​já existem (veja, por exemplo, aqui e os links no MathWorld ) – então você está tentando estender o registro, ou fazer isso apenas por diversão?

Algoritmo de Shor: http://en.wikipedia.org/wiki/Shor%27s_algorithm

Claro que você precisa de um computador quântico: D

Gostaria de sugerir a partir do mesmo algoritmo usado no Maple, o Quadratic Sieve .

  1. Escolha o seu número ímpar n para fatorar,
  2. Escolha um número natural k
  3. Pesquise todos p <= k para que k ^ 2 não seja congruente com (n mod p) para obter um fator base B = p1, p2, …, pt ,
  4. A partir do r > chão (n), procure pelo menos t + 1 valores de modo que y ^ 2 = r ^ 2 – n todos tenham apenas fatores em B,
  5. Para cada y1 , y2 , …, y (t + 1) calculado, você gera um vetor v (yi) = (e1, e2, …, et) onde ei é calculado reduzindo-se o módulo 2 o expoente pi em yi ,
  6. Use a Eliminação Gaussiana para encontrar alguns dos vetores que sumdos fornecem um vetor nulo
  7. Defina x como o produto de ri relacionado ao yi encontrado na etapa anterior e configure y como p1 ^ a * p2 ^ b * p3 ^ c * .. * pt ^ z em que expoentes são a metade dos expoentes encontrados na fatoração de yi
  8. Calcule d = mcd (xy, n) , se 1 então d é um fator não-trivial de n , caso contrário, inicie a partir da etapa 2, escolhendo um k maior.

O problema sobre esses algoritmos é que eles realmente implicam muita teoria em cálculo numérico.

Este é um papel da Factorização Inteira em Maple.

“A partir de algumas instruções muito simples -” tornar a fatoração de números inteiros mais rápida no Maple “- implementamos o algoritmo de fatoração Quadratic Sieve em uma combinação de Maple e C …”

http://www.cecm.sfu.ca/~pborwein/MITACS/papers/percival.pdf

Depende do tamanho dos seus números. Se você está procurando por pares amigáveis, você está fazendo muitas fatorações, então a chave pode não ser fatorar o mais rápido possível, mas compartilhar o máximo de trabalho possível entre diferentes chamadas. Para acelerar a divisão de testes, você pode observar a memorização e / ou precalcular os primos até a raiz quadrada do maior número de interesse. É mais rápido obter a fatoração primária e, em seguida, calcular a sum de todos os fatores a partir dela, do que percorrer todo o caminho até o sqrt (n) para cada número.

Se você está procurando por pares amigáveis ​​realmente grandes, digamos, maiores que 2 ^ 64, então, em um pequeno número de máquinas, você não pode fazê-lo fatorizando cada número, não importa quão rápido seja sua fatoração. Os atalhos que você está usando para encontrar candidatos podem ajudá-lo a considerá-los.

Uma implementação de tabela de consulta mais 2015 C ++ versão 2 27 para 1 GB de memory:

 #include  // cerr, cout, and NULL #include  // memcpy() #define uint unsigned __int32 uint *factors; const uint MAX_F=134217728; // 2^27 void buildFactors(){ factors=new (nothrow) uint [(MAX_F+1)*2]; // 4 * 2 * 2^27 = 2^30 = 1GB if(factors==NULL)return; // not able to allocate enough free memory int i; for(i=0;i<(MAX_F+1)*2;i++)factors[i]=0; //Sieve of Eratosthenese factors[1*2]=1; factors[1*2+1]=1; for(i=2;i*i<=MAX_F;i++){ for(;factors[i*2] && i*i<=MAX_F;i++); factors[i*2]=1; factors[i*2+1]=i; for(int j=2;i*j<=MAX_F;j++){ factors[i*j*2]=i; factors[i*j*2+1]=j; } } for(;i<=MAX_F;i++){ for(;i<=MAX_F && factors[i*2];i++); if(i>MAX_F)return; factors[i*2]=1; factors[i*2+1]=i; } } uint * factor(uint x, int &factorCount){ if(x > MAX_F){factorCount=-1;return NULL;} uint tmp[70], at=x; int i=0; while(factors[at*2]>1){ tmp[i++]=factors[at*2]; cout<<"at:"< 

Atualizar: ou sacrificar alguma simplicidade para um pouco mais de intervalo apenas após 2 28

 #include  // cerr, cout, and NULL #include  // memcpy(), memset() //#define dbg(A) A #ifndef dbg #define dbg(A) #endif #define uint unsigned __int32 #define uint8 unsigned __int8 #define uint16 unsigned __int16 uint * factors; uint8 *factors08; uint16 *factors16; uint *factors32; const uint LIMIT_16 = 514; // First 16-bit factor, 514 = 2*257 const uint LIMIT_32 = 131074;// First 32-bit factor, 131074 = 2*65537 const uint MAX_FACTOR = 268501119; //const uint64 LIMIT_64 = 8,589,934,594; // First 64-bit factor, 2^33+1 const uint TABLE_SIZE = 268435456; // 2^28 => 4 * 2^28 = 2^30 = 1GB 32-bit table const uint o08=1, o16=257 ,o32=65665; //o64=4294934465 // TableSize = 2^37 => 8 * 2^37 = 2^40 1TB 64-bit table // => MaxFactor = 141,733,953,600 /* Layout of factors[] array * Indicies(32-bit) i Value Size AFactorOf(i) * ---------------- ------ ---------- ---------------- * factors[0..128] [1..513] 8-bit factors08[i-o08] * factors[129..65408] [514..131073] 16-bit factors16[i-o16] * factors[65409..268435455] [131074..268501119] 32-bit factors32[i-o32] * * Note: stopping at i*i causes AFactorOf(i) to not always be LargestFactor(i) */ void buildFactors(){ dbg(cout<<"Allocating RAM"<0); for(;i*j0); for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i; } }i--; dbg(cout<<"Setting: 32-Bit Values"<MAX_FACTOR)return; factors32[i-o32]=1; } } uint * factor(uint x, int &factorCount){ if(x > MAX_FACTOR){factorCount=-1;return NULL;} uint tmp[70], at=x; int i=0; while(at>=LIMIT_32 && factors32[at-o32]>1){ tmp[i++]=factors32[at-o32]; dbg(cout<<"at32:"<=LIMIT_16 && factors16[at-o16]>1){ tmp[i++]=factors16[at-o16]; dbg(cout<<"at16:"<1){ tmp[i++]=factors08[at-o08]; dbg(cout<<"at08:"< MAX_FACTOR)return -1; if(x < LIMIT_16) return factors08[x-o08]; if(x < LIMIT_32) return factors16[x-o16]; return factors32[x-o32]; } void main(){ cout<<"Loading factors lookup table"<