siqs.h File Reference

The Self-Initializing Quadratic Sieve factorization algorithm. More...

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

Go to the source code of this file.

Data Structures
struct	struct_siqs_params_t
	Defines the variable parameters used in the SIQS algorithm. More...
Defines
#define	_TIFA_SIQS_H_
#define	SIQS_DFLT_SIEVE_HALF_WIDTH   500000
#define	SIQS_DFLT_NPRIMES_IN_BASE   NFIRST_PRIMES/16
#define	SIQS_DFLT_NPRIMES_TDIV   NFIRST_PRIMES/16
#define	SIQS_DFLT_NRELATIONS   24
#define	SIQS_DFLT_LINALG_METHOD   SMART_GAUSS_ELIM
#define	SIQS_DFLT_USE_LARGE_PRIMES   true
Typedefs
typedef struct struct_siqs_params_t	siqs_params_t
	Equivalent to struct struct_siqs_params_t.
Functions
void	set_siqs_params_to_default (const mpz_t n, siqs_params_t *const params)
	Fills a siqs_params_t with default values.
ecode_t	siqs (mpz_array_t *const factors, uint32_array_t *const multis, const mpz_t n, const siqs_params_t *const params, const factoring_mode_t mode)
	Integer factorization via the self-initializing quadratic sieve (SIQS) algorithm.

---

Detailed Description

The Self-Initializing Quadratic Sieve factorization algorithm.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

Definition in file siqs.h.

---

Define Documentation

#define _TIFA_SIQS_H_

Standard include guard.

Definition at line 33 of file siqs.h.

#define SIQS_DFLT_LINALG_METHOD   SMART_GAUSS_ELIM

Default linear system resolution method to use.

Definition at line 75 of file siqs.h.

#define SIQS_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 58 of file siqs.h.

#define SIQS_DFLT_NPRIMES_TDIV   NFIRST_PRIMES/16

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

Definition at line 64 of file siqs.h.

#define SIQS_DFLT_NRELATIONS   24

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

Definition at line 70 of file siqs.h.

#define SIQS_DFLT_SIEVE_HALF_WIDTH   500000

Default sieving half-width.

Definition at line 52 of file siqs.h.

#define SIQS_DFLT_USE_LARGE_PRIMES   true

Use the large prime variation by default.

Definition at line 80 of file siqs.h.

---

Function Documentation

void set_siqs_params_to_default	(	const mpz_t	n,
		siqs_params_t *const	params
	)

Fills a siqs_params_t with default values.

Fills a siqs_params_t with default values.

Parameters:

[in]	n	The number to factor.
[out]	params	A pointer to the siqs_params_t structure to fill.

ecode_t siqs	(	mpz_array_t *const	factors,
		uint32_array_t *const	multis,
		const mpz_t	n,
		const siqs_params_t *const	params,
		const factoring_mode_t	mode
	)

Integer factorization via the self-initializing quadratic sieve (SIQS) algorithm.

Attempts to factor the non perfect square integer n with the SIQS 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).

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 SIQS algorithm.
[in]	mode	The factoring mode to use.

Returns:

An exit code.