#include <smooth_filter.h>
Data Fields | |
| mpz_ptr | n |
| mpz_ptr | kn |
| smooth_filter_method_t | method |
| unsigned short int | nsteps |
| unsigned long int | batch_size |
| unsigned long int | base_size |
| uint32_array_t * | complete_base |
| uint32_array_t * | factor_base [MAX_NSTEPS] |
| mpz_array_t * | candidate_xi |
| mpz_array_t * | candidate_yi |
| mpz_array_t * | candidate_ai |
| mpz_array_t * | accepted_xi |
| mpz_array_t * | accepted_yi |
| mpz_array_t * | accepted_ai |
| mpz_array_t * | filtered_xi [MAX_NSTEPS] |
| mpz_array_t * | filtered_yi [MAX_NSTEPS] |
| mpz_array_t * | filtered_ai [MAX_NSTEPS] |
| mpz_array_t * | cofactors [MAX_NSTEPS] |
| mpz_t | bounds [MAX_NSTEPS] |
| mpz_t | prod_pj [MAX_NSTEPS+1] |
| hashtable_t * | htable |
| bool | use_large_primes |
| bool | use_siqs_variant |
lib/utils/include/smooth_filter.h
This structure and its associated functions implement the multi-step early abort strategy in a way reminiscent of Pomerance's suggestion in "Analysis and Comparison of Some Integer Factoring Algorithm" with the exception that the smoothness tests are performed by batch instead of trial division.
C. Pomerance, Analysis and Comparison of Some Integer Factoring Algorithm, in Mathematical Centre Tracts 154.
Definition at line 171 of file smooth_filter.h.
| mpz_ptr struct_smooth_filter_t::n |
The number to factor.
Definition at line 175 of file smooth_filter.h.
| mpz_ptr struct_smooth_filter_t::kn |
The number to factor multiplied by a multiplier.
Definition at line 179 of file smooth_filter.h.
The method to use for smooth residue detection.
Definition at line 183 of file smooth_filter.h.
| unsigned short int struct_smooth_filter_t::nsteps |
The number of steps in the early abort strategy. If nsteps == 0 no early abort is performed.
nsteps should be less than or equal to MAX_NSTEPS. Definition at line 190 of file smooth_filter.h.
| unsigned long int struct_smooth_filter_t::batch_size |
Number of relations to accumulate before testing for smoothness.
Definition at line 194 of file smooth_filter.h.
| unsigned long int struct_smooth_filter_t::base_size |
Size of the complete factor base.
Definition at line 198 of file smooth_filter.h.
Pointer to the complete factor base.
Definition at line 202 of file smooth_filter.h.
| uint32_array_t* struct_smooth_filter_t::factor_base[MAX_NSTEPS] |
Array giving the factor base to use at each step if we use the early-abort strategy.
Definition at line 207 of file smooth_filter.h.
The candidate x's. Together with candidate_yi, stores candidate relations verifying x^2 (mod kn) == y (mod kn)
candidate_ai if use_siqs_batch_variant is true. In that case the relations become x^2 (mod kn) == y * a (mod kn). Definition at line 216 of file smooth_filter.h.
The candidate y's. Together with candidate_xi, stores candidate relations verifying x^2 (mod kn) == y (mod kn)
candidate_ai if use_siqs_batch_variant is true. In that case the relations become x^2 (mod kn) == y * a (mod kn). Definition at line 225 of file smooth_filter.h.
Used only if use_siqs_batch_variant is true.
candidate_ai stores the a's (i.e. the value of the first parameter of the SIQS polynomial used). Together with candidate_xi and candidate_yi, stores candidate relations verifying x^2 (mod kn) == y * a (mod kn).
Definition at line 234 of file smooth_filter.h.
The accepted x's. Together with accepted_yi, stores 'good' relations verifying x^2 (mod kn) == y (mod kn) with y smooth over the factor base.
accepted_ai if use_siqs_batch_variant is true. In that case the relations become x^2 (mod kn) == y * a (mod kn). Definition at line 244 of file smooth_filter.h.
The accepted y's. Together with accepted_xi, stores 'good' relations verifying x^2 (mod kn) == y (mod kn) with y smooth over the factor base.
accepted_ai if use_siqs_batch_variant is true. In that case the relations become x^2 (mod kn) == y * a (mod kn). Definition at line 254 of file smooth_filter.h.
Used only if use_siqs_batch_variant is true.
The accepted a's (i.e. the value of the first parameter of the SIQS polynomial used). Together with accepted_xi, and accepted_yi, stores candidate relations verifying x^2 (mod kn) == y * a (mod kn) with y smooth over the factor base.
Definition at line 264 of file smooth_filter.h.
| mpz_array_t* struct_smooth_filter_t::filtered_xi[MAX_NSTEPS] |
The filtered_xi[s] array gives the filtered x's after s early abort steps. Together with filtered_yi[s] and cofactors[s], stores relations verifying x^2 (mod kn) == y * cofactor (mod kn) with cofactor smooth over the base composed by the partial_factor bases used in the early abort steps up to (and including) the s-th one, and with y less than bounds[s].
filtered_ai if use_siqs_batch_variant is true. In that case the relations become x^2 (mod kn) == y * a * cofactor (mod kn). Definition at line 278 of file smooth_filter.h.
| mpz_array_t* struct_smooth_filter_t::filtered_yi[MAX_NSTEPS] |
The filtered_yi[s] array gives the filtered x's after s early abort steps. See filtered_xi.
Definition at line 283 of file smooth_filter.h.
| mpz_array_t* struct_smooth_filter_t::filtered_ai[MAX_NSTEPS] |
The filtered_ai[s] array gives the filtered a's after s early abort steps. See filtered_xi.
Definition at line 288 of file smooth_filter.h.
| mpz_array_t* struct_smooth_filter_t::cofactors[MAX_NSTEPS] |
The cofactor[s] array gives the cofactors of the y's in filtered_yi[s] after s early abort steps. See filtered_xi.
Definition at line 293 of file smooth_filter.h.
| mpz_t struct_smooth_filter_t::bounds[MAX_NSTEPS] |
bounds[s] is the upper bound of the s-th early abort step. A relation will not pass this step if it has a 'y' greater than this bound.
Definition at line 299 of file smooth_filter.h.
| mpz_t struct_smooth_filter_t::prod_pj[MAX_NSTEPS+1] |
prod_pj[s] is the product of all the elements in the partial factor base at the s-th early abort step.
Definition at line 304 of file smooth_filter.h.
Hashtable used if the large prime variation is used. Can be NULL if the variation is not used.
Definition at line 309 of file smooth_filter.h.
true if and only if we are using the large prime variation.
Definition at line 313 of file smooth_filter.h.
true if and only if we are using this smooth_filter_t with SIQS.
Definition at line 318 of file smooth_filter.h.