New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
bug in polynomial root finding mod n #1292
Comments
comment:1
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. |
comment:2
In this particular case, roots() is done by factoring modulo n then extracting
There is presumably another algorithm for finding roots that works given For now a quick hack would be to just do a stupid for loop to find all roots |
comment:4
For the IntegerModRing case, we could probably do something with http://www.shoup.net/ntl/doc/ZZ_pXFactoring.txt . |
comment:5
Attachment: 1292.patch.gz 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
Looks good to me. |
comment:7
Merged in 2.8.15.alpha2. |
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).
Component: basic arithmetic
Issue created by migration from https://trac.sagemath.org/ticket/1292
The text was updated successfully, but these errors were encountered: