smallfactor.h (1081B)
1 #ifndef SMALLFACTOR_H 2 #define SMALLFACTOR_H 3 4 #include <assert.h> 5 #include <flint.h> 6 #include <fmpz.h> 7 #include <stdlib.h> 8 9 #include "context.h" 10 11 #define SMALLFACTOR_FOUND 1 12 #define SMALLFACTOR_NOT_FOUND 0 13 14 /** 15 * Euclidean small factor finder 16 * 17 * Try to find a small, non-trivial, factor of the number n. This is 18 * done by computing gcd(n, p) where p is the product of all primes less 19 * than 2^16. If SMALLFACTOR_FOUND is returned the out variable is set 20 * to a non-trivial factor of n. If this does not find a non-trivial 21 * factor SMALLFACTOR_NOT_FOUND is returned. 22 * 23 * This is often quicker than trial division if we want a cheap way of 24 * filtering out composite numbers with small factors form a list of 25 * composite numbers where most of the numbers only have large factors. 26 * 27 * @param out where to write the output 28 * @param n the number to try to find factors of 29 * @returns 30 * SMALLFACTOR_FOUND if out was set to a nontrivial factor of n 31 * SMALLFACTOR_NOT_FOUND otherwise 32 */ 33 size_t smallfactor_euclidean(ctx_t *ctx, fmpz_t out, const fmpz_t n); 34 35 #endif