include/flint/fmpz_factor.h

0001 /*
0002     Copyright (C) 2011 Fredrik Johansson
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef FMPZ_FACTOR_H
0013 #define FMPZ_FACTOR_H
0014
0015 #ifdef FMPZ_FACTOR_INLINES_C
0016 #define FMPZ_FACTOR_INLINE
0017 #else
0018 #define FMPZ_FACTOR_INLINE static inline \
0019  error fmpz_factor/inline.c currently does not exist as no function has been inlined
0020 #endif
0021
0022 #include "fmpz_types.h"
0023
0024 #ifdef __cplusplus
0025 extern "C" {
0026 #endif
0027
0028 /* Utility functions *********************************************************/
0029
0030 void fmpz_factor_init(fmpz_factor_t factor);
0031 void fmpz_factor_clear(fmpz_factor_t factor);
0032
0033 void _fmpz_factor_fit_length(fmpz_factor_t factor, slong len);
0034 void _fmpz_factor_set_length(fmpz_factor_t factor, slong newlen);
0035
0036 void _fmpz_factor_append(fmpz_factor_t factor, const fmpz_t p, ulong exp);
0037 void _fmpz_factor_append_ui(fmpz_factor_t factor, ulong p, ulong exp);
0038
0039 void _fmpz_factor_concat(fmpz_factor_t factor1, fmpz_factor_t factor2, ulong exp);
0040
0041 /* I/O ***********************************************************************/
0042
0043 #ifdef FLINT_HAVE_FILE
0044 int fmpz_factor_fprint(FILE * fs, const fmpz_factor_t factor);
0045 #endif
0046 int fmpz_factor_print(const fmpz_factor_t factor);
0047
0048 /* Factoring *****************************************************************/
0049
0050 void _fmpz_factor_extend_factor_ui(fmpz_factor_t factor, ulong n);
0051
0052 int fmpz_factor_trial_range(fmpz_factor_t factor, const fmpz_t n, ulong start, ulong num_primes);
0053 int fmpz_factor_trial(fmpz_factor_t factor, const fmpz_t n, slong num_primes);
0054
0055 void fmpz_factor_no_trial(fmpz_factor_t factor, const fmpz_t n);
0056
0057 void fmpz_factor_si(fmpz_factor_t factor, slong n);
0058 void fmpz_factor(fmpz_factor_t factor, const fmpz_t n);
0059
0060 int fmpz_factor_smooth(fmpz_factor_t factor, const fmpz_t n, slong bits, int proved);
0061
0062 int fmpz_factor_pp1(fmpz_t factor, const fmpz_t n, ulong B1, ulong B2_sqrt, ulong c);
0063
0064 void fmpz_factor_refine(fmpz_factor_t res, const fmpz_factor_t f);
0065
0066 void flint_mpn_sqr_and_add_a(nn_ptr y, nn_ptr a, nn_ptr n, ulong n_size, nn_ptr ninv, ulong normbits);
0067
0068 int flint_mpn_factor_pollard_brent_single(nn_ptr factor, nn_ptr n, nn_ptr ninv, nn_ptr a, nn_ptr y, ulong n_size, ulong normbits, ulong max_iters);
0069 int fmpz_factor_pollard_brent_single(fmpz_t p_factor, fmpz_t n_in, fmpz_t yi, fmpz_t ai, ulong max_iters);
0070 int fmpz_factor_pollard_brent(fmpz_t factor, flint_rand_t state, fmpz_t n, ulong max_tries, ulong max_iters);
0071
0072 /* Expansion *****************************************************************/
0073
0074 void fmpz_factor_expand_iterative(fmpz_t n, const fmpz_factor_t factor);
0075 void fmpz_factor_expand_multiexp(fmpz_t n, const fmpz_factor_t factor);
0076 void fmpz_factor_expand(fmpz_t n, const fmpz_factor_t factor);
0077
0078 /* Multiplicative functions **************************************************/
0079
0080 void fmpz_factor_euler_phi(fmpz_t res, const fmpz_factor_t fac);
0081
0082 int fmpz_factor_moebius_mu(const fmpz_factor_t fac);
0083
0084 void fmpz_factor_divisor_sigma(fmpz_t res, ulong k, const fmpz_factor_t fac);
0085
0086 /* ECM Factoring functions ***************************************************/
0087
0088 typedef struct ecm_s
0089 {
0090     nn_ptr t, u, v, w;  /* temp variables */
0091     nn_ptr x, z;    /* the coordinates */
0092     nn_ptr a24;     /* value (a + 2)/4 */
0093     nn_ptr ninv;    /* invere of n */
0094     nn_ptr one;     /* one shifted */
0095
0096     unsigned char *GCD_table; /* checks whether baby step int is
0097                            coprime to Primorial or not */
0098
0099     unsigned char **prime_table;
0100
0101     ulong n_size;
0102     ulong normbits;
0103
0104 } ecm_s;
0105
0106 typedef ecm_s ecm_t[1];
0107
0108 void fmpz_factor_ecm_init(ecm_t ecm_inf, ulong sz);
0109 void fmpz_factor_ecm_clear(ecm_t ecm_inf);
0110 void fmpz_factor_ecm_double(nn_ptr x, nn_ptr z, nn_ptr x0, nn_ptr z0, nn_ptr n, ecm_t ecm_inf);
0111 void fmpz_factor_ecm_add(nn_ptr x, nn_ptr z, nn_ptr x1, nn_ptr z1, nn_ptr x2, nn_ptr z2, nn_ptr x0, nn_ptr z0, nn_ptr n, ecm_t ecm_inf);
0112 void fmpz_factor_ecm_mul_montgomery_ladder(nn_ptr x, nn_ptr z, nn_ptr x0, nn_ptr z0, ulong k, nn_ptr n, ecm_t ecm_inf);
0113 int fmpz_factor_ecm_select_curve(nn_ptr f, nn_ptr sig, nn_ptr n, ecm_t ecm_inf);
0114 int fmpz_factor_ecm_stage_I(nn_ptr f, const ulong *prime_array, ulong num, ulong B1, nn_ptr n, ecm_t ecm_inf);
0115 int fmpz_factor_ecm_stage_II(nn_ptr f, ulong B1, ulong B2, ulong P, nn_ptr n, ecm_t ecm_inf);
0116 int fmpz_factor_ecm(fmpz_t f, ulong curves, ulong B1, ulong B2, flint_rand_t state, const fmpz_t n_in);
0117
0118 /* Inlines *******************************************************************/
0119
0120 void fmpz_factor_get_fmpz(fmpz_t z, const fmpz_factor_t factor, slong i);
0121
0122 #ifdef __cplusplus
0123 }
0124 #endif
0125
0126 #endif