cfrac.h File Reference

The CFRAC factorization algorithm. More...

#include <stdbool.h>
#include <gmp.h>
#include "first_primes.h"
#include "array.h"
#include "lindep.h"
#include "smooth_filter.h"
#include "factoring_machine.h"
#include "exit_codes.h"

Go to the source code of this file.

Data Structures
struct	struct_cfrac_params_t
	Defines the variable parameters used in the CFRAC algorithm. More...
Defines
#define	_TIFA_CFRAC_H_
#define	CFRAC_DFLT_NPRIMES_IN_BASE   (NFIRST_PRIMES/16)
#define	CFRAC_DFLT_NPRIMES_TDIV   (NFIRST_PRIMES/16)
#define	CFRAC_DFLT_NRELATIONS   32
#define	CFRAC_DFLT_LINALG_METHOD   SMART_GAUSS_ELIM
#define	CFRAC_DFLT_USE_LARGE_PRIMES   true
Typedefs
typedef struct struct_cfrac_params_t	cfrac_params_t
	Equivalent to struct struct_cfrac_params_t.
Functions
void	set_cfrac_params_to_default (const mpz_t n, cfrac_params_t *const params)
	Fills a cfrac_params_t with "good" default values.
ecode_t	cfrac (mpz_array_t *const factors, uint32_array_t *const multis, const mpz_t n, const cfrac_params_t *const params, const factoring_mode_t mode)
	Integer factorization via the continued fraction (CFRAC) algorithm.

---

Detailed Description

The CFRAC factorization algorithm.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

This is the TIFA library's implementation of the CFRAC factorization algorithm from M. A. Morrison and J. Brillhart, together with the large prime variation.

See also:

"A Method of Factoring and the Factorization of F_7", M. A. Morrison and J. Brillhart, Mathematics of Computation, vol 29, #129, Jan 1975, pages 183-205.

Definition in file cfrac.h.

---

Define Documentation

#define _TIFA_CFRAC_H_

Standard include guard.

Definition at line 41 of file cfrac.h.

#define CFRAC_DFLT_LINALG_METHOD   SMART_GAUSS_ELIM

Default linear system resolution method to use.

Definition at line 79 of file cfrac.h.

#define CFRAC_DFLT_NPRIMES_IN_BASE   (NFIRST_PRIMES/16)

Default number of prime numbers composing the factor base on which to factor the residues.

Definition at line 62 of file cfrac.h.

#define CFRAC_DFLT_NPRIMES_TDIV   (NFIRST_PRIMES/16)

Default number of the first primes to use in the trial division of the residues.

Definition at line 68 of file cfrac.h.

#define CFRAC_DFLT_NRELATIONS   32

Default number of congruence relations to find before attempting the factorization of the large integer.

Definition at line 74 of file cfrac.h.

#define CFRAC_DFLT_USE_LARGE_PRIMES   true

Use the large prime variation by default.

Definition at line 84 of file cfrac.h.

---

Function Documentation

ecode_t cfrac	(	mpz_array_t *const	factors,
		uint32_array_t *const	multis,
		const mpz_t	n,
		const cfrac_params_t *const	params,
		const factoring_mode_t	mode
	)

Integer factorization via the continued fraction (CFRAC) algorithm.

Attempts to factor the non perfect square integer n with the CFRAC algorithm, using the set of parameters given by params and 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.

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).

The "no large primes" variant is currently disabled.

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	Pointer to the values of the parameters used in the CFRAC algorithm.
[in]	mode	The factoring mode to use.

Returns:

An exit code.

void set_cfrac_params_to_default	(	const mpz_t	n,
		cfrac_params_t *const	params
	)

Fills a cfrac_params_t with "good" default values.

Fills a cfrac_params_t with "good" default values choosen according to the size of the number n to factor.

Warning:

There is no guarantee that the choosen parameter values will be the best ones for a given number to factor. However, provided that the number to factor is between 40 and 200 bits long, the choosen values should be nearly optimal.

Parameters:

[in]	n	The mpz_t integer to factor.
[out]	params	A pointer to the cfrac_params_t structure to fill.