squfof.h File Reference

The SQUFOF 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_squfof_params_t
	Defines the variable parameters used in the SQUFOF algorithm (dummy structure). More...
Defines
#define	_TIFA_SQUFOF_H_
Typedefs
typedef struct struct_squfof_params_t	squfof_params_t
	Equivalent to struct struct_squfof_params_t.
Functions
void	set_squfof_params_to_default (squfof_params_t *const params)
	Fills a squfof_params_t with default values (dummy function).
ecode_t	squfof (mpz_array_t *const factors, uint32_array_t *const multis, const mpz_t n, const squfof_params_t *const params, const factoring_mode_t mode)
	Integer factorization via the square form factorization (SQUFOF) algorithm.

---

Detailed Description

The SQUFOF factorization algorithm.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

This is the TIFA library's implementation of Shanks' square form factorization algorithm (SQUFOF), based on the description given by Jason Gower and Samuel Wagstaff in their paper "Square Form Factorization" to be published in Mathematics of Computation.

Note:

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

See also:

"Square Form Factorization", Jason E. Gower & Samuel S. Wagstaff Jr. Mathematics of Computation, S 0025-5718(07)02010-8, Article electronically published on May 14, 2007.

"Square Form Factorization", Jason E. Gower, PhD thesis, Purdue University, December 2004.

For a description of the "large step algorithm" used to quickly jump over several forms, see: "On the Parallel Generation of the Residues for the Continued Fraction Factoring Algorithm", Hugh C. Williams, Marvin C. Wunderlich, Mathematics of Computation, Volume 48, Number 177, January 1987, pages 405-423

Definition in file squfof.h.

---

Define Documentation

#define _TIFA_SQUFOF_H_

Standard include guard.

Definition at line 54 of file squfof.h.

---

Function Documentation

void set_squfof_params_to_default

(

squfof_params_t *const

params

)

Fills a squfof_params_t with default values (dummy function).

This function is intended to fill a squfof_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 squfof_params_t structure to fill.

ecode_t squfof	(	mpz_array_t *const	factors,
		uint32_array_t *const	multis,
		const mpz_t	n,
		const squfof_params_t *const	params,
		const factoring_mode_t	mode
	)

Integer factorization via the square form factorization (SQUFOF) algorithm.

Attempts to factor the non perfect square integer n with the SQUFOF 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 (the exact limit depending on the number to factor and the multiplier used). This choice was made because most of the computations are then performed using only single precision operations. Such a limitation should not be much of a problem since SQUFOF 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	SQUFOF's parameters (currently unused).
[in]	mode	The factoring mode to use.

Returns:

An exit code.