lindep.h File Reference

Functions used in the resolution of the linear systems. More...

#include <inttypes.h>
#include "array.h"
#include "x_array_list.h"
#include "matrix.h"
#include "exit_codes.h"

Go to the source code of this file.

Defines
#define	_TIFA_LINDEP_H_
Typedefs
typedef enum linalg_method_enum	linalg_method_t
	Equivalent to enum linalg_method_enum.
Enumerations
enum	linalg_method_enum { SMART_GAUSS_ELIM = 0 }
Functions
void	fill_matrix_trial_div (binary_matrix_t *const matrix, mpz_array_t *const partially_factored, const mpz_array_t *const to_factor, const uint32_array_t *const factor_base)
	Fills a binary matrix via trial divisions.
void	fill_trial_div_decomp (binary_matrix_t *const matrix, byte_matrix_t *const decomp_matrix, mpz_array_t *const partially_factored, const mpz_array_t *const to_factor, const uint32_array_t *const factor_base)
	Similar to fill_matrix_trial_div but also stores valuations.
void	fill_matrix_from_list (binary_matrix_t *const matrix, const mpz_array_t *const smooth_array, const uint32_array_list_t *const list, const uint32_array_t *const factor_base)
	Fills a binary matrix from a list of factors.
void	fill_matrix_from_list_decomp (binary_matrix_t *const matrix, byte_matrix_t *const decomp_matrix, const mpz_array_t *const smooth_array, const uint32_array_list_t *const list, const uint32_array_t *const factor_base)
	Similar to fill_matrix_from_list but also stores valuations.
uint32_array_list_t *	find_dependencies (binary_matrix_t *const matrix, linalg_method_t method)
	Solves a linear system over GF(2).
ecode_t	find_factors (mpz_array_t *const factors, const mpz_t n, const mpz_array_t *const xi_array, const mpz_array_t *const yi_array, const uint32_array_list_t *const dependencies)
	Find factors of an integer from congruence relations.
ecode_t	find_factors_decomp (mpz_array_t *const factors, const mpz_t n, const mpz_array_t *const xi_array, const byte_matrix_t *const yi_decomp_matrix, const uint32_array_list_t *const dependencies, const uint32_array_t *const factor_base)
	Similar to find_factors but uses the factorization of each y_i.
Variables
static const char *const	linalg_method_to_str [1]

---

Detailed Description

Functions used in the resolution of the linear systems.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

Functions used in the resolution of the linear systems over GF(2) found in factorization problems and in the very last stage of the factorization process (determination of factors after linear algebra phase).

Definition in file lindep.h.

---

Define Documentation

#define _TIFA_LINDEP_H_

Standard include guard.

Definition at line 37 of file lindep.h.

---

Enumeration Type Documentation

enum linalg_method_enum

Enumeration listing the different linear system resolution method implemented.

For the time being, only one method is available.

Enumerator:

SMART_GAUSS_ELIM

"Smart" gaussian elimination described in: "A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers", by D. Parkinson and M. Wunderlich (Parallel Computing 1 (1984) 65-73).

Definition at line 58 of file lindep.h.

---

Function Documentation

void fill_matrix_from_list	(	binary_matrix_t *const	matrix,
		const mpz_array_t *const	smooth_array,
		const uint32_array_list_t *const	list,
		const uint32_array_t *const	factor_base
	)

Fills a binary matrix from a list of factors.

Fills the binary matrix matrix from a previously computed list giving all known factors.

Note:

list countains the previously computed factors of each integers in smooth_array, in other words, we know that smooth_array->data[i] is divisible by all the integers of the uint32_array_t given by list->data[i].

The binary matrix is filled so that:

• There is a '1' in the (i-th row, 1st col) position in the matrix if smooth_factor->data[i] is negative.
• There is a '1' in the (i-th row, j-th col) position in the matrix if smooth_factor->data[i] is divisible by an odd power of list->data[i]->data[k]. Here j is found so that factor_base->data[j] = list->data[i]->data[k].
• In all other cases, the (i-th row, j-th col) position in the matrix contains a 0.

Parameters:

[out]	matrix	A pointer to the binary matrix to fill.
[out]	smooth_array	A pointer to the array giving the integers to factor.
[in]	list	A pointer to the factor list for each integer to factor.
[in]	factor_base	A pointer to the array listing the integers to trial divide by.

void fill_matrix_from_list_decomp	(	binary_matrix_t *const	matrix,
		byte_matrix_t *const	decomp_matrix,
		const mpz_array_t *const	smooth_array,
		const uint32_array_list_t *const	list,
		const uint32_array_t *const	factor_base
	)

Similar to fill_matrix_from_list but also stores valuations.

Fills the binary matrix matrix from a previously computed list giving all known factors.

Also stores in decomp_matrix the valuation of each integer from smooth_array for each prime in the factor base. For example the valuation of smooth_array->data[i] for the prime given by factor_base->data[j] will be stored in decomp_matrix->data[i][j].

Note:

list countains the previously computed factors of each integers in smooth_array, in other words, we know that smooth_array->data[i] is divisible by all the integers of the uint32_array_t given by list->data[i].

The binary matrix is filled so that:

• There is a '1' in the (i-th row, 1st col) position in the matrix if smooth_factor->data[i] is negative.
• There is a '1' in the (i-th row, j-th col) position in the matrix if smooth_factor->data[i] is divisible by an odd power of list->data[i]->data[k]. Here j is found so that factor_base->data[j] = list->data[i]->data[k].
• In all other cases, the (i-th row, j-th col) position in the matrix contains a 0.

Parameters:

[out]	matrix	A pointer to the binary matrix to fill.
[out]	decomp_matrix	A pointer to the byte matrix to fill.
[out]	smooth_array	A pointer to the array giving the integers to factor.
[in]	list	A pointer to the factor list for each integer to factor.
[in]	factor_base	A pointer to the array listing the integers to trial divide by.

void fill_matrix_trial_div	(	binary_matrix_t *const	matrix,
		mpz_array_t *const	partially_factored,
		const mpz_array_t *const	to_factor,
		const uint32_array_t *const	factor_base
	)

Fills a binary matrix via trial divisions.

Fills the binary matrix matrix by trial divisions of the integers listed in to_factor by the integers listed in factor_base. After these trial divisions, each partially factored integer from to_factor are stored in partially_factored.

Note:

The binary matrix is filled so that:

• There is a '1' in the (i-th row, 1st col) position in the matrix if to_factor->data[i] is negative.
• There is a '1' in the (i-th row, j-th col) position in the matrix if to_factor->data[i] is divisible by an odd power of factor_base->data[j].
• In all other cases, the (i-th row, j-th col) position in the matrix contains a 0.

Parameters:

[out]	matrix	A pointer to the binary matrix to fill.
[out]	partially_factored	A pointer to the partially factored integers.
[in]	to_factor	A pointer to the array listing the integers to factor.
[in]	factor_base	A pointer to the array listing the integers to trial divide by.

void fill_trial_div_decomp	(	binary_matrix_t *const	matrix,
		byte_matrix_t *const	decomp_matrix,
		mpz_array_t *const	partially_factored,
		const mpz_array_t *const	to_factor,
		const uint32_array_t *const	factor_base
	)

Similar to fill_matrix_trial_div but also stores valuations.

Fills the binary matrix matrix by trial divisions of the integers listed in to_factor by the integers listed in factor_base. After these trial divisions, each partially factored integer from to_factor are stored in partially_factored.

Also stores in decomp_matrix the valuation of each integer from to_factor for each prime in the factor base. For example the valuation of to_factor->data[i] for the prime given by factor_base->data[j] will be stored in decomp_matrix->data[i][j].

Note:

The binary matrix is filled so that:

• There is a '1' in the (i-th row, 1st col) position in the matrix if to_factor->data[i] is negative.
• There is a '1' in the (i-th row, j-th col) position in the matrix if to_factor->data[i] is divisible by an odd power of factor_base->data[j].
• In all other cases, the (i-th row, j-th col) position in the matrix contains a 0.

Parameters:

[out]	matrix	A pointer to the binary matrix to fill.
[out]	decomp_matrix	A pointer to the byte matrix to fill.
[out]	partially_factored	A pointer to the partially factored integers.
[in]	to_factor	A pointer to the array listing the integers to factor.
[in]	factor_base	A pointer to the array listing the integers to trial divide by.

uint32_array_list_t* find_dependencies	(	binary_matrix_t *const	matrix,
		linalg_method_t	method
	)

Solves a linear system over GF(2).

Solves the linear system over GF(2) given by the binary matrix matrix, using the resolution method method.

Note:

For the time being, the only implemented method is SMART_GAUSS_ELIM.

Parameters:

[in,out]	matrix	A pointer to the binary matrix giving the system to solve.
[in]	method	The linear system resolution method to use.

ecode_t find_factors	(	mpz_array_t *const	factors,
		const mpz_t	n,
		const mpz_array_t *const	xi_array,
		const mpz_array_t *const	yi_array,
		const uint32_array_list_t *const	dependencies
	)

Find factors of an integer from congruence relations.

Find factors of the integer n from congruence relations of the form {(x_i)^2}_i = {y_i}_i (mod n) where {y_i}_i is a perfect square.

Each entry in dependencies gives the list of the aforementioned indexes i so that such a previous relation will hold.

Upon termination, returns the following ecode_t:

• SOME_FACTORS_FOUND if some factors were found
• NO_FACTOR FOUND is no factor was found
• FATAL_INTERNAL_ERROR is case of... a really ugly error!

Parameters:

[out]	factors	The factors of n found.
[in]	n	The integer to factor.
[in]	xi_array	A pointer to an array giving the avalaible x_i values.
[in]	yi_array	A pointer to an array giving the avalaible y_i values.
[in]	dependencies	A pointer to an array list giving the sets of indexes from which a congruence relation can be computed.

Returns:

An exit code.

ecode_t find_factors_decomp	(	mpz_array_t *const	factors,
		const mpz_t	n,
		const mpz_array_t *const	xi_array,
		const byte_matrix_t *const	yi_decomp_matrix,
		const uint32_array_list_t *const	dependencies,
		const uint32_array_t *const	factor_base
	)

Similar to find_factors but uses the factorization of each y_i.

Find factors of the integer n from congruence relations of the form {(x_i)^2}_i = {y_i}_i (mod n) where {y_i}_i is a perfect square.

Each entry in dependencies gives the list of the aforementioned indexes i so that such a previous relation will hold.

The difference with the find_factors function is that here the y_i are not given directly but rather by their factorizations on the factor base by yi_decomp_matrix. For example the valuation of y_i for the prime given by factor_base->data[j] is stored in yi_decomp_matrix->data[i][j].

Upon termination, returns the following ecode_t:

• SOME_FACTORS_FOUND if some factors were found
• NO_FACTOR FOUND is no factor was found
• FATAL_INTERNAL_ERROR is case of... a really ugly error!

Parameters:

[out]	factors	The factors of n found.
[in]	n	The integer to factor.
[in]	xi_array	A pointer to an array giving the avalaible x_i values.
[in]	yi_decomp_matrix	A pointer to a byte matrix giving the factorization of the y_i.
[in]	dependencies	A pointer to an array list giving the sets of indexes from which a congruence relation can be computed.
[in]	factor_base	A pointer to the array listing the primes in the factor base.

Returns:

An exit code.

---

Variable Documentation

const char* const linalg_method_to_str[1] [static]

Initial value:

 {
    "smart gaussian elimination"
}

Global constant array mapping linalg methods to their string representations.

Definition at line 78 of file lindep.h.