bernsteinisms.h File Reference

Algorithms from two D. J. Bernstein's papers on the factorization of small integers. More...

#include <inttypes.h>
#include "array.h"
#include "x_array_list.h"
#include "hashtable.h"
#include "smooth_filter.h"

Go to the source code of this file.

Defines

#define _TIFA_BERNSTEINISMS_H_

Functions

mpz_t * bern_51 (uint32_t b, const mpz_t u)

Daniel J. Bernstein's algorithm 5.1.

mpz_t * bern_53 (uint32_t b, const mpz_t u, const mpz_t x)

Daniel J. Bernstein's algorithm 5.3.

uint32_array_t * bern_63 (const mpz_t x, const mpz_array_t *const tree)

Daniel J. Bernstein's algorithm 6.3.

void bern_71 (uint32_array_list_t *const decomp_list, const mpz_array_t *const to_be_factored, const uint32_array_t *const odd_primes)

Daniel J. Bernstein's algorithm 7.1.

uint32_t bern_21_rt (mpz_array_t *const smooth, const mpz_array_t *const xi, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 (with computation of a remainder tree).

uint32_t bern_21 (mpz_array_t *const smooth, const mpz_array_t *const xi, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 (without computation of a remainder tree).

uint32_t bern_21_rt_pairs (mpz_array_t *const xi, mpz_array_t *const smooth_yi, const mpz_array_t *const cand_xi, const mpz_array_t *const cand_yi, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 modified.

uint32_t bern_21_pairs (mpz_array_t *const xi, mpz_array_t *const smooth_yi, const mpz_array_t *const cand_xi, const mpz_array_t *const cand_yi, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 modified (without computation of a remainder tree).

uint32_t bern_21_rt_pairs_lp (const mpz_t n, hashtable_t *const htable, mpz_array_t *const xi, mpz_array_t *const smooth_yi, const mpz_array_t *const cand_xi, const mpz_array_t *const cand_yi, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 modified, with large primes variation.

uint32_t bern_21_pairs_lp (const mpz_t n, hashtable_t *const htable, mpz_array_t *const xi, mpz_array_t *const smooth_yi, const mpz_array_t *const cand_xi, const mpz_array_t *const cand_yi, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 modified, with large primes variation (without computation of a remainder tree).

uint32_t bern_21_rt_pairs_siqs (mpz_array_t *const xi, mpz_array_t *const smooth_yi, mpz_array_t *const a_for_smooth_gx, const mpz_array_t *const cand_xi, const mpz_array_t *const cand_yi, const mpz_array_t *const cand_a, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 modified for SIQS (with computation of a remainder tree).

uint32_t bern_21_rt_pairs_lp_siqs (const mpz_t n, hashtable_t *const htable, mpz_array_t *const xi, mpz_array_t *const smooth_yi, mpz_array_t *const a_for_smooth_yi, const mpz_array_t *const cand_xi, const mpz_array_t *const cand_yi, const mpz_array_t *const cand_a, const mpz_t z)

Daniel J. Bernstein's algorithm 2.1 modified for SIQS, with large primes variation (with computation of a remainder tree).

uint32_t djb_batch_rt (smooth_filter_t *const filter, unsigned long int step)

Daniel J. Bernstein's algorithm 2.1 adapted to be used with a smooth_filter_t.

Detailed Description

Algorithms from two D. J. Bernstein's papers on the factorization of small integers.

Author:: Jerome Milan

Date:: Fri Jun 10 2011

Version:: 2011-06-10

Algorithms from two D. J. Bernstein's papers on the factorization of small integers:

"How to find small factors of integers", http://cr.yp.to/papers/sf.pdf
"How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Definition in file bernsteinisms.h.

Define Documentation

#define _TIFA_BERNSTEINISMS_H_

Standard include guard.

Definition at line 40 of file bernsteinisms.h.

Function Documentation

uint32_t bern_21	(	mpz_array_t *const	smooth,
		const mpz_array_t *const	xi,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 (without computation of a remainder tree).

Given the prime numbers p_j listed by pj and the positive integers x_i listed by xi, determines the {p_j}-smooth part of each x_i and stores them in smooth, so that smooth->data[i] is the {p_j}-smooth part of xi->data[i].

The function stops when each integer from xi has been checked for smoothness or when the smooth array is completely filled. It then returns the index of the last integer in xi that has been checked for smoothness.

This is the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers".

Note:: This function differs from bern_21_rt only because no remainder tree is computed. This can sometimes be faster than the full fledged version.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[out]`	smooth	A pointer to the {p_j}-smooth parts of each x_i integer.
`[in]`	xi	A pointer to the list of the x_i integers.
`[in]`	z	The product of the the p_j prime numbers in the facotr base.

Returns:: The index of the last integer in xi that has been checked for smoothness.

uint32_t bern_21_pairs	(	mpz_array_t *const	xi,
		mpz_array_t *const	smooth_yi,
		const mpz_array_t *const	cand_xi,
		const mpz_array_t *const	cand_yi,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 modified (without computation of a remainder tree).

Given the prime numbers p_j listed by pj and the positive integers y_i listed by cand_yi, determines the y_i that are {p_j}-smooth and stores them in smooth_yi, so that smooth_yi->data[i] is indeed {p_j}-smooth.

In a typical factorization problem, we other found ourselves in situations where each y_i is associated to another integer x_i. The x_i associated to the {p_j}-smooth y_i are hence stored in xi.

The function stops when each integer from cand_yi has been checked for smoothness or when the smooth_yi array is completely filled. It then returns the index of the last integer in cand_yi that has been checked for smoothness.

This function uses the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers" except that this function has been tailored to better suit the factorization problem.

Note:: This function is very similar to bern_21_rt_pairs. The only difference is that in bern_21_pairs no remainder tree is computed. This can sometimes be faster than the full fledged version.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[out]`	xi	A pointer to the {x_i} associated to the {p_j}-smooth y_i integer.
`[out]`	smooth_yi	A pointer to the {p_j}-smooth y_i integer.
`[in]`	cand_xi	A pointer to the list of the x_i integers.
`[in]`	cand_yi	A pointer to the list of the y_i integers.
`[in]`	z	The product of the the p_j prime numbers in the facotr base.

Returns:: The index of the last integer in cand_yi that has been checked for smoothness.

uint32_t bern_21_pairs_lp	(	const mpz_t	n,
		hashtable_t *const	htable,
		mpz_array_t *const	xi,
		mpz_array_t *const	smooth_yi,
		const mpz_array_t *const	cand_xi,
		const mpz_array_t *const	cand_yi,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 modified, with large primes variation (without computation of a remainder tree).

Given z, the product of prime numbers p_j and the positive integers y_i listed by cand_yi, determines the y_i that are {p_j}-smooth and stores them in smooth_yi, so that smooth_yi->data[i] is indeed {p_j}-smooth.

In a typical factorization problem, we other found ourselves in situations where each y_i is associated to another integer x_i. The x_i associated to the {p_j}-smooth y_i are hence stored in xi.

Moreover, this function implements the so-called large primes variation. If a given y_i is not {p_j}-smooth but is the product of a prime p by a {p_j}-smooth number, it is stored in the hashtable htable. Subsequently, if another y_j is the product of a {p_j}-smooth number by the same prime number p, then y_i*y_j/(p^2) is stored in smooth_yi and x_i*x_j*pinv is stored in xi where pinv is the inverse of p in Z/cZ.

The function stops when each integer from cand_yi has been checked for smoothness or when the smooth_yi array is completely filled. It then returns the index of the last integer in cand_yi that has been checked for smoothness.

This function uses the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers" except that this function has been tailored to better suit the factorization problem.

Note:: This function is very similar to bern_21_rt_pairs_lp. The only difference is that here no remainder tree is computed. This can sometimes be faster than the full fledged version.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[in]`	n	The integer to factor.
`[in]`	htable	A pointer to the hashtable used for the large prime variation.
`[out]`	xi	A pointer to the {x_i} associated to the {p_j}-smooth y_i integer.
`[out]`	smooth_yi	A pointer to the {p_j}-smooth y_i integer.
`[in]`	cand_xi	A pointer to the list of the x_i integers.
`[in]`	cand_yi	A pointer to the list of the y_i integers.
`[in]`	z	The product of the the p_j prime numbers in the facotr base.

Returns:: The index of the last integer in cand_yi that has been checked for smoothness.

uint32_t bern_21_rt	(	mpz_array_t *const	smooth,
		const mpz_array_t *const	xi,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 (with computation of a remainder tree).

Given the prime numbers p_j listed by pj and the positive integers x_i listed by xi, determines the {p_j}-smooth part of each x_i and stores them in smooth, so that smooth->data[i] is the {p_j}-smooth part of xi->data[i].

The function stops when each integer from xi has been checked for smoothness or when the smooth array is completely filled. It then returns the index of the last integer in xi that has been checked for smoothness.

This is the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers".

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[out]`	smooth	A pointer to the {p_j}-smooth parts of each x_i integer.
`[in]`	xi	A pointer to the list of the x_i integers.
`[in]`	z	The product of the the p_j prime numbers in the facotr base.

Returns:: The index of the last integer in xi that has been checked for smoothness.

uint32_t bern_21_rt_pairs	(	mpz_array_t *const	xi,
		mpz_array_t *const	smooth_yi,
		const mpz_array_t *const	cand_xi,
		const mpz_array_t *const	cand_yi,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 modified.

Given the prime numbers p_j listed by pj and the positive integers y_i listed by cand_yi, determines the y_i that are {p_j}-smooth and stores them in smooth_yi, so that smooth_yi->data[i] is indeed {p_j}-smooth.

In a typical factorization problem, we other found ourselves in situations where each y_i is associated to another integer x_i. The x_i associated to the {p_j}-smooth y_i are hence stored in xi.

The function stops when each integer from cand_yi has been checked for smoothness or when the smooth_yi array is completely filled. It then returns the index of the last integer in cand_yi that has been checked for smoothness.

This function uses the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers" except that this function has been tailored to better suit the factorization problem.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[out]`	xi	A pointer to the {x_i} associated to the {p_j}-smooth y_i integer.
`[out]`	smooth_yi	A pointer to the {p_j}-smooth y_i integer.
`[in]`	cand_xi	A pointer to the list of the x_i integers.
`[in]`	cand_yi	A pointer to the list of the y_i integers.
`[in]`	z	The product of the the p_j prime numbers in the facotr base.

Returns:: The index of the last integer in cand_yi that has been checked for smoothness.

uint32_t bern_21_rt_pairs_lp	(	const mpz_t	n,
		hashtable_t *const	htable,
		mpz_array_t *const	xi,
		mpz_array_t *const	smooth_yi,
		const mpz_array_t *const	cand_xi,
		const mpz_array_t *const	cand_yi,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 modified, with large primes variation.

Given z, the product of prime numbers p_j and the positive integers y_i listed by cand_yi, determines the y_i that are {p_j}-smooth and stores them in smooth_yi, so that smooth_yi->data[i] is indeed {p_j}-smooth.

In a typical factorization problem, we other found ourselves in situations where each y_i is associated to another integer x_i. The x_i associated to the {p_j}-smooth y_i are hence stored in xi.

Moreover, this function implements the so-called large primes variation. If a given y_i is not {p_j}-smooth but is the product of a prime p by a {p_j}-smooth number, it is stored in the hashtable htable. Subsequently, if another y_j is the product of a {p_j}-smooth number by the same prime number p, then y_i*y_j/(p^2) is stored in smooth_yi and x_i*x_j*pinv is stored in xi where pinv is the inverse of p in Z/cZ.

The function stops when each integer from cand_yi has been checked for smoothness or when the smooth_yi array is completely filled. It then returns the index of the last integer in cand_yi that has been checked for smoothness.

This function uses the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers" except that this function has been tailored to better suit the factorization problem.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[in]`	n	The integer to factor.
`[in]`	htable	A pointer to the hashtable used for the large prime variation.
`[out]`	xi	A pointer to the {x_i} associated to the {p_j}-smooth y_i integer.
`[out]`	smooth_yi	A pointer to the {p_j}-smooth y_i integer.
`[in]`	cand_xi	A pointer to the list of the x_i integers.
`[in]`	cand_yi	A pointer to the list of the y_i integers.
`[in]`	z	The product of the the p_j prime numbers in the facotr base.

Returns:: The index of the last integer in cand_yi that has been checked for smoothness.

uint32_t bern_21_rt_pairs_lp_siqs	(	const mpz_t	n,
		hashtable_t *const	htable,
		mpz_array_t *const	xi,
		mpz_array_t *const	smooth_yi,
		mpz_array_t *const	a_for_smooth_yi,
		const mpz_array_t *const	cand_xi,
		const mpz_array_t *const	cand_yi,
		const mpz_array_t *const	cand_a,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 modified for SIQS, with large primes variation (with computation of a remainder tree).

Given z, the product of prime numbers p_j and the positive integers y_i listed by cand_yi, determines the y_i that are {p_j}-smooth and stores them in smooth_yi, so that smooth_yi->data[i] is indeed {p_j}-smooth.

In a typical factorization problem, we other found ourselves in situations where each y_i is associated to another integer x_i. The x_i associated to the {p_j}-smooth y_i are hence stored in xi.

Moreover, this function implements the so-called large primes variation. If a given y_i is not {p_j}-smooth but is the product of a prime p by a {p_j}-smooth number, it is stored in the hashtable htable. Subsequently, if another y_j is the product of a {p_j}-smooth number by the same prime number p, then y_i*y_j/(p^2) is stored in smooth_yi and x_i*x_j*pinv is stored in xi where pinv is the inverse of p in Z/cZ.

The function stops when each integer from cand_yi has been checked for smoothness or when the smooth_yi array is completely filled. It then returns the index of the last integer in cand_yi that has been checked for smoothness.

This function uses the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers" except that this function has been tailored to better suit the factorization problem, particularly to our SIQS implementation where we need to keep track of additionnal a_i integers associated to each y_i integers. These extra integers are stored in cand_a whereas the a_i associated to the smooth y_i will be stored in the a_for_smooth_gx array.

Note:: The a_i integers are actually the values of the first parameter of the polynomials used in the SIQS algorithm.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[in]`	n	The integer to factor.
`[in]`	htable	A pointer to the hashtable used for the large prime variation.
`[out]`	xi	A pointer to the `x_i` associated to the {p_j}-smooth `y_i` integer.
`[out]`	smooth_yi	A pointer to the {p_j}-smooth `y_i` integer.
`[out]`	a_for_smooth_yi	A pointer to the array of the `a_i` integers.
`[in]`	cand_xi	A pointer to the list of the `x_i` integers.
`[in]`	cand_yi	A pointer to the list of the `y_i` integers.
`[in]`	cand_a	A pointer to the list of the `a_i` integers associated to the {p_j}-smooth y_i integers.
`[in]`	z	The product of the the `p_j` prime numbers in the factor base.

Returns:: The index of the last integer in cand_yi that has been checked for smoothness.

uint32_t bern_21_rt_pairs_siqs	(	mpz_array_t *const	xi,
		mpz_array_t *const	smooth_yi,
		mpz_array_t *const	a_for_smooth_gx,
		const mpz_array_t *const	cand_xi,
		const mpz_array_t *const	cand_yi,
		const mpz_array_t *const	cand_a,
		const mpz_t	z
	)

Daniel J. Bernstein's algorithm 2.1 modified for SIQS (with computation of a remainder tree).

Given z, the product of prime numbers p_j and the positive integers y_i listed by cand_yi, determines the y_i that are {p_j}-smooth and stores them in smooth_yi, so that smooth_yi->data[i] is indeed {p_j}-smooth.

In a typical factorization problem, we other found ourselves in situations where each y_i is associated to another integer x_i. The x_i associated to the {p_j}-smooth y_i are hence stored in xi.

The function stops when each integer from cand_yi has been checked for smoothness or when the smooth_yi array is completely filled. It then returns the index of the last integer in cand_yi that has been checked for smoothness.

This function uses the algorithm 2.1 described in Daniel J. Bernstein's paper: "How to find smooth parts of integers" except that this function has been tailored to better suit the factorization problem, particularly to our SIQS implementation where we need to keep track of additionnal a_i integers associated to each y_i integers. These extra integers are stored in cand_a whereas the a_i associated to the smooth y_i will be stored in the a_for_smooth_gx array.

Note:: The a_i integers are actually the values of the first parameter of the polynomials used in the SIQS algorithm.

See also:: Daniel J. Bernstein's paper: "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf

Parameters:

`[out]`	xi	A pointer to the `x_i` associated to the {p_j}-smooth `y_i` integer.
`[out]`	smooth_yi	A pointer to the {p_j}-smooth `y_i` integer.
`[out]`	a_for_smooth_gx	A pointer to the array of the `a_i` integers.
`[in]`	cand_xi	A pointer to the list of the `x_i` integers.
`[in]`	cand_yi	A pointer to the list of the `y_i` integers.
`[in]`	cand_a	A pointer to the list of the `a_i` integers associated to the {p_j}-smooth y_i integers.
`[in]`	z	The product of the the `p_j` prime numbers in the factor base.

Returns:: The index of the last integer in cand_yi that has been checked for smoothness.

mpz_t* bern_51	(	uint32_t	b,
		const mpz_t	u
	)

Daniel J. Bernstein's algorithm 5.1.

Given a positive integer b and an odd positive integer u, returns a non negative integer v < 2^b such that 1 + u*v = 0 (mod 2^b).

This is the algorithm 5.1 described in Daniel J. Bernstein's paper: "How to find small factors of integers".

See also:: Daniel J. Bernstein's paper: "How to find small factors of integers", http://cr.yp.to/papers/sf.pdf

Parameters:

`[in]`	b	A positive integer.
`[in]`	u	An odd positive `mpz_t` integer.

Returns:: A non negative mpz_t integer v < 2^b such that 1 + u*v = 0 (mod 2^b).

mpz_t* bern_53	(	uint32_t	b,
		const mpz_t	u,
		const mpz_t	x
	)

Daniel J. Bernstein's algorithm 5.3.

Given an odd positive integer u < 2^c and a non negative integer x < 2^(b + c), returns a non negative integer r < 2^(c + 1) such that r*2^b = x (mod u).

This is the algorithm 5.3 described in Daniel J. Bernstein's paper: "How to find small factors of integers".

See also:: Daniel J. Bernstein's paper: "How to find small factors of integers", http://cr.yp.to/papers/sf.pdf

Parameters:

`[in]`	b	A positive integer.
`[in]`	u	An odd positive `mpz_t` integer.
`[in]`	x	An non negative `mpz_t` integer.

Returns:: A non negative mpz_t integer r such that r*2^b = x (mod u).

uint32_array_t* bern_63	(	const mpz_t	x,
		const mpz_array_t *const	tree
	)

Daniel J. Bernstein's algorithm 6.3.

Given a non negative integer x and given the product tree tree of a sequence of odd positive integers p_i, returns the integers p_i such that: x mod p_i = 0.

This is the algorithm 6.3 described in Daniel J. Bernstein's paper: "How to find small factors of integers".

See also:: Daniel J. Bernstein's paper: "How to find small factors of integers", http://cr.yp.to/papers/sf.pdf

Parameters:

`[in]`	x	A non negative positive integer.
`[in]`	tree	The product tree of a sequence of odd positive integers p_i.

Returns:: A pointer to an uint32_array_t holding the integers p_i such that: x mod p_i = 0.

void bern_71	(	uint32_array_list_t *const	decomp_list,
		const mpz_array_t *const	to_be_factored,
		const uint32_array_t *const	odd_primes
	)

Daniel J. Bernstein's algorithm 7.1.

Given a sequence of odd primes p_j given by odd_primes and a set of integers n_i given by to_be_factored, determines, for each n_i, the list of odd primes p_j such that (n_i mod p_j = 0) and stores them in decomp_list. Each entry in decomp_list->data[i] is a pointer to a mpz_array_t listing the p_j for the integer to_be_factored->data[i].

This is the algorithm 7.1 described in Daniel J. Bernstein's paper: "How to find small factors of integers".

See also:: Daniel J. Bernstein's paper: "How to find small factors of integers", http://cr.yp.to/papers/sf.pdf

Parameters:

`[out]`	decomp_list	A pointer to the list of matching p_j for each n_i.
`[in]`	to_be_factored	A pointer to the set of integers n_i.
`[in]`	odd_primes	A pointer to the set of integers p_j.

uint32_t djb_batch_rt	(	smooth_filter_t *const	filter,
		unsigned long int	step
	)

Daniel J. Bernstein's algorithm 2.1 adapted to be used with a smooth_filter_t.

If `filter->nsteps` == 0

In such a case, no early abort strategy is performed. The effect of the function is the same as bern_21_*_pairs_* called with:

    filter->n
    filter->htable
    filter->accepted_xi
    filter->accepted_yi
    filter->accepted_ai
    filter->candidate_xi
    filter->candidate_yi
    filter->candidate_ai
    filter->prod_pj[0]

If `filter->nsteps` != 0

An early abort strategy is performed.

If 1 <= step < filter->nsteps:
Relations at step step-1 from filter, (filter->filtered_*[step-1]) are used as "candidate" arrays to populate either filter->accepted_* or filter->filtered_*[step].

If step == 0:
The candidate relations are taken from filter->candidate_*.

If step == filter->nsteps:
The candidate relations are taken from filter->filtered_*[filter->nsteps - 1] and 'good' relations will be stored in filter->accepted_*.

See also:: The bern_21_* functions.

Warning:: Using filter->nsteps != 0 is not recommended. First, it certainly does not make any sense to try to early-abort the batch. Second, even if it is useful (for some weird reasons that I'm not aware of), the cases filter->nsteps != 0 have not been tuned / fully debugged.

Parameters:

	filter	pointer to the `smooth_filter_t` to use
	step	the step number in the early abort strategy

Returns:: The number of relations used from the "candidate" arrays.


Defines
#define	_TIFA_BERNSTEINISMS_H_
Functions
mpz_t *	bern_51 (uint32_t b, const mpz_t u)
	Daniel J. Bernstein's algorithm 5.1.
mpz_t *	bern_53 (uint32_t b, const mpz_t u, const mpz_t x)
	Daniel J. Bernstein's algorithm 5.3.
uint32_array_t *	bern_63 (const mpz_t x, const mpz_array_t *const tree)
	Daniel J. Bernstein's algorithm 6.3.
void	bern_71 (uint32_array_list_t const decomp_list, const mpz_array_t const to_be_factored, const uint32_array_t *const odd_primes)
	Daniel J. Bernstein's algorithm 7.1.
uint32_t	bern_21_rt (mpz_array_t const smooth, const mpz_array_t const xi, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 (with computation of a remainder tree).
uint32_t	bern_21 (mpz_array_t const smooth, const mpz_array_t const xi, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 (without computation of a remainder tree).
uint32_t	bern_21_rt_pairs (mpz_array_t const xi, mpz_array_t const smooth_yi, const mpz_array_t const cand_xi, const mpz_array_t const cand_yi, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 modified.
uint32_t	bern_21_pairs (mpz_array_t const xi, mpz_array_t const smooth_yi, const mpz_array_t const cand_xi, const mpz_array_t const cand_yi, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 modified (without computation of a remainder tree).
uint32_t	bern_21_rt_pairs_lp (const mpz_t n, hashtable_t const htable, mpz_array_t const xi, mpz_array_t const smooth_yi, const mpz_array_t const cand_xi, const mpz_array_t *const cand_yi, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 modified, with large primes variation.
uint32_t	bern_21_pairs_lp (const mpz_t n, hashtable_t const htable, mpz_array_t const xi, mpz_array_t const smooth_yi, const mpz_array_t const cand_xi, const mpz_array_t *const cand_yi, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 modified, with large primes variation (without computation of a remainder tree).
uint32_t	bern_21_rt_pairs_siqs (mpz_array_t const xi, mpz_array_t const smooth_yi, mpz_array_t const a_for_smooth_gx, const mpz_array_t const cand_xi, const mpz_array_t const cand_yi, const mpz_array_t const cand_a, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 modified for SIQS (with computation of a remainder tree).
uint32_t	bern_21_rt_pairs_lp_siqs (const mpz_t n, hashtable_t const htable, mpz_array_t const xi, mpz_array_t const smooth_yi, mpz_array_t const a_for_smooth_yi, const mpz_array_t const cand_xi, const mpz_array_t const cand_yi, const mpz_array_t *const cand_a, const mpz_t z)
	Daniel J. Bernstein's algorithm 2.1 modified for SIQS, with large primes variation (with computation of a remainder tree).
uint32_t	djb_batch_rt (smooth_filter_t *const filter, unsigned long int step)
	Daniel J. Bernstein's algorithm 2.1 adapted to be used with a `smooth_filter_t`.

bernsteinisms.h File Reference

Defines

Functions

Detailed Description

Define Documentation

Function Documentation

If filter->nsteps == 0

If filter->nsteps != 0

If `filter->nsteps` == 0

If `filter->nsteps` != 0