fermat.h File Reference

McKee's variant of the Fermat factorization algorithm. More...

#include <stdlib.h>
#include <gmp.h>
#include "array.h"
#include "factoring_machine.h"
#include "exit_codes.h"

Go to the source code of this file.

Data Structures
struct	struct_fermat_params_t
	Defines the variable parameters used in Fermat's algorithm (dummy structure). More...
Defines
#define	_TIFA_FERMAT_H_
Typedefs
typedef struct struct_fermat_params_t	fermat_params_t
	Equivalent to struct struct_fermat_params_t.
Functions
void	set_fermat_params_to_default (fermat_params_t *const params)
	Fills a fermat_params_t with default values (dummy function).
ecode_t	fermat (mpz_array_t *const factors, uint32_array_t *const multis, const mpz_t n, const fermat_params_t *const params, const factoring_mode_t mode)
	Integer factorization via McKee's speedup of Fermat's factorization algorithm.

---

Detailed Description

McKee's variant of the Fermat factorization algorithm.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

This is the TIFA library's implementation of James McKee's proposed speedup of the Fermat factorization algorithm (SQUFOF), based on the description given by McKee in its paper "Speeding Fermat's Factoring Method".

Note:

This implementation can only factor numbers whose size is less than twice the size of an unsigned long int.

See also:

"Speeding Fermat's Factoring Method", James McKee. Mathematics of Computation, Volume 68, Number 228, pages 1729-1737.

Definition in file fermat.h.

---

Define Documentation

#define _TIFA_FERMAT_H_

Standard include guard.

Definition at line 44 of file fermat.h.

---

Function Documentation

ecode_t fermat	(	mpz_array_t *const	factors,
		uint32_array_t *const	multis,
		const mpz_t	n,
		const fermat_params_t *const	params,
		const factoring_mode_t	mode
	)

Integer factorization via McKee's speedup of Fermat's factorization algorithm.

Attempts to factor the non perfect square integer n using James McKee's proposed enhancement of Fermat's algorithm, using the factoring mode given by mode. Found factors are then stored in factors. Additionally, if the factoring mode used is set to FIND_COMPLETE_FACTORIZATION, factors' multiplicities are stored in the array multis.

Warning:

This implementation can only factor numbers whose sizes in bits are strictly less than twice the size of an unsigned long int. This choice was made to maximize the use of single precision operations. Such a limitation should not be much of a problem since Fermat's algorithm is mostly used to factor very small integers (up to, say, 20 decimal digits).

Note:

If the factoring mode used is different from FIND_COMPLETE_FACTORIZATION, multis is allowed to be a NULL pointer. Otherwise, using a NULL pointer will lead to a fatal error.

Warning:

If the factors and multis arrays have not enough room to store the found factors (and the multiplicities, if any), they will be automatically resized to accommodate the data. This has to be kept in mind when trying to do ingenious stuff with memory management (hint: don't try to be clever here).

Parameters:

[out]	factors	Pointer to the found factors of n.
[out]	multis	Pointer to the multiplicities of the found factors (only computed if mode is set to FIND_COMPLETE_FACTORIZATION).
[in]	n	The non perfect square integer to factor.
[in]	params	Fermat's algorithm parameters (currently unused).
[in]	mode	The factoring mode to use.

Returns:

An exit code.

void set_fermat_params_to_default

(

fermat_params_t *const

params

)

Fills a fermat_params_t with default values (dummy function).

This function is intended to fill a fermat_params_t with default values.

Warning:

For the time being, this is a dummy function which does absolutely nothing at all, but is kept only as a placeholder should the need for user parameters arise in future code revisions.

Parameters:

params

A pointer to the fermat_params_t structure to fill.