1 /*
2     Copyright (C) 2009 William Hart
3 
4     This file is part of FLINT.
5 
6     FLINT is free software: you can redistribute it and/or modify it under
7     the terms of the GNU Lesser General Public License (LGPL) as published
8     by the Free Software Foundation; either version 2.1 of the License, or
9     (at your option) any later version.  See <http://www.gnu.org/licenses/>.
10 */
11 
12 #ifndef FMPZ_H
13 #define FMPZ_H
14 
15 #ifdef FMPZ_INLINES_C
16 #define FMPZ_INLINE FLINT_DLL
17 #else
18 #define FMPZ_INLINE static __inline__
19 #endif
20 
21 #undef ulong
22 #define ulong ulongxx/* interferes with system includes */
23 #include <stdlib.h>
24 #include <stdio.h>
25 #undef ulong
26 
27 #include <gmp.h>
28 #define ulong mp_limb_t
29 
30 #include "flint.h"
31 #include "nmod_vec.h"
32 #include "fmpz-conversions.h"
33 
34 #if HAVE_PTHREAD
35 #include <pthread.h>
36 #endif
37 
38 #ifdef __cplusplus
39  extern "C" {
40 #endif
41 
42 typedef slong fmpz;
43 typedef fmpz fmpz_t[1];
44 
45 typedef gmp_randstate_t fmpz_randstate_t;
46 
47 extern __mpz_struct * fmpz_arr;
48 extern gmp_randstate_t fmpz_randstate;
49 
50 typedef struct
51 {
52    mp_ptr dinv;
53    slong n;
54    flint_bitcnt_t norm;
55 } fmpz_preinvn_struct;
56 
57 typedef fmpz_preinvn_struct fmpz_preinvn_t[1];
58 
59 typedef struct
60 {
61    int count;
62 #if HAVE_PTHREAD
63    pthread_t thread;
64 #endif
65    void * address;
66 } fmpz_block_header_s;
67 
68 /* maximum positive value a small coefficient can have */
69 #define COEFF_MAX ((WORD(1) << (FLINT_BITS - 2)) - WORD(1))
70 
71 /* minimum negative value a small coefficient can have */
72 #define COEFF_MIN (-((WORD(1) << (FLINT_BITS - 2)) - WORD(1)))
73 
74 #define COEFF_IS_MPZ(x) (((x) >> (FLINT_BITS - 2)) == WORD(1))  /* is x a pointer not an integer */
75 
76 FLINT_DLL __mpz_struct * _fmpz_new_mpz(void);
77 
78 FLINT_DLL void _fmpz_clear_mpz(fmpz f);
79 
80 FLINT_DLL void _fmpz_cleanup_mpz_content(void);
81 
82 FLINT_DLL void _fmpz_cleanup(void);
83 
84 FLINT_DLL __mpz_struct * _fmpz_promote(fmpz_t f);
85 
86 FLINT_DLL __mpz_struct * _fmpz_promote_val(fmpz_t f);
87 
88 FMPZ_INLINE
_fmpz_demote(fmpz_t f)89 void _fmpz_demote(fmpz_t f)
90 {
91     /*
92        warning, if fmpz_demote changes, fmpz_zero must
93        also be changed to match
94     */
95     if (COEFF_IS_MPZ(*f))
96     {
97         _fmpz_clear_mpz(*f);
98         (*f) = WORD(0);
99     }
100 }
101 
102 FLINT_DLL void _fmpz_demote_val(fmpz_t f);
103 
104 FLINT_DLL void _fmpz_init_readonly_mpz(fmpz_t f, const mpz_t z);
105 
106 FLINT_DLL void _fmpz_clear_readonly_mpz(mpz_t);
107 
108 FMPZ_INLINE
fmpz_init(fmpz_t f)109 void fmpz_init(fmpz_t f)
110 {
111 	(*f) = WORD(0);
112 }
113 
114 FLINT_DLL void fmpz_init2(fmpz_t f, ulong limbs);
115 
116 FMPZ_INLINE
fmpz_init_set(fmpz_t f,const fmpz_t g)117 void fmpz_init_set(fmpz_t f, const fmpz_t g)
118 {
119     if (!COEFF_IS_MPZ(*g))
120     {
121         *f = *g;
122     }
123     else
124     {
125         __mpz_struct *ptr;
126 
127         ptr = _fmpz_new_mpz();
128         *f = PTR_TO_COEFF(ptr);
129         mpz_set(ptr, COEFF_TO_PTR(*g));
130     }
131 }
132 
133 FMPZ_INLINE
fmpz_init_set_ui(fmpz_t f,ulong g)134 void fmpz_init_set_ui(fmpz_t f, ulong g)
135 {
136     if (g <= COEFF_MAX)
137     {
138         *f = g;
139     }
140     else
141     {
142         __mpz_struct *ptr;
143 
144         ptr = _fmpz_new_mpz();
145         *f = PTR_TO_COEFF(ptr);
146         flint_mpz_set_ui(ptr, g);
147     }
148 }
149 
150 FMPZ_INLINE
fmpz_init_set_si(fmpz_t f,slong g)151 void fmpz_init_set_si(fmpz_t f, slong g)
152 {
153     if (COEFF_MIN <= g && g <= COEFF_MAX)
154     {
155         *f = g;
156     }
157     else
158     {
159         __mpz_struct *ptr;
160 
161         ptr = _fmpz_new_mpz();
162         *f = PTR_TO_COEFF(ptr);
163         flint_mpz_set_si(ptr, g);
164     }
165 }
166 
167 FMPZ_INLINE
fmpz_clear(fmpz_t f)168 void fmpz_clear(fmpz_t f)
169 {
170     if (COEFF_IS_MPZ(*f))
171         _fmpz_clear_mpz(*f);
172 }
173 
174 FLINT_DLL void fmpz_randbits(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
175 
176 FLINT_DLL void fmpz_randm(fmpz_t f, flint_rand_t state, const fmpz_t m);
177 
178 FLINT_DLL void fmpz_randtest(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
179 
180 FLINT_DLL void fmpz_randtest_unsigned(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
181 
182 FLINT_DLL void fmpz_randtest_not_zero(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
183 
184 FLINT_DLL void fmpz_randtest_mod(fmpz_t f, flint_rand_t state, const fmpz_t m);
185 
186 FLINT_DLL void fmpz_randtest_mod_signed(fmpz_t f, flint_rand_t state, const fmpz_t m);
187 
188 FLINT_DLL void fmpz_randprime(fmpz_t f, flint_rand_t state,
189                               flint_bitcnt_t bits, int proved);
190 
191 FLINT_DLL slong fmpz_get_si(const fmpz_t f);
192 
193 FLINT_DLL ulong fmpz_get_ui(const fmpz_t f);
194 
195 FMPZ_INLINE void
fmpz_get_uiui(mp_limb_t * hi,mp_limb_t * low,const fmpz_t f)196 fmpz_get_uiui(mp_limb_t * hi, mp_limb_t * low, const fmpz_t f)
197 {
198     if (!COEFF_IS_MPZ(*f))
199     {
200         *low = *f;
201         *hi  = 0;
202     }
203     else
204     {
205         __mpz_struct * mpz = COEFF_TO_PTR(*f);
206         *low = mpz->_mp_d[0];
207         *hi  = mpz->_mp_size == 2 ? mpz->_mp_d[1] : 0;
208     }
209 }
210 
211 FMPZ_INLINE void
fmpz_set_si(fmpz_t f,slong val)212 fmpz_set_si(fmpz_t f, slong val)
213 {
214     if (val < COEFF_MIN || val > COEFF_MAX) /* val is large */
215     {
216         __mpz_struct *mpz_coeff = _fmpz_promote(f);
217         flint_mpz_set_si(mpz_coeff, val);
218     }
219     else
220     {
221         _fmpz_demote(f);
222         *f = val;               /* val is small */
223     }
224 }
225 
226 FMPZ_INLINE void
fmpz_set_ui(fmpz_t f,ulong val)227 fmpz_set_ui(fmpz_t f, ulong val)
228 {
229     if (val > COEFF_MAX)        /* val is large */
230     {
231         __mpz_struct *mpz_coeff = _fmpz_promote(f);
232         flint_mpz_set_ui(mpz_coeff, val);
233     }
234     else
235     {
236         _fmpz_demote(f);
237         *f = val;               /* val is small */
238     }
239 }
240 
241 FMPZ_INLINE void
fmpz_neg_ui(fmpz_t f,ulong val)242 fmpz_neg_ui(fmpz_t f, ulong val)
243 {
244     if (val > COEFF_MAX)
245     {
246         __mpz_struct *mpz_coeff = _fmpz_promote(f);
247         flint_mpz_set_ui(mpz_coeff, val);
248         mpz_neg(mpz_coeff, mpz_coeff);
249     }
250     else
251     {
252         _fmpz_demote(f);
253         *f = -(slong) val;
254     }
255 }
256 
257 FMPZ_INLINE void
fmpz_set_uiui(fmpz_t f,mp_limb_t hi,mp_limb_t lo)258 fmpz_set_uiui(fmpz_t f, mp_limb_t hi, mp_limb_t lo)
259 {
260     if (hi == 0)
261     {
262         fmpz_set_ui(f, lo);
263     }
264     else
265     {
266         __mpz_struct *z = _fmpz_promote(f);
267         if (z->_mp_alloc < 2)
268             mpz_realloc2(z, 2 * FLINT_BITS);
269         z->_mp_d[0] = lo;
270         z->_mp_d[1] = hi;
271         z->_mp_size = 2;
272     }
273 }
274 
275 FMPZ_INLINE void
fmpz_neg_uiui(fmpz_t f,mp_limb_t hi,mp_limb_t lo)276 fmpz_neg_uiui(fmpz_t f, mp_limb_t hi, mp_limb_t lo)
277 {
278     if (hi == 0)
279     {
280         fmpz_neg_ui(f, lo);
281     }
282     else
283     {
284         __mpz_struct *z = _fmpz_promote(f);
285         if (z->_mp_alloc < 2)
286             mpz_realloc2(z, 2 * FLINT_BITS);
287         z->_mp_d[0] = lo;
288         z->_mp_d[1] = hi;
289         z->_mp_size = -2;
290     }
291 }
292 
293 FLINT_DLL void fmpz_set_signed_uiui(fmpz_t r, ulong hi, ulong lo);
294 
295 FLINT_DLL void fmpz_set_signed_uiuiui(fmpz_t r, ulong hi, ulong mid, ulong lo);
296 
297 FLINT_DLL void fmpz_set_ui_array(fmpz_t out, const ulong * in, slong in_len);
298 
299 FLINT_DLL void fmpz_get_ui_array(ulong * out, slong out_len, const fmpz_t in);
300 
301 FLINT_DLL void fmpz_get_mpz(mpz_t x, const fmpz_t f);
302 
303 FLINT_DLL void fmpz_set_mpz(fmpz_t f, const mpz_t x);
304 
305 FLINT_DLL double fmpz_get_d(const fmpz_t f);
306 
307 FLINT_DLL void fmpz_set_d(fmpz_t f, double c);
308 
309 FLINT_DLL void fmpz_get_mpf(mpf_t x, const fmpz_t f);
310 
311 FLINT_DLL void fmpz_set_mpf(fmpz_t f, const mpf_t x);
312 
313 FLINT_DLL void fmpz_get_mpfr(mpfr_t x, const fmpz_t f, mpfr_rnd_t rnd);
314 
315 FLINT_DLL int fmpz_get_mpn(mp_ptr *n, fmpz_t n_in);
316 
317 FLINT_DLL int fmpz_set_str(fmpz_t f, const char * str, int b);
318 
319 FLINT_DLL void flint_mpz_init_set_readonly(mpz_t z, const fmpz_t f);
320 
321 FLINT_DLL void flint_mpz_clear_readonly(mpz_t z);
322 
323 FLINT_DLL void fmpz_init_set_readonly(fmpz_t f, const mpz_t z);
324 
325 FLINT_DLL void fmpz_clear_readonly(fmpz_t f);
326 
327 FLINT_DLL int fmpz_abs_fits_ui(const fmpz_t f);
328 
329 FLINT_DLL int fmpz_fits_si(const fmpz_t f);
330 
331 FMPZ_INLINE
fmpz_zero(fmpz_t f)332 void fmpz_zero(fmpz_t f)
333 {
334    if (COEFF_IS_MPZ(*f))
335       _fmpz_clear_mpz(*f);
336    *f = WORD(0);
337 }
338 
339 FMPZ_INLINE
fmpz_one(fmpz_t f)340 void fmpz_one(fmpz_t f)
341 {
342     if (COEFF_IS_MPZ(*f))
343     {
344         _fmpz_clear_mpz(*f);
345 	}
346     *f = WORD(1);
347 }
348 
349 FMPZ_INLINE
fmpz_is_zero(const fmpz_t f)350 int fmpz_is_zero(const fmpz_t f)
351 {
352    return (*f == 0);
353 }
354 
355 FMPZ_INLINE
fmpz_is_one(const fmpz_t f)356 int fmpz_is_one(const fmpz_t f)
357 {
358    return (*f == 1);
359 }
360 
361 FMPZ_INLINE
fmpz_is_pm1(const fmpz_t f)362 int fmpz_is_pm1(const fmpz_t f)
363 {
364    return (*f == 1 || *f == -1);
365 }
366 
367 FLINT_DLL void fmpz_set(fmpz_t f, const fmpz_t g);
368 
369 FLINT_DLL int fmpz_equal(const fmpz_t f, const fmpz_t g);
370 
371 FLINT_DLL int fmpz_equal_si(const fmpz_t f, slong g);
372 
373 FLINT_DLL int fmpz_equal_ui(const fmpz_t f, ulong g);
374 
375 FLINT_DLL int fmpz_read(fmpz_t f);
376 
377 FLINT_DLL int fmpz_fread(FILE * file, fmpz_t f);
378 
379 FLINT_DLL size_t fmpz_inp_raw( fmpz_t x, FILE *fin );
380 
381 FLINT_DLL int fmpz_print(const fmpz_t x);
382 
383 FLINT_DLL int fmpz_fprint(FILE * file, const fmpz_t x);
384 
385 FLINT_DLL size_t fmpz_out_raw( FILE *fout, const fmpz_t x );
386 
387 FLINT_DLL size_t fmpz_sizeinbase(const fmpz_t f, int b);
388 
389 FLINT_DLL char * fmpz_get_str(char * str, int b, const fmpz_t f);
390 
391 FMPZ_INLINE
fmpz_swap(fmpz_t f,fmpz_t g)392 void fmpz_swap(fmpz_t f, fmpz_t g)
393 {
394     if (f != g)  /* swapping required */
395     {
396         fmpz t = *f;
397         *f = *g;
398         *g = t;
399     }
400 }
401 
402 FLINT_DLL int fmpz_cmp(const fmpz_t f, const fmpz_t g);
403 
404 FLINT_DLL int fmpz_cmp_ui(const fmpz_t f, ulong g);
405 
406 FLINT_DLL int fmpz_cmp_si(const fmpz_t f, slong g);
407 
408 FLINT_DLL int fmpz_cmpabs(const fmpz_t f, const fmpz_t g);
409 
410 FMPZ_INLINE
fmpz_is_even(const fmpz_t f)411 int fmpz_is_even(const fmpz_t f)
412 {
413     if (!COEFF_IS_MPZ(*f))
414     {
415         return !((*f) & WORD(1));
416     }
417     else
418     {
419         return mpz_even_p(COEFF_TO_PTR(*f));
420     }
421 }
422 
423 FMPZ_INLINE
fmpz_is_odd(const fmpz_t f)424 int fmpz_is_odd(const fmpz_t f)
425 {
426     if (!COEFF_IS_MPZ(*f))
427     {
428         return ((*f) & WORD(1));
429     }
430     else
431     {
432         return mpz_odd_p(COEFF_TO_PTR(*f));
433     }
434 }
435 
436 FLINT_DLL mp_size_t fmpz_size(const fmpz_t f);
437 
438 FLINT_DLL int fmpz_sgn(const fmpz_t f);
439 
440 FLINT_DLL flint_bitcnt_t fmpz_bits(const fmpz_t f);
441 
442 FLINT_DLL flint_bitcnt_t fmpz_val2(const fmpz_t x);
443 
444 FMPZ_INLINE void
fmpz_neg(fmpz_t f1,const fmpz_t f2)445 fmpz_neg(fmpz_t f1, const fmpz_t f2)
446 {
447     if (!COEFF_IS_MPZ(*f2))     /* coeff is small */
448     {
449         fmpz t = -*f2;          /* Need to save value in case of aliasing */
450         _fmpz_demote(f1);
451         *f1 = t;
452     }
453     else                        /* coeff is large */
454     {
455         /* No need to retain value in promotion, as if aliased, both already large */
456         __mpz_struct *mpz_res = _fmpz_promote(f1);
457         mpz_neg(mpz_res, COEFF_TO_PTR(*f2));
458     }
459 }
460 
461 FLINT_DLL void fmpz_abs(fmpz_t f1, const fmpz_t f2);
462 
463 FLINT_DLL void fmpz_add(fmpz_t f, const fmpz_t g, const fmpz_t h);
464 
465 FLINT_DLL void fmpz_sub(fmpz_t f, const fmpz_t g, const fmpz_t h);
466 
467 FLINT_DLL void fmpz_mul_ui(fmpz_t f, const fmpz_t g, ulong x);
468 
469 FLINT_DLL void fmpz_mul_si(fmpz_t f, const fmpz_t g, slong x);
470 
471 FLINT_DLL void fmpz_mul(fmpz_t f, const fmpz_t g, const fmpz_t h);
472 
473 FLINT_DLL void fmpz_mul_2exp(fmpz_t f, const fmpz_t g, ulong exp);
474 
475 FLINT_DLL void fmpz_add_ui(fmpz_t f, const fmpz_t g, ulong x);
476 
477 FLINT_DLL void fmpz_sub_ui(fmpz_t f, const fmpz_t g, ulong x);
478 
fmpz_add_si(fmpz_t f,const fmpz_t g,slong x)479 FMPZ_INLINE void fmpz_add_si(fmpz_t f, const fmpz_t g, slong x)
480 {
481     if (x >= 0)
482         fmpz_add_ui(f, g, (ulong) x);
483     else
484         fmpz_sub_ui(f, g, (ulong) -x);
485 }
486 
fmpz_sub_si(fmpz_t f,const fmpz_t g,slong x)487 FMPZ_INLINE void fmpz_sub_si(fmpz_t f, const fmpz_t g, slong x)
488 {
489     if (x >= 0)
490         fmpz_sub_ui(f, g, (ulong) x);
491     else
492         fmpz_add_ui(f, g, (ulong) -x);
493 }
494 
495 FLINT_DLL void fmpz_addmul_ui(fmpz_t f, const fmpz_t g, ulong x);
496 
497 FLINT_DLL void fmpz_submul_ui(fmpz_t f, const fmpz_t g, ulong x);
498 
499 FLINT_DLL void fmpz_addmul(fmpz_t f, const fmpz_t g, const fmpz_t h);
500 
501 FLINT_DLL void fmpz_submul(fmpz_t f, const fmpz_t g, const fmpz_t h);
502 
503 FLINT_DLL void fmpz_fmma(fmpz_t f, const fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_t d);
504 
505 FLINT_DLL void fmpz_fmms(fmpz_t f, const fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_t d);
506 
507 FLINT_DLL void fmpz_pow_ui(fmpz_t f, const fmpz_t g, ulong exp);
508 
509 FLINT_DLL int fmpz_pow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t e);
510 
511 FLINT_DLL void fmpz_powm_ui(fmpz_t f, const fmpz_t g, ulong exp, const fmpz_t m);
512 
513 FLINT_DLL void fmpz_powm(fmpz_t f, const fmpz_t g, const fmpz_t e, const fmpz_t m);
514 
515 FLINT_DLL void fmpz_setbit(fmpz_t f, ulong i);
516 
517 FLINT_DLL int fmpz_tstbit(const fmpz_t f, ulong i);
518 
519 FLINT_DLL void fmpz_clrbit(fmpz_t f, ulong i);
520 
521 FLINT_DLL void fmpz_complement(fmpz_t r, const fmpz_t f);
522 
523 FLINT_DLL void fmpz_combit(fmpz_t f, ulong i);
524 
525 FLINT_DLL void fmpz_and(fmpz_t r, const fmpz_t a, const fmpz_t b);
526 
527 FLINT_DLL void fmpz_or(fmpz_t r, const fmpz_t a, const fmpz_t b);
528 
529 FLINT_DLL void fmpz_xor(fmpz_t r, const fmpz_t a, const fmpz_t b);
530 
531 FLINT_DLL flint_bitcnt_t fmpz_popcnt(const fmpz_t c);
532 
533 FLINT_DLL double fmpz_dlog(const fmpz_t x);
534 FLINT_DLL slong fmpz_flog(const fmpz_t x, const fmpz_t b);
535 FLINT_DLL slong fmpz_flog_ui(const fmpz_t x, ulong b);
536 FLINT_DLL slong fmpz_clog(const fmpz_t x, const fmpz_t b);
537 FLINT_DLL slong fmpz_clog_ui(const fmpz_t x, ulong b);
538 
539 FLINT_DLL int fmpz_sqrtmod(fmpz_t b, const fmpz_t a, const fmpz_t p);
540 
541 FLINT_DLL void fmpz_sqrt(fmpz_t f, const fmpz_t g);
542 
543 FLINT_DLL int fmpz_is_square(const fmpz_t f);
544 
545 FLINT_DLL void fmpz_root(fmpz_t r, const fmpz_t f, slong n);
546 
547 FLINT_DLL int fmpz_is_perfect_power(fmpz_t root, const fmpz_t f);
548 
549 FLINT_DLL void fmpz_sqrtrem(fmpz_t f, fmpz_t r, const fmpz_t g);
550 
551 FLINT_DLL ulong fmpz_fdiv_ui(const fmpz_t g, ulong h);
552 
553 FLINT_DLL ulong fmpz_mod_ui(fmpz_t f, const fmpz_t g, ulong h);
554 
555 FLINT_DLL void fmpz_mod(fmpz_t f, const fmpz_t g, const fmpz_t h);
556 
557 FLINT_DLL void fmpz_smod(fmpz_t f, const fmpz_t g, const fmpz_t h);
558 
559 FMPZ_INLINE void
fmpz_negmod(fmpz_t r,const fmpz_t a,const fmpz_t mod)560 fmpz_negmod(fmpz_t r, const fmpz_t a, const fmpz_t mod)
561 {
562    if (fmpz_is_zero(a))
563       fmpz_zero(r);
564    else
565       fmpz_sub(r, mod, a);
566 }
567 
568 FLINT_DLL void fmpz_gcd(fmpz_t f, const fmpz_t g, const fmpz_t h);
569 
570 FLINT_DLL void fmpz_lcm(fmpz_t f, const fmpz_t g, const fmpz_t h);
571 
572 FLINT_DLL void fmpz_gcdinv(fmpz_t d, fmpz_t a, const fmpz_t f, const fmpz_t g);
573 
574 FLINT_DLL void fmpz_xgcd(fmpz_t d, fmpz_t a, fmpz_t b, const fmpz_t f, const fmpz_t g);
575 
576 FLINT_DLL void fmpz_xgcd_partial(fmpz_t co2, fmpz_t co1,
577                                        fmpz_t r2, fmpz_t r1, const fmpz_t L);
578 
579 FLINT_DLL int fmpz_invmod(fmpz_t f, const fmpz_t g, const fmpz_t h);
580 
581 FLINT_DLL int fmpz_jacobi(const fmpz_t a, const fmpz_t p);
582 
583 FLINT_DLL void fmpz_divides_mod_list(fmpz_t xstart, fmpz_t xstride,
584                fmpz_t xlength, const fmpz_t a, const fmpz_t b, const fmpz_t n);
585 
586 FLINT_DLL slong _fmpz_remove(fmpz_t x, const fmpz_t f, double finv);
587 
588 FLINT_DLL slong fmpz_remove(fmpz_t rop, const fmpz_t op, const fmpz_t f);
589 
590 FLINT_DLL void fmpz_divexact(fmpz_t f, const fmpz_t g, const fmpz_t h);
591 
592 FLINT_DLL void fmpz_divexact_si(fmpz_t f, const fmpz_t g, slong h);
593 
594 FLINT_DLL void fmpz_divexact_ui(fmpz_t f, const fmpz_t g, ulong h);
595 
596 FLINT_DLL int fmpz_divisible(const fmpz_t f, const fmpz_t g);
597 
598 FLINT_DLL int fmpz_divisible_si(const fmpz_t f, slong g);
599 
600 FLINT_DLL void fmpz_cdiv_qr(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h);
601 
602 FLINT_DLL void fmpz_cdiv_q(fmpz_t f, const fmpz_t g, const fmpz_t h);
603 
604 FLINT_DLL void fmpz_cdiv_q_si(fmpz_t f, const fmpz_t g, slong h);
605 
606 FLINT_DLL void fmpz_cdiv_q_ui(fmpz_t f, const fmpz_t g, ulong h);
607 
608 FLINT_DLL void fmpz_cdiv_q_2exp(fmpz_t f, const fmpz_t g, ulong exp);
609 
610 FLINT_DLL void fmpz_cdiv_r_2exp(fmpz_t f, const fmpz_t g, ulong exp);
611 
612 FLINT_DLL ulong fmpz_cdiv_ui(const fmpz_t g, ulong h);
613 
614 FLINT_DLL void fmpz_fdiv_qr(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h);
615 
616 FLINT_DLL void fmpz_fdiv_qr_preinvn(fmpz_t f, fmpz_t s, const fmpz_t g,
617                                      const fmpz_t h, const fmpz_preinvn_t inv);
618 
619 FLINT_DLL void fmpz_fdiv_q(fmpz_t f, const fmpz_t g, const fmpz_t h);
620 
621 FLINT_DLL void fmpz_fdiv_r(fmpz_t f, const fmpz_t g, const fmpz_t h);
622 
623 FLINT_DLL void fmpz_fdiv_q_ui(fmpz_t f, const fmpz_t g, ulong h);
624 
625 FLINT_DLL void fmpz_fdiv_q_si(fmpz_t f, const fmpz_t g, slong h);
626 
627 FLINT_DLL void fmpz_fdiv_q_2exp(fmpz_t f, const fmpz_t g, ulong exp);
628 
629 FLINT_DLL void fmpz_fdiv_r_2exp(fmpz_t f, const fmpz_t g, ulong exp);
630 
631 FLINT_DLL void fmpz_tdiv_q(fmpz_t f, const fmpz_t g, const fmpz_t h);
632 
633 FLINT_DLL void fmpz_tdiv_qr(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h);
634 
635 FLINT_DLL void fmpz_tdiv_q_ui(fmpz_t f, const fmpz_t g, ulong h);
636 
637 FLINT_DLL void fmpz_tdiv_q_si(fmpz_t f, const fmpz_t g, slong h);
638 
639 FLINT_DLL void fmpz_tdiv_r_2exp(fmpz_t f, const fmpz_t g, ulong exp);
640 
641 FLINT_DLL ulong fmpz_tdiv_ui(const fmpz_t g, ulong h);
642 
643 FLINT_DLL void fmpz_tdiv_q_2exp(fmpz_t f, const fmpz_t g, ulong exp);
644 
645 FLINT_DLL void fmpz_preinvn_init(fmpz_preinvn_t inv, const fmpz_t f);
646 
647 FLINT_DLL void fmpz_preinvn_clear(fmpz_preinvn_t inv);
648 
649 FLINT_DLL double fmpz_get_d_2exp(slong * exp, const fmpz_t f);
650 
651 FLINT_DLL void fmpz_set_d_2exp(fmpz_t f, double m, slong exp);
652 
653 FMPZ_INLINE void
fmpz_mul2_uiui(fmpz_t f,const fmpz_t g,ulong h1,ulong h2)654 fmpz_mul2_uiui(fmpz_t f, const fmpz_t g, ulong h1, ulong h2)
655 {
656     mp_limb_t hi, lo;
657 
658     umul_ppmm(hi, lo, h1, h2);
659     if (!hi)
660     {
661         fmpz_mul_ui(f, g, lo);
662     }
663     else
664     {
665         fmpz_mul_ui(f, g, h1);
666         fmpz_mul_ui(f, f, h2);
667     }
668 }
669 
670 FMPZ_INLINE void
fmpz_divexact2_uiui(fmpz_t f,const fmpz_t g,ulong h1,ulong h2)671 fmpz_divexact2_uiui(fmpz_t f, const fmpz_t g, ulong h1, ulong h2)
672 {
673     mp_limb_t hi, lo;
674 
675     umul_ppmm(hi, lo, h1, h2);
676     if (!hi)
677     {
678         fmpz_divexact_ui(f, g, lo);
679     }
680     else
681     {
682         fmpz_divexact_ui(f, g, h1);
683         fmpz_divexact_ui(f, f, h2);
684     }
685 }
686 
687 FLINT_DLL void fmpz_mul_tdiv_q_2exp(fmpz_t f, const fmpz_t g, const fmpz_t h, ulong exp);
688 
689 FLINT_DLL void fmpz_mul_si_tdiv_q_2exp(fmpz_t f, const fmpz_t g, slong x, ulong exp);
690 
691 FLINT_DLL void fmpz_fac_ui(fmpz_t f, ulong n);
692 
693 FLINT_DLL void fmpz_fib_ui(fmpz_t f, ulong n);
694 
695 FLINT_DLL void fmpz_bin_uiui(fmpz_t res, ulong n, ulong k);
696 
697 FLINT_DLL void _fmpz_rfac_ui(fmpz_t r, const fmpz_t x, ulong a, ulong b);
698 
699 FLINT_DLL void fmpz_rfac_ui(fmpz_t r, const fmpz_t x, ulong n);
700 
701 FLINT_DLL void fmpz_rfac_uiui(fmpz_t r, ulong x, ulong n);
702 
703 FLINT_DLL int fmpz_bit_pack(mp_ptr arr, flint_bitcnt_t shift, flint_bitcnt_t bits,
704                   const fmpz_t coeff, int negate, int borrow);
705 
706 FLINT_DLL int fmpz_bit_unpack(fmpz_t coeff, mp_srcptr arr, flint_bitcnt_t shift,
707                     flint_bitcnt_t bits, int negate, int borrow);
708 
709 FLINT_DLL void fmpz_bit_unpack_unsigned(fmpz_t coeff, mp_srcptr arr,
710                               flint_bitcnt_t shift, flint_bitcnt_t bits);
711 
712 /* crt ***********************************************************************/
713 
714 FLINT_DLL void _fmpz_CRT_ui_precomp(fmpz_t out, const fmpz_t r1, const fmpz_t m1,
715     ulong r2, ulong m2, mp_limb_t m2inv, const fmpz_t m1m2, mp_limb_t c,
716         int sign);
717 
718 FLINT_DLL void fmpz_CRT_ui(fmpz_t out, const fmpz_t r1, const fmpz_t m1,
719     ulong r2, ulong m2, int sign);
720 
721 #define FLINT_FMPZ_LOG_MULTI_MOD_CUTOFF 2
722 
723 typedef struct
724 {
725     const mp_limb_t * primes;
726     slong num_primes;
727     slong n;         /* we have 2^n >= num_primes > 2^(n-1) */
728     fmpz ** comb;   /* Array of arrays of products */
729     fmpz ** res;    /* successive residues r_i^-1 mod r_{i+1} for pairs r_i, r_{i+1} */
730     nmod_t * mod;
731 }
732 fmpz_comb_struct;
733 
734 typedef struct
735 {
736     slong n;
737     fmpz ** comb_temp;
738     fmpz_t temp;
739     fmpz_t temp2;
740 }
741 fmpz_comb_temp_struct;
742 
743 typedef fmpz_comb_struct fmpz_comb_t[1];
744 typedef fmpz_comb_temp_struct fmpz_comb_temp_t[1];
745 
746 FLINT_DLL void fmpz_comb_temp_init(fmpz_comb_temp_t temp, const fmpz_comb_t comb);
747 FLINT_DLL void fmpz_comb_temp_clear(fmpz_comb_temp_t temp);
748 
749 FLINT_DLL void fmpz_comb_init(fmpz_comb_t comb, mp_srcptr primes, slong num_primes);
750 FLINT_DLL void fmpz_comb_clear(fmpz_comb_t comb);
751 
752 FLINT_DLL void fmpz_multi_mod_ui(mp_limb_t * out, const fmpz_t in,
753     const fmpz_comb_t comb, fmpz_comb_temp_t temp);
754 
755 FLINT_DLL void fmpz_multi_CRT_ui(fmpz_t output, mp_srcptr residues,
756     const fmpz_comb_t comb, fmpz_comb_temp_t temp, int sign);
757 
758 FLINT_DLL void fmpz_CRT(fmpz_t out, const fmpz_t r1, const fmpz_t m1,
759                                                 fmpz_t r2, fmpz_t m2, int sign);
760 
fmpz_set_ui_smod(fmpz_t f,mp_limb_t x,mp_limb_t m)761 FMPZ_INLINE void fmpz_set_ui_smod(fmpz_t f, mp_limb_t x, mp_limb_t m)
762 {
763     if (x <= m / 2)
764         fmpz_set_ui(f, x);
765     else
766         fmpz_set_si(f, x - m);
767 }
768 
769 /* instructions do A = B + I*(C - B) mod M */
770 typedef struct
771 {
772     slong a_idx; /* index of A */
773     slong b_idx; /* index of B */
774     slong c_idx; /* index of C */
775     fmpz_t idem;     /* I */
776     fmpz_t modulus;  /* M */
777 } _fmpz_multi_crt_prog_instr;
778 
779 typedef struct
780 {
781     _fmpz_multi_crt_prog_instr * prog; /* straight line program */
782     slong length; /* length of prog */
783     slong alloc;  /* alloc of prog */
784     slong localsize; /* length of outputs required in nmod_poly_crt_run */
785     slong temp1loc; /* index of temporary used in run */
786     slong temp2loc; /* index of another tempory used in run */
787     int good;   /* the moduli are good for CRT, essentially relatively prime */
788 } fmpz_multi_crt_struct;
789 
790 typedef fmpz_multi_crt_struct fmpz_multi_crt_t[1];
791 
792 FLINT_DLL void fmpz_multi_crt_init(fmpz_multi_crt_t CRT);
793 
794 FLINT_DLL int fmpz_multi_crt_precompute(fmpz_multi_crt_t CRT,
795                                                const fmpz * moduli, slong len);
796 
797 FLINT_DLL int fmpz_multi_crt_precompute_p(fmpz_multi_crt_t CRT,
798                                        const fmpz * const * moduli, slong len);
799 
800 FLINT_DLL void fmpz_multi_crt_precomp(fmpz_t output, const fmpz_multi_crt_t P,
801                                                           const fmpz * inputs);
802 
803 FLINT_DLL void fmpz_multi_crt_precomp_p(fmpz_t output,
804                         const fmpz_multi_crt_t P, const fmpz * const * inputs);
805 
806 FLINT_DLL int fmpz_multi_crt(fmpz_t output, const fmpz * moduli,
807                                                const fmpz * values, slong len);
808 
809 FLINT_DLL void fmpz_multi_crt_clear(fmpz_multi_crt_t P);
810 
_fmpz_multi_crt_local_size(const fmpz_multi_crt_t CRT)811 FMPZ_INLINE slong _fmpz_multi_crt_local_size(const fmpz_multi_crt_t CRT)
812 {
813     return CRT->localsize;
814 }
815 
816 FLINT_DLL void _fmpz_multi_crt_run(fmpz * outputs, const fmpz_multi_crt_t CRT,
817                                                           const fmpz * inputs);
818 
819 FLINT_DLL void _fmpz_multi_crt_run_p(fmpz * outputs,
820                       const fmpz_multi_crt_t CRT, const fmpz * const * inputs);
821 
822 /*****************************************************************************/
823 
824 FLINT_DLL mp_limb_t fmpz_abs_ubound_ui_2exp(slong * exp, const fmpz_t x, int bits);
825 
826 FLINT_DLL mp_limb_t fmpz_abs_lbound_ui_2exp(slong * exp, const fmpz_t x, int bits);
827 
828 FLINT_DLL void fmpz_lucas_chain(fmpz_t Vm, fmpz_t Vm1, const fmpz_t A,
829                                                const fmpz_t m, const fmpz_t n);
830 
831 FLINT_DLL void fmpz_lucas_chain_full(fmpz_t Vm, fmpz_t Vm1, const fmpz_t A, const fmpz_t B,
832                                          const fmpz_t m, const fmpz_t n);
833 
834 FLINT_DLL void fmpz_lucas_chain_double(fmpz_t U2m, fmpz_t U2m1, const fmpz_t Um,
835                              const fmpz_t Um1, const fmpz_t A,
836                              const fmpz_t B, const fmpz_t n);
837 
838 FLINT_DLL void fmpz_lucas_chain_add(fmpz_t Umn, fmpz_t Umn1, const fmpz_t Um,
839                              const fmpz_t Um1, const fmpz_t Un,
840                              const fmpz_t Un1, const fmpz_t A,
841                              const fmpz_t B, const fmpz_t n);
842 
843 FLINT_DLL void fmpz_lucas_chain_mul(fmpz_t Ukm, fmpz_t Ukm1,
844                                const fmpz_t Um, const fmpz_t Um1,
845                                const fmpz_t A, const fmpz_t B, const fmpz_t k,
846                                const fmpz_t n);
847 
848 FLINT_DLL void fmpz_lucas_chain_VtoU(fmpz_t Um, fmpz_t Um1,
849                             const fmpz_t Vm, const fmpz_t Vm1,
850                             const fmpz_t A, const fmpz_t B, const fmpz_t Dinv,
851                             const fmpz_t n);
852 
853 FLINT_DLL int fmpz_is_probabprime_lucas(const fmpz_t n);
854 
855 FLINT_DLL int fmpz_is_probabprime_BPSW(const fmpz_t n);
856 
857 FLINT_DLL int fmpz_is_strong_probabprime(const fmpz_t n, const fmpz_t a);
858 
859 FLINT_DLL int fmpz_is_probabprime(const fmpz_t p);
860 
861 FLINT_DLL int fmpz_is_prime_pseudosquare(const fmpz_t n);
862 
863 FLINT_DLL void _fmpz_nm1_trial_factors(const fmpz_t n, mp_ptr pm1,
864                                                  slong * num_pm1, ulong limit);
865 
866 FLINT_DLL int fmpz_is_prime_pocklington(fmpz_t F, fmpz_t R,
867                                     const fmpz_t n, mp_ptr pm1, slong num_pm1);
868 
869 FLINT_DLL void _fmpz_np1_trial_factors(const fmpz_t n,
870                                      mp_ptr pp1, slong * num_pp1, ulong limit);
871 
872 FLINT_DLL int fmpz_is_prime_morrison(fmpz_t F, fmpz_t R,
873                                     const fmpz_t n, mp_ptr pm1, slong num_pm1);
874 
875 FLINT_DLL int fmpz_is_prime(const fmpz_t p);
876 
877 FLINT_DLL int fmpz_divisor_in_residue_class_lenstra(fmpz_t fac, const fmpz_t n,
878                                                const fmpz_t r, const fmpz_t s);
879 
880 FLINT_DLL void fmpz_nextprime(fmpz_t res, const fmpz_t n, int proved);
881 
882 /* Primorials */
883 
884 FLINT_DLL void fmpz_primorial(fmpz_t res, ulong n);
885 
886 /* Multiplicative functions */
887 
888 FLINT_DLL void fmpz_euler_phi(fmpz_t res, const fmpz_t n);
889 
890 FLINT_DLL int fmpz_moebius_mu(const fmpz_t n);
891 
892 FLINT_DLL void fmpz_divisor_sigma(fmpz_t res, const fmpz_t n, ulong k);
893 
894 /* Functions that should be in ulong extras */
895 
896 FLINT_DLL ulong n_powmod2_fmpz_preinv(ulong a, const fmpz_t exp,
897                                                           ulong n, ulong ninv);
898 
nmod_pow_fmpz(mp_limb_t a,const fmpz_t exp,nmod_t mod)899 FMPZ_INLINE mp_limb_t nmod_pow_fmpz(mp_limb_t a, const fmpz_t exp, nmod_t mod)
900 {
901     return n_powmod2_fmpz_preinv(a, exp, mod.n, mod.ninv);
902 }
903 
904 /* Inlines *******************************************************************/
905 
906 FLINT_DLL fmpz * __new_fmpz();
907 FLINT_DLL void __free_fmpz(fmpz * f);
908 FLINT_DLL void __fmpz_set_si(fmpz_t f, slong val);
909 FLINT_DLL void __fmpz_set_ui(fmpz_t f, ulong val);
910 FLINT_DLL void __fmpz_init(fmpz_t f);
911 FLINT_DLL void __fmpz_init_set_ui(fmpz_t f, ulong g);
912 FLINT_DLL void __fmpz_clear(fmpz_t f);
913 FLINT_DLL int __fmpz_lt(fmpz_t f, fmpz_t g);
914 FLINT_DLL int __fmpz_gt(fmpz_t f, fmpz_t g);
915 FLINT_DLL int __fmpz_lte(fmpz_t f, fmpz_t g);
916 FLINT_DLL int __fmpz_gte(fmpz_t f, fmpz_t g);
917 FLINT_DLL int __fmpz_eq(fmpz_t f, fmpz_t g);
918 FLINT_DLL int __fmpz_neq(fmpz_t f, fmpz_t g);
919 FLINT_DLL void __fmpz_init_set(fmpz_t f, const fmpz_t g);
920 FLINT_DLL void __fmpz_neg(fmpz_t f1, const fmpz_t f2);
921 
922 #ifdef __cplusplus
923 }
924 #endif
925 
926 #include "fmpz_factor.h"
927 
928 #endif
929 
930