#include <inttypes.h>
#include <array.h>
#include <hashtable.h>
#include <gmp.h>
Go to the source code of this file.
Data Structures | |
| struct | struct_smooth_filter_t |
| Structure grouping variables needed for multi-step early abort strategy. More... | |
Defines | |
| #define | _TIFA_SMOOTH_FILTER_H_ |
| #define | MAX_NSTEPS 4 |
Typedefs | |
|
typedef struct struct_smooth_filter_t | smooth_filter_t |
Equivalent to struct struct_smooth_filter_t. | |
|
typedef enum smooth_filter_method_enum | smooth_filter_method_t |
Equivalent to enum smooth_filter_method_enum. | |
Enumerations | |
| enum | smooth_filter_method_enum { TDIV = 0, TDIV_EARLY_ABORT, DJB_BATCH } |
Functions | |
| void | complete_filter_init (smooth_filter_t *const filter, uint32_array_t *const base) |
Complete initialization of a smooth_filter_t. | |
| void | clear_smooth_filter (smooth_filter_t *const filter) |
Clears a smooth_filter_t. | |
| void | filter_new_relations (smooth_filter_t *const filter) |
| Filters new relations to keep 'good' ones. | |
| void | print_filter_status (smooth_filter_t *const filter) |
Prints the status of the buffers of a smooth_filter_t. | |
Variables | |
| static const char *const | filter_method_to_str [3] |
smooth_filter_t 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 (see bernsteinisms.h) instead of trial division.
smooth_filter_t structure?
The following code snippet, while incomplete, illustrates the way a smooth_filter_t should be used.
//
// Fill the with the smooth_filter_t with our parameters...
//
smooth_filter_t filter;
filter.n = n; // number to factor
filter.kn = kn; // number to factor x multiplier
filter.batch_size = 1024; // number of relations to perform a batch
filter.methid = TDIV_EARLY_ABORT; // use the early abort strategy
filter.nsteps = 2; // use a 2-step early abort strategy
filter.htable = htable;
filter.use_large_primes = true;
filter.use_siqs_batch_variant = false;
filter.base_size = factor_base->length; // size of factor base
filter.candidate_xi = candidate_xi; // candidate relations stored
filter.candidate_yi = candidate_yi; // in candidate_* arrays
filter.accepted_xi = accepted_xi; // 'good' relations stored
filter.accepted_yi = accepted_yi; // in accepted_* arrays
//
// Complete the filter initialization by allocating its internal
// buffers, computing the early abort bounds and the intermediate
// factor bases...
//
complete_filter_init(&filter, factor_base);
while (accepted_yi->length != nrels_to_collect) {
//
// While we don't have enough relations, create new ones and
// stores them in the candidate_* arrays such that
// yi = xi^2 (mod kn). (The generate_relations function here
// is completely fictitious)
//
generate_relations(candidate_xi, candidate_yi);
//
// Select 'good' relations such that yi = xi^2 (mod kn) with
// yi smooth. Note that pointers to the candidate_* and
// accepted_* arrays were given in the filter structure.
//
filter_new_relations(&filter);
}
//
// This clears _only_ the memory allocated by complete_init_filter.
//
clear_smooth_filter(&filter);
Definition in file smooth_filter.h.
| #define _TIFA_SMOOTH_FILTER_H_ |
Standard include guard.
Definition at line 95 of file smooth_filter.h.
| #define MAX_NSTEPS 4 |
Maximum number of steps used in the multi-step early abort strategy.
Definition at line 110 of file smooth_filter.h.
An enumeration of the possible methods used to test residue smoothness.
| TDIV | Simple trial division. |
| TDIV_EARLY_ABORT | Simple trial division with (multi-step) early abort. |
| DJB_BATCH | D. Bernstein's batch method described in "How to find smooth parts of integers", http://cr.yp.to/factorization/smoothparts-20040510.pdf. |
Definition at line 117 of file smooth_filter.h.
| void clear_smooth_filter | ( | smooth_filter_t *const | filter | ) |
Clears a smooth_filter_t.
Clears the memory of a smooth_filter_t that was allocated by complete_filter_init().
candidate_* arrays or the htable hashtable. | void complete_filter_init | ( | smooth_filter_t *const | filter, | |
| uint32_array_t *const | base | |||
| ) |
Complete initialization of a smooth_filter_t.
Complete the initialization of a smooth_filter_t by allocating needed memory space.
n kn nsteps batch_size base_size htable candidate_xi candidate_yi accepted_xi accepted_yi use_large_primes use_siqs_batch_variant candidate_* arrays since the structure just refers to them, but does not own them.
nsteps > MAX_NSTEPS then complete_filter_init will set it to MAX_NSTEPS.method == DJB_BATCH then nsteps will be set to 0 and no early abort will be performed.| filter | a pointer to the smooth_filter_t to initialize | |
| base | a pointer to the complete factor base used |
| void filter_new_relations | ( | smooth_filter_t *const | filter | ) |
Filters new relations to keep 'good' ones.
Filters the relations given by filter->candidate_* via a smoothness detecting batch using a filter->nsteps steps early abort strategy and stores the 'good' relations in filter->accepted_*. Has no effect if the filter->candidate_* are not full since we need filter->batch_size relations to perform a batch.
| filter | a pointer to the smooth_filter_t used |
| void print_filter_status | ( | smooth_filter_t *const | filter | ) |
Prints the status of the buffers of a smooth_filter_t.
Prints a status summary of the internal buffers of a smooth_filter_t on the standard output.
| filter | a pointer to the smooth_filter_t to inspect |
const char* const filter_method_to_str[3] [static] |
Initial value:
{
"trial division",
"trial division + early abort",
"batch",
}
Definition at line 143 of file smooth_filter.h.