00001 // Copyright (C) 2011 CNRS - Ecole Polytechnique - INRIA. 00002 // 00003 // This file is part of TIFA. 00004 // 00005 // TIFA is free software; you can redistribute it and/or modify it under the 00006 // terms of the GNU Lesser General Public License as published by the Free 00007 // Software Foundation; either version 2.1 of the License, or (at your option) 00008 // any later version. 00009 // 00010 // TIFA is distributed in the hope that it will be useful, but WITHOUT ANY 00011 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 00012 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for 00013 // more details. 00014 // 00015 // You should have received a copy of the GNU Lesser General Public License 00016 // along with this library; if not, write to the Free Software Foundation, 00017 // Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00018 00029 #if !defined(_TIFA_SIQS_SIEVE_H_) 00030 #define _TIFA_SIQS_SIEVE_H_ 00031 00032 #include <stdint.h> 00033 #include <stdbool.h> 00034 00035 #include <gmp.h> 00036 00037 #include "exit_codes.h" 00038 #include "array.h" 00039 #include "approx.h" 00040 #include "buckets.h" 00041 #include "siqs_poly.h" 00042 #include "stopwatch.h" 00043 00044 #ifdef __cplusplus 00045 extern "C" { 00046 #endif 00047 00048 // 00049 // Logarithm (in base 2) of the largest size of a sieve chunk. The optimal 00050 // value is architecture dependant, so this value should be tweaked according 00051 // to the target processor. 00052 // 00053 // WARNING: Should be an integer in the [10..20] range. 00054 // 00055 #define LOG2_SIEVE_CHUNK_MAX_SIZE 15 00056 00057 // 00058 // Largest size of a sieve chunk. 00059 // 00060 // SIEVE_CHUNK_MAX_SIZE = 2^LOG2_SIEVE_CHUNK_MAX_SIZE 00061 // 00062 #if (LOG2_SIEVE_CHUNK_MAX_SIZE == 10) 00063 #define SIEVE_CHUNK_MAX_SIZE 1024 00064 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 11) 00065 #define SIEVE_CHUNK_MAX_SIZE 2048 00066 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 12) 00067 #define SIEVE_CHUNK_MAX_SIZE 4096 00068 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 13) 00069 #define SIEVE_CHUNK_MAX_SIZE 8192 00070 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 14) 00071 #define SIEVE_CHUNK_MAX_SIZE 16384 00072 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 15) 00073 #define SIEVE_CHUNK_MAX_SIZE 32768 00074 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 16) 00075 #define SIEVE_CHUNK_MAX_SIZE 65536 00076 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 17) 00077 #define SIEVE_CHUNK_MAX_SIZE 131072 00078 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 18) 00079 #define SIEVE_CHUNK_MAX_SIZE 262144 00080 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 19) 00081 #define SIEVE_CHUNK_MAX_SIZE 524288 00082 #elif (LOG2_SIEVE_CHUNK_MAX_SIZE == 20) 00083 #define SIEVE_CHUNK_MAX_SIZE 1048576 00084 #else 00085 #error "LOG2_SIEVE_CHUNK_MAX_SIZE should be in [10..20]" 00086 #endif 00087 00088 // 00089 // Do not sieve for the NPRIMES_TO_SKIP smallest primes in the factor base 00090 // 00091 #define NPRIMES_TO_SKIP 20 00092 // 00093 // Smallest prime index for which a bucket sieve is performed 00094 // 00095 #define BUCKETS_SMALLEST_PRIME 2400 00096 00097 #if (NPRIMES_TO_SKIP == 0) 00098 // 00099 // Sieving for the prime 2 is done separately... 00100 // 00101 #define SIEVE_WITH_2 1 00102 #undef NPRIMES_TO_SKIP 00103 #define NPRIMES_TO_SKIP 1 00104 #else 00105 #define SIEVE_WITH_2 0 00106 #endif 00107 00108 // 00109 // If ROUND_HALF_WIDTH is not zero, round the half-width to the nearest 00110 // multiple of SIEVE_CHUNK_MAX_SIZE (unless if the half-width is less than 00111 // SIEVE_CHUNK_MAX_SIZE). 00112 // 00113 #define ROUND_HALF_WIDTH 0 00114 00122 struct struct_siqs_sieve_t { 00127 uint32_t nchunks; 00132 uint32_t chunk_size; 00137 int32_t next_chunkno_to_fill; 00141 uint32_t scan_begin; 00146 uint32_t threshold; 00150 byte_array_t* log_primes; 00154 byte_array_t* sieve; 00158 siqs_poly_t* poly; 00163 int32_array_t *sol1; 00168 int32_array_t *sol2; 00173 #if !ROUND_HALF_WIDTH 00174 uint32_t endlast; 00175 #endif 00176 00180 bool use_buckets; 00185 uint32_t nprimes_no_buckets; 00190 uint32_t buckets_first_prime; 00194 buckets_t* buckets_positive; 00198 buckets_t* buckets_negative; 00202 stopwatch_t init_poly_timer; 00206 stopwatch_t fill_timer; 00210 stopwatch_t scan_timer; 00211 }; 00212 00217 typedef struct struct_siqs_sieve_t siqs_sieve_t; 00218 00234 siqs_sieve_t* alloc_siqs_sieve( 00235 mpz_t n, 00236 uint32_array_t* const factor_base, 00237 byte_array_t* const log_primes, 00238 uint32_array_t* const sqrtm_pi, 00239 uint32_t half_width 00240 ); 00241 00253 void free_siqs_sieve(siqs_sieve_t* sieve); 00254 00265 ecode_t fill_sieve(siqs_sieve_t* const sieve); 00266 00276 ecode_t scan_sieve( 00277 siqs_sieve_t* const sieve, 00278 int32_array_t* const survivors, 00279 uint32_t nsurvivors 00280 ); 00281 00291 void set_siqs_sieve_threshold(siqs_sieve_t* const sieve, uint32_t threshold); 00292 00300 void print_init_poly_timing(siqs_sieve_t* const sieve); 00301 00309 void print_fill_timing(siqs_sieve_t* const sieve); 00310 00318 void print_scan_timing(siqs_sieve_t* const sieve); 00319 00320 #ifdef __cplusplus 00321 } 00322 #endif 00323 00324 #endif 00325 00326