Fatorando números: Algoritmo de Fermat

Esses dias estive à procura de um método melhor para fatorar números que aquele, em pseudo-código:

for(i=2; i<sqrt(numero); i++)
    while(numero % i == 0)
        numero = numero / i
        append(fatores, i)

e encontrei o algoritmo de fermat, que se basea no princípio de que se pode escrever qualquer número ímpar e positivo na forma (r – s)(r + s). Lembrando que esse é um caso de produto notável, em que (r – s)(r + s) = r² – s², temos:
1² – 0² = 1
2² – 1² = 3
3² – 2² = 5

Depois nós efetuamos a soma e a subtração e fatoramos o resultado delas.

O algoritmo em si é:

  • Dividimos n por 2 até que ele vire um número ímpar (e adicionamos 2 à lista de fatores).
  • Definimos o intervalo em que vamos procurar a resposta, tal que \sqrt{n} \le r < \frac{n+1}{2} .
  • Para cada valor de r:
    • m = r^2 - n
    • Se m for maior que zero e tiver raiz exata, s = \sqrt{m} . Então, fatoramos (r – s) e (r + s).
  • Se chegarmos ao maior número que r pode ser sem que achemos (r – s) e (r + s), então n é um número primo e o adicionamos à lista de fatores.

A parte matemática é essa. Clique para ver o resto do artigo se quiser ver uma implementação em Python, uma em C e uma em Lisp.

Em Lisp vou ficar devendo por enquanto; o código atual funciona apenas no CLISP, e não no SBCL/CMUCL que são muito mais rápidos. Eu já sei o motivo, preciso achar um jeito de contornar o problema. É provável que eu aproveite e refaça parte do código.

Python

Essa foi a primeira versão que escrevi, é bastante simples e não há muito o que explicar. isqrt foi o jeito que eu achei de fazer r e s serem inteiros. Já a linha:

if m >= 0 and math.sqrt(m) == math.floor( math.sqrt(m) ):

foi como chequei se a raiz de m é exata ou não.

#!/usr/bin/env python
# coding=utf-8
import math
import sys

factors = []

def isqrt(number):
	return (int(math.sqrt(number)))

def fermat(number):
	global factors

	while number % 2 == 0:
		number = number/2
		factors.append(2)

	if number == 1:
		return

	r = isqrt(number)
	is_prime = True
	while r < (number+1)/2:
		m = (r ** 2) - number

		if m >= 0 and math.sqrt(m) == math.floor( math.sqrt(m) ):
			s = isqrt(m)
			fermat(r - s)
			fermat(r + s)

			is_prime = False
			return

		r = r+1
	
	if is_prime == True:
		factors.append(number)


num = int(sys.argv[1])

fermat(num)

print factors

C

Foi feita a partir da versão para Python, com a diferença de que C não possui funções para listas. No fim, acabei usando aquele método de árvores binárias para colocar números em ordem crescente que mostrei antes, evitando assim de ter que implementar uma função para colocar uma lista em ordem.

Não esqueça de compilar passando -lm como opção para o gcc já que usamos a biblioteca math.h.

/* compile com gcc -lm -o fermat fermat.c */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct leaf {
	int value;
	struct leaf* lft;
	struct leaf* rgt;
};
struct leaf* factors = NULL;

void insert(struct leaf** tree, int value);
void print_tree(struct leaf* tree);

void fermat(int number);

int main(int argc, char* argv[])
{
	int num = atoi(argv[1]);

	fermat(num);

	print_tree(factors);

	return(0);
}

void insert(struct leaf** tree, int value)
{
	struct leaf* current = *tree;

	if(current == NULL)
	{
		struct leaf* new = malloc(sizeof(struct leaf));
		new->value = value;
		new->lft = NULL;
		new->rgt = NULL;

		*tree = new;
	}

	else
	{
		if(value < current->value)
			insert(&(current->lft), value);
		else
			insert(&(current->rgt), value);
	}
}

void print_tree(struct leaf* tree)
{
	struct leaf* current = tree;

	if(current!=NULL)
	{
		print_tree(current->lft);
		printf("%d ", current->value);
		print_tree(current->rgt);
	}
}

void fermat(int number)
{
	int r;
	short int is_prime = 1;

	while(number % 2 == 0)
	{
		number = number/2;
		insert(&factors,2);
	}

	if(number == 1)
		return;

	r = sqrt(number);

	while(r < (number+1)/2)
	{
		int m = (r*r) - number;

		if(m >= 0 && sqrt(m) == floor(sqrt(m)))
		{
			int s = sqrt(m);

			fermat(r - s);
			fermat(r + s);

			is_prime = 0;
			return;
		}
		r=r+1;

	} 

	if(is_prime == 1)
		insert(&factors,number);
}
Publicidade

Uma resposta para “Fatorando números: Algoritmo de Fermat

  1. Antonio junho 20, 2012 às 10:40 am

    O problema é que dá erro na linha

    struct leaf* new = malloc(sizeof(struct leaf));

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: