ecm.h File Reference

The elliptic curve method of integer factorization (ECM). More...

#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_ecm_params_t
	Defines the variable parameters used in ECM. More...
Defines
#define	_TIFA_ECM_H_
Typedefs
typedef struct struct_ecm_params_t	ecm_params_t
	Equivalent to struct struct_ecm_params_t.
Functions
void	set_ecm_params_to_default (const mpz_t n, ecm_params_t *const params)
	Fills an ecm_params_t with "good" default values.
ecode_t	ecm (mpz_array_t *const factors, uint32_array_t *const multis, const mpz_t n, const ecm_params_t *const params, const factoring_mode_t mode)
	Integer factorization with the elliptic curve method (ECM).

---

Detailed Description

The elliptic curve method of integer factorization (ECM).

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

This is the TIFA library's implementation of the 'ECM' factorization algorithm. The second phase of the algorithm follows the standard continuation and is implemented in a way reminiscent of the description given in the article "Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware" by Kris Gaj et al.

See also:

"Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware", K. Gaj et al., Cryptographic Hardware and Embedded Systems - CHES 2006.

Warning:

This is merely a toy-implementation of ECM without any smart optimizations. More work is certainly needed to make it competitive for small numbers. Large numbers are, of course, out of the scope of this library.

Definition in file ecm.h.

---

Define Documentation

#define _TIFA_ECM_H_

Standard include guard.

Definition at line 48 of file ecm.h.

---

Function Documentation

ecode_t ecm	(	mpz_array_t *const	factors,
		uint32_array_t *const	multis,
		const mpz_t	n,
		const ecm_params_t *const	params,
		const factoring_mode_t	mode
	)

Integer factorization with the elliptic curve method (ECM).

Attempts to factor the non perfect square integer n with the ECM, 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 ECM.
[in]	mode	The factoring mode to use.

Returns:

An exit code.

void set_ecm_params_to_default	(	const mpz_t	n,
		ecm_params_t *const	params
	)

Fills an ecm_params_t with "good" default values.

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

Warning:

This is, for the time being, a dummy function. Parameters are not set to suitable values at all! Do not use it: for the time being, you should choose the parameters by yourself! Shocking!

Parameters:

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