1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
.. _fq-poly_factor:
**fq_default_poly_factor.h** -- factorisation of univariate polynomials over finite fields
==========================================================================================
Types, macros and constants
-------------------------------------------------------------------------------
.. type:: fq_default_poly_factor_t
Memory Management
--------------------------------------------------------------------------------
.. function:: void fq_default_poly_factor_init(fq_default_poly_factor_t fac, const fq_default_ctx_t ctx)
Initialises ``fac`` for use. An :type:`fq_default_poly_factor_t`
represents a polynomial in factorised form as a product of
polynomials with associated exponents.
.. function:: void fq_default_poly_factor_clear(fq_default_poly_factor_t fac, const fq_default_ctx_t ctx)
Frees all memory associated with ``fac``.
.. function:: void fq_default_poly_factor_realloc(fq_default_poly_factor_t fac, slong alloc, const fq_default_ctx_t ctx)
Reallocates the factor structure to provide space for
precisely ``alloc`` factors.
.. function:: void fq_default_poly_factor_fit_length(fq_default_poly_factor_t fac, slong len, const fq_default_ctx_t ctx)
Ensures that the factor structure has space for at least
``len`` factors. This function takes care of the case of
repeated calls by always at least doubling the number of factors
the structure can hold.
Basic Operations
--------------------------------------------------------------------------------
.. function:: void fq_default_poly_factor_set(fq_default_poly_factor_t res, const fq_default_poly_factor_t fac, const fq_default_ctx_t ctx)
Sets ``res`` to the same factorisation as ``fac``.
.. function:: void fq_default_poly_factor_print_pretty(const fq_default_poly_factor_t fac, const char * var, const fq_default_ctx_t ctx)
Pretty-prints the entries of ``fac`` to standard output.
.. function:: void fq_default_poly_factor_print(const fq_default_poly_factor_t fac, const fq_default_ctx_t ctx)
Prints the entries of ``fac`` to standard output.
.. function:: void fq_default_poly_factor_insert(fq_default_poly_factor_t fac, const fq_default_poly_t poly, slong exp, const fq_default_ctx_t ctx)
Inserts the factor ``poly`` with multiplicity ``exp`` into
the factorisation ``fac``.
If ``fac`` already contains ``poly``, then ``exp`` simply
gets added to the exponent of the existing entry.
.. function:: void fq_default_poly_factor_concat(fq_default_poly_factor_t res, const fq_default_poly_factor_t fac, const fq_default_ctx_t ctx)
Concatenates two factorisations.
This is equivalent to calling :func:`fq_default_poly_factor_insert`
repeatedly with the individual factors of ``fac``.
Does not support aliasing between ``res`` and ``fac``.
.. function:: void fq_default_poly_factor_pow(fq_default_poly_factor_t fac, slong exp, const fq_default_ctx_t ctx)
Raises ``fac`` to the power ``exp``.
.. function:: ulong fq_default_poly_remove(fq_default_poly_t f, const fq_default_poly_t p, const fq_default_ctx_t ctx)
Removes the highest possible power of ``p`` from ``f`` and
returns the exponent.
.. function:: slong fq_default_poly_factor_length(fq_default_poly_factor_t fac, const fq_default_ctx_t ctx)
Return the number of factors, not including the unit.
.. function:: void fq_default_poly_factor_get_poly(fq_default_poly_t poly, const fq_default_poly_factor_t fac, slong i, const fq_default_ctx_t ctx)
Set ``poly`` to factor ``i`` of ``fac`` (numbering starts at zero).
.. function:: slong fq_default_poly_factor_exp(fq_default_poly_factor_t fac, slong i, const fq_default_ctx_t ctx)
Return the exponent of factor ``i`` of ``fac``.
Irreducibility Testing
--------------------------------------------------------------------------------
.. function:: int fq_default_poly_is_irreducible(const fq_default_poly_t f, const fq_default_ctx_t ctx)
Returns 1 if the polynomial ``f`` is irreducible, otherwise returns 0.
.. function:: int fq_default_poly_is_squarefree(const fq_default_poly_t f, const fq_default_ctx_t ctx)
Returns 1 if ``f`` is squarefree, and 0 otherwise. As a special
case, the zero polynomial is not considered squarefree.
Factorisation
--------------------------------------------------------------------------------
.. function:: void fq_default_poly_factor_equal_deg(fq_default_poly_factor_t factors, const fq_default_poly_t pol, slong d, const fq_default_ctx_t ctx)
Assuming ``pol`` is a product of irreducible factors all of
degree ``d``, finds all those factors and places them in
factors. Requires that ``pol`` be monic, non-constant and
squarefree.
.. function:: void fq_default_poly_factor_split_single(fq_default_poly_t linfactor, const fq_default_poly_t input, const fq_default_ctx_t ctx)
Assuming ``input`` is a product of factors all of degree 1, finds a single
linear factor of ``input`` and places it in ``linfactor``.
Requires that ``input`` be monic and non-constant.
.. function:: void fq_default_poly_factor_distinct_deg(fq_default_poly_factor_t res, const fq_default_poly_t poly, slong * const * degs, const fq_default_ctx_t ctx)
Factorises a monic non-constant squarefree polynomial ``poly``
of degree `n` into factors `f[d]` such that for `1 \leq d \leq n`
`f[d]` is the product of the monic irreducible factors of
``poly`` of degree `d`. Factors are stored in ``res``,
associated powers of irreducible polynomials are stored in
``degs`` in the same order as factors.
Requires that ``degs`` have enough space for irreducible polynomials'
powers (maximum space required is ``n * sizeof(slong)``).
.. function:: void fq_default_poly_factor_squarefree(fq_default_poly_factor_t res, const fq_default_poly_t f, const fq_default_ctx_t ctx)
Sets ``res`` to a squarefree factorization of ``f``.
.. function:: void fq_default_poly_factor(fq_default_poly_factor_t res, fq_default_t lead, const fq_default_poly_t f, const fq_default_ctx_t ctx)
Factorises a non-constant polynomial ``f`` into monic
irreducible factors choosing the best algorithm for given modulo
and degree. The output ``lead`` is set to the leading coefficient of `f`
upon return. Choice of algorithm is based on heuristic measurements.
Root Finding
--------------------------------------------------------------------------------
.. function:: void fq_default_poly_roots(fq_default_poly_factor_t r, const fq_default_poly_t f, int with_multiplicity, const fq_default_ctx_t ctx)
Fill `r` with factors of the form `x - r_i` where the `r_i` are the distinct roots of a nonzero `f` in `F_q`.
If `with\_multiplicity` is zero, the exponent `e_i` of the factor `x - r_i` is `1`. Otherwise, it is the largest `e_i` such that `(x-r_i)^e_i` divides `f`.
This function throws if `f` is zero, but is otherwise always successful.
|
