1 /*
2 Copyright (C) 2016 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 #include <gmp.h>
13 #include "flint.h"
14 #include "fmpz.h"
15 #include "fmpz_vec.h"
16 #include "mpn_extras.h"
17 #include "ulong_extras.h"
18 #include "qsieve.h"
19 #include "thread_support.h"
20
21 void
fmpz_factor_no_trial(fmpz_factor_t factor,const fmpz_t n)22 fmpz_factor_no_trial(fmpz_factor_t factor, const fmpz_t n)
23 {
24 int exp, i;
25
26 if (fmpz_is_prime(n))
27 _fmpz_factor_append(factor, n, 1);
28 else
29 {
30 fmpz_t root;
31
32 fmpz_init(root);
33
34 exp = fmpz_is_perfect_power(root, n);
35
36 if (exp != 0)
37 {
38 fmpz_factor_t fac;
39
40 fmpz_factor_init(fac);
41
42 fmpz_factor_no_trial(fac, root);
43
44 _fmpz_factor_concat(factor, fac, exp);
45
46 fmpz_factor_clear(fac);
47 } else
48 {
49 fmpz_factor_t fac, fac2, fac3;
50 slong bits = fmpz_sizeinbase(n, 2);
51 int done;
52
53 fmpz_factor_init(fac3);
54
55 done = fmpz_factor_smooth(fac3, n, FLINT_MAX(bits/3 - 17, 2), 1);
56
57 if (!done)
58 {
59 fmpz_t n2;
60 slong exp2;
61
62 fmpz_init(n2);
63
64 /* take out cofactor and factor it */
65 fmpz_set(n2, fac3->p + fac3->num - 1);
66 exp = fac3->exp[fac3->num - 1];
67 fac3->exp[fac3->num - 1] = 0;
68 fac3->num--;
69
70 fmpz_factor_init(fac);
71
72 /* qsieve can't factor perfect powers */
73 exp2 = fmpz_is_perfect_power(root, n2);
74
75 if (exp2)
76 _fmpz_factor_append(fac, root, exp2);
77 else
78 qsieve_factor(fac, n2);
79
80 for (i = 0; i < fac->num; i++)
81 {
82 fmpz_factor_init(fac2);
83
84 fmpz_factor_no_trial(fac2, fac->p + i);
85
86 _fmpz_factor_concat(fac3, fac2, exp*fac->exp[i]);
87
88 fmpz_factor_clear(fac2);
89 }
90
91 fmpz_factor_clear(fac);
92
93 fmpz_clear(n2);
94 }
95
96 _fmpz_factor_concat(factor, fac3, 1);
97
98 fmpz_factor_clear(fac3);
99 }
100
101 fmpz_clear(root);
102 }
103 }
104