Fatoração de Fermat

Este algoritmo de fatoração foi desenvolvido por  Pierre de Fermat. O algoritmo é baseado na representação do números inteiros ímpares como a diferença de dois  quadrados.

$N = a^{2} - b^{2}$

Essa diferença pode ser fatorada da seguinte maneira:

$a^{2} - b^{2} = (a+b)(a-b)$

Se N = cd é uma fatoração de N então
$N = a^{2} - b^{2}$
$c = a+b$
$d = a-b$
$c+d = 2a$
$a = \frac{c+d}{2}$
$c-d = 2b$
$b = \frac{c-d}{2}$
$N = (\frac{c+d}{2})^2 - (\frac{c-d}{2})^2$

Como a = $\sqrt{N + b^2}$,logo a >= $\sqrt{N}$ e a < N.

A idéia do algorimor é percorrer todos os valores de  a = |$\sqrt{N}$|...N. Para cada valor de a, verifique se b = $\sqrt{a^2 - N}$ é inteiro e se (a+b) (a-b) são fatores não triviais de N.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <map>

using namespace std;


int eh_quadrado(int x){
 int y = (int)(sqrt(x+0.5));
 return y*y == x;
} 

int fermat_factor(int N){
 int a,b,b2,c,d;
 for(a=(int)ceil(sqrt(N));a<=N;a++){
  b2 = a*a - N;
  if( eh_quadrado(b2) ){
   b = (int)sqrt(b2);
   c = a+b;
   if(c!=1 and c!=N)
    return c;
  }
 }
}

int primo(int n){ 
 if(n==1) return 1;
 else if( n< 4) return 1;
 else if( n%2 ==0) return 0;
 else if( n< 9) return 1;
 else if( n%3 ==0) return 0;
 else {
  int r = (int)sqrt(n);
  int f = 5;
  
  while( f<=r){
   if(n%f==0) return 0;
   if(n%(f+2)==0) return 0;
   f=f+6;
  }
 }
 return 1;
}


void factorization(int N, map <int, int> & fatores ){
 int f;
 
 if(primo(N)){
  fatores[N]++;
 }else{
  f = fermat_factor(N);
  factorization(f, fatores);
  factorization(N/f, fatores);
 }
}



void fermat_factorization(int N, map <int, int>  & fatores){
 while(N%2==0) { fatores[2]++; N=N/2;}
 factorization(N, fatores);
}

void trial_factorization(int N, map <int, int>  & fatores){
 
 int i = 3;
 int limite;
 
 while(N%2==0) { fatores[2]++; N=N/2;}
 
 limite = (int)sqrt(N);
 
 while( N!=1 && i <= limite ){   
   while(N%i==0) { fatores[i]++; N=N/i;}
   limite = (int)sqrt(N);  
   i = i+2;
 }
 
 if(N!=1){ fatores[N]++;}
 
}


int main(){
 
 /*
 for(int i=1;i<=10000;i++)
  if(eh_quadrado(i))
   printf("%d\n",i);
 */
 
 map <int, int> fatores;
 map <int, int>::iterator iter;
 
 printf("fatores:\n");
 fermat_factorization(675734124, fatores);
 
 printf("%d\n", fatores.size());
 
 for(iter = fatores.begin(); iter!= fatores.end(); iter++){
  printf("%d %d\n", iter->first , iter->second);
 }
 
 fatores.clear();
 
 trial_factorization(675734124, fatores);
 
 printf("fatores:\n");
 
 printf("%d\n", fatores.size());
 
 for(iter = fatores.begin(); iter!= fatores.end(); iter++){
  printf("%d %d\n", iter->first , iter->second);
 }
 return 0;

}

Saída:


fatores:
5
2 2
3 1
13 1
113 1
38333 1
fatores:
5
2 2
3 1
13 1
113 1
38333 1