Opened 13 years ago
Closed 13 years ago
#1292 closed defect (fixed)
[with patch] bug in polynomial root finding mod n
Reported by: | was | Owned by: | cwitty |
---|---|---|---|
Priority: | critical | Milestone: | sage-2.8.15 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This was reported by michael to sage-devel on Nov 27, 2007. It's a genuine bug which gives incorrect mathematical results (hence the critical marking).
R=IntegerModRing(3^2) A=PolynomialRing(R,'y') y=A.gen() f=10*y^2 - y^3 - 9; f.roots(multiplicities=false) /// [1, 0]
print [k for k in R if f(k) == 0] /// [0, 1, 3, 6]
Attachments (1)
Change History (8)
comment:1 Changed 13 years ago by
comment:2 Changed 13 years ago by
In this particular case, roots() is done by factoring modulo n then extracting the roots from the linear factors. That algorithm makes no sense directly in case of a non-integral domain (unique factorization is irrelevant -- what matters if that a product is 0 then at least 1 factor is). Use {{{R.is_integral_domain()}.
sage: f.factor() (8) * (y + 8) * y^2
There is presumably another algorithm for finding roots that works given
a factorization even over a non-integral domain. Probably we should
list all zero-divisor products a*b = 0, then for each factor g_i(x)
of the
polynomial, find all y such g_1(y) = a, g_2(y) = b
. Also, worry about the
8 factor out front!
For now a quick hack would be to just do a stupid for loop to find all roots in the non-integral-domain case -- at least that would be mathematically correct.
comment:3 Changed 13 years ago by
- Owner changed from somebody to cwitty
comment:4 Changed 13 years ago by
For the IntegerModRing? case, we could probably do something with http://www.shoup.net/ntl/doc/ZZ_pXFactoring.txt .
Changed 13 years ago by
comment:5 Changed 13 years ago by
- Milestone changed from sage-2.9 to sage-2.8.15
- Summary changed from bug in polynomial root finding mod n to [with patch] bug in polynomial root finding mod n
I've attached a patch that only does root finding by factorization if the coefficient ring is an integral domain; so for this problem, it uses enumeration instead, and does find all four roots. I think that using a non-stupid root-finding algorithm here should be a separate ticket; that's an enhancement request, instead of a critical bug fix.
NOTE THAT THIS PATCH REQUIRES THAT PATCHES FROM #1270 AND #1273 ARE ALREADY APPLIED. This is just because #1273 happens to touch the same paragraph in the docstring of roots() that I needed to change for this patch, so I had to choose between depending on #1273 or conflicting with #1273. Since I hope and expect that #1273 will be applied for 2.8.15, I chose to depend on it; if #1273 is rejected, I'll upload a modified patch that doesn't depend on #1273.
comment:6 Changed 13 years ago by
Looks good to me.
comment:7 Changed 13 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in 2.8.15.alpha2.
In this case, the roots method tries to factor f and extract roots from the factorization:
I'm told that we need to check that the coefficient ring forms a unique factorization domain before using this strategy, but I don't know how to check that in Sage.