tdiv.h File Reference

The trial division factorization algorithm. More...

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

Go to the source code of this file.

Defines
#define	_TIFA_TDIV_H_
#define	TDIV_DFLT_NPRIMES_TDIV   (NFIRST_PRIMES/32)
Functions
ecode_t	tdiv (mpz_array_t *const factors, uint32_array_t *const multis, const mpz_t n, const uint32_t nprimes)
	Integer factorization via trial division (TDIV).

---

Detailed Description

The trial division factorization algorithm.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

Naive (partial) factorization via trial divisions by a few small primes.

Definition in file tdiv.h.

---

Define Documentation

#define _TIFA_TDIV_H_

Standard include guard.

Definition at line 35 of file tdiv.h.

#define TDIV_DFLT_NPRIMES_TDIV   (NFIRST_PRIMES/32)

Default number of the first primes to use for trial division.

Definition at line 52 of file tdiv.h.

---

Function Documentation

ecode_t tdiv	(	mpz_array_t *const	factors,
		uint32_array_t *const	multis,
		const mpz_t	n,
		const uint32_t	nprimes
	)

Integer factorization via trial division (TDIV).

Attempts to factor the integer n via trial division by the first nprimes primes. Found factors are then stored in the array factors and multiplicities are stored in multis.

Returns:

• COMPLETE_FACTORIZATION_FOUND if the complete factorization of n was found.

• SOME_FACTORS_FOUND if some factors were found but could not account for the complete factorization of n. In that case, the unfactored part of n is stored in factors->data[factors->lenth - 1].

• NO_FACTOR_FOUND if no factor were found.

Warning:

The prime numbers are not computed but read from a table. Consequently the number of primes nprimes should be less than or equal to NFIRST_PRIMES (defined in array.h). If nprimes is zero, then the default value DFLT_TDIV_NPRIMES will be used instead.

Parameters:

[out]	factors	Pointer to the found factors of n.
[out]	multis	Pointer to the multiplicities of the found factors.
[in]	n	The integer to factor.
[in]	nprimes	The number of primes to trial divide n by.

Returns:

An exit code.