Turbinando a fatoração de fermat

Podemos turbinar a fatoração de Fermat, evitando  a computação das raízes quadradas de de todos $a^2 - N$.

Dado um valor de m, podemos reduzir a quantidade de números que devem ser computados.

Por exemplo, os quadrados perfeitos módulo 20 terminam em 0,1,4,5,9 ou 16. Dessa maneira, Eliminamos 14 possibilidades módulo 20.

$b^2 = a^2 - N$ deve terminar em 0,1,4,5,9 ou 16.

Vamos calcular as possibilidades $a^2$ módulo 20 ser um quadrado perfeito dado que $b^2$ é um quadrado perfeito.  

a^2 = b^2 + N 

Vamos supor que  N módulo 20 = 3

$b^2 + N$ mod 20 
0 + 3 = 3
1 + 3 = 4
4 + 3 = 7
5 + 3 = 8
9 + 3 = 12
16+ 3 = 19

Dado que $b^2$ é um quadrado perfeito, então a^2 mod 20 = 1

Os valores de a tal que $a^2$ mod 20 = 1 são:
1,9,11,19

Precisamos apenar computar os valores de a que termina 1,9,11 e 19. Dessa maneira, eliminamos 16 possibilidade de 20. 

#include <stdio.h>
#include <stdlib.h>
#include <set>

using namespace std;

int main(){
 int n,m,i;
 set <int> squared;
 set <int> squaredA;
 set <int> a;
 set <int>::iterator it;
  
 scanf("Entre com m:");
 scanf("%d",&m);

 printf("Os seguintes numeros sao quadrado perfeitos modulo %d\n",m);
 for(i=0;i<m;i++)
  squared.insert((i*i)%m);
 
 for(it= squared.begin(); it != squared.end(); it++)
  printf("%d\n", *it);
 
 printf("Entre com n:");
 scanf("%d",&n);
 
 printf("%d modulo %d = %d\n",n,m,n%m);
 
 //a^2 - b^2 = N
 //a^2  = N + b^2
 
 printf("a^2 tem que terminar em\n");
 for(it= squared.begin(); it != squared.end(); it++)
  if( squared.find((*it + n%m)%m)!= squared.end() ){
   printf("%d\n", (*it + n%m)%m);
   squaredA.insert((*it + n%m)%m);  
  }
 
 printf("a tem que terminar em\n"); 
 for(i=0;i<m;i++){
  if( squaredA.find((i*i)%m)!= squaredA.end() ){
   a.insert(i%m);
  }
 }
  
 for(it= a.begin(); it != a.end(); it++)
  printf("%d\n",*it);
  
 system("PAUSE"); 

}

Saída


20
Os seguintes numeros sao quadrado perfeitos modulo 20
0
1
4
5
9
16
Entre com n:17
17 modulo 20 = 17
a^2 tem que terminar em
1
a tem que terminar em
1
9
11
19
Pressione qualquer tecla para continuar. . .

Fonte: http://en.wikipedia.org/wiki/Fermat's_factorization_method