-
Notifications
You must be signed in to change notification settings - Fork 63
/
Poly.jl
98 lines (86 loc) · 2.49 KB
/
Poly.jl
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
##############################################################################
#
# Basic manipulation
#
##############################################################################
function is_power(a::PolyRingElem, n::Int)
# not the best algorithm... but it works generically
# probably a equal-degree-factorisation would be good + some more gcd's
# implement some Newton-type algo?
degree(a) % n == 0 || return false, a
fl, x = is_power(leading_coefficient(a), n)
fl || return false, a
f = factor(a)
all(i -> i % n == 0, values(f.fac)) || return false, a
return true, x*prod(p^div(k, n) for (p, k) = f.fac)
end
################################################################################
#
# Factorisation
#
################################################################################
function factor(R::Field, f::PolyRingElem)
Rt = AbstractAlgebra.PolyRing(R)
f1 = change_base_ring(R, f; parent = Rt)
return factor(f1)
end
function factor(R::Ring, f::FracElem)
fn = factor(R(numerator(f)))
fd = factor(R(denominator(f)))
fn.unit = divexact(fn.unit, fd.unit)
for (k,v) = fd.fac
if Base.haskey(fn.fac, k)
fn.fac[k] -= v
else
fn.fac[k] = -v
end
end
return fn
end
################################################################################
#
# Roots
#
################################################################################
@doc raw"""
roots(f::PolyRingElem)
Returns the roots of the polynomial `f` in the base ring of `f` as an array.
"""
function roots(f::PolyRingElem)
lf = factor(f)
rts = Vector{elem_type(base_ring(f))}()
for (p, e) in lf
if degree(p) == 1
push!(rts, -divexact(constant_coefficient(p), leading_coefficient(p)))
end
end
return rts
end
@doc raw"""
roots(R::Field, f::PolyRingElem)
Returns the roots of the polynomial `f` in the field `R` as an array.
"""
function roots(R::Field, f::PolyRingElem)
Rt = AbstractAlgebra.PolyRing(R)
f1 = change_base_ring(R, f, parent = Rt)
return roots(f1)
end
function roots(a::FinFieldElem, i::Int)
_, x = polynomial_ring(parent(a), cached = false)
return roots(x^i-a)
end
function sturm_sequence(f::PolyRingElem{<:FieldElem})
g = f
h = derivative(g)
seq = typeof(f)[g,h]
while true
r = rem(g, h)
if r != 0
push!(seq, -r)
g, h = h, -r
else
break
end
end
return seq
end