Opened 9 years ago
Closed 4 years ago
#13825 closed enhancement (fixed)
roots over IntegerModRing is horribly slow
Reported by:  zimmerma  Owned by:  malb 

Priority:  minor  Milestone:  sage8.3 
Component:  commutative algebra  Keywords:  
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Paul Zimmermann 
Report Upstream:  N/A  Work issues:  
Branch:  7473370 (Commits, GitHub, GitLab)  Commit:  74733709b81eb1a2235f4620b357d10e4f05ec34 
Dependencies:  Stopgaps: 
Description
Consider the following:
  Sage Version 5.1, Release Date: 20120709   Type "notebook()" for the browserbased notebook interface.   Type "help()" for help.   sage: R.<x> = IntegerModRing(20000009)[] sage: eq = x^6+x17 sage: time eq.roots(multiplicities=False) [3109038, 17207405] Time: CPU 202.93 s, Wall: 203.65 s
A faster method would be (when the modulus is not too large) to factor it, solve modulo the prime factors, and reconstruct using CRT:
sage: R.<x> = IntegerModRing(61)[] sage: eq = x^6+x17 sage: time eq.roots(multiplicities=False) [51, 37] Time: CPU 0.00 s, Wall: 0.00 s sage: R.<x> = IntegerModRing(327869)[] sage: eq = x^6+x17 sage: time eq.roots(multiplicities=False) [158217] Time: CPU 0.00 s, Wall: 0.00 s sage: crt([51,158217],[61,327869]) 3109038 sage: crt([37,158217],[61,327869]) 17207405
Change History (11)
comment:1 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:2 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:4 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:5 Changed 4 years ago by
 Branch set to public/13825
 Commit set to f39a8f3ed36766ed2c13c1c9760ff46ee1897648
 Milestone changed from sage6.4 to sage8.3
 Status changed from new to needs_review
comment:6 Changed 4 years ago by
 Commit changed from f39a8f3ed36766ed2c13c1c9760ff46ee1897648 to 8fda9641f3527c3cff3f049ecc0e619415b7798f
Branch pushed to git repo; I updated commit sha1. New commits:
8fda964  trac 13825 fixing one doctest

comment:7 Changed 4 years ago by
looks good to me. Just a tiny remark: if the modulus is not square free, we can also call roots on each p^{k} and use CRT. Even if roots mod p^{k} is slow, this will be better. Otherwise I'm happy to give a positive review.
comment:8 Changed 4 years ago by
 Commit changed from 8fda9641f3527c3cff3f049ecc0e619415b7798f to 74733709b81eb1a2235f4620b357d10e4f05ec34
Branch pushed to git repo; I updated commit sha1. New commits:
7473370  trac 13825 better code for roots in all Zmod(N)[x]

comment:9 Changed 4 years ago by
Here is a slightly better version, that works also for nonsquare free modulus N. I still reduce to prime fields for p dividing N, solve there, use the c.r.t. to get back to solution modulo rad(N), and then a naive iteration to find solutions modulo N.
comment:10 Changed 4 years ago by
 Reviewers set to Paul Zimmermann
 Status changed from needs_review to positive_review
this looks good to me. Great!
comment:11 Changed 4 years ago by
 Branch changed from public/13825 to 74733709b81eb1a2235f4620b357d10e4f05ec34
 Resolution set to fixed
 Status changed from positive_review to closed
first tentative
New commits:
trac 13825 use chinese remainer theorem to find roots for some Zmod(n)[x]