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: sage-8.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:

Status badges

Description

Consider the following: 

----------------------------------------------------------------------
| Sage Version 5.1, Release Date: 2012-07-09                         |
| Type "notebook()" for the browser-based notebook interface.        |
| Type "help()" for help.                                            |
----------------------------------------------------------------------
sage: R.<x> = IntegerModRing(20000009)[]
sage: eq = x^6+x-17                      
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+x-17                      
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+x-17                      
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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 4 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to public/13825
  • Commit set to f39a8f3ed36766ed2c13c1c9760ff46ee1897648
  • Milestone changed from sage-6.4 to sage-8.3
  • Status changed from new to needs_review

first tentative

New commits:

​f39a8f3trac 13825 use chinese remainer theorem to find roots for some Zmod(n)[x]

comment:6 Changed 4 years ago by git

  • Commit changed from f39a8f3ed36766ed2c13c1c9760ff46ee1897648 to 8fda9641f3527c3cff3f049ecc0e619415b7798f

Branch pushed to git repo; I updated commit sha1. New commits:

​8fda964trac 13825 fixing one doctest

comment:7 Changed 4 years ago by zimmerma

looks good to me. Just a tiny remark: if the modulus is not square free, we can also call roots on each pk and use CRT. Even if roots mod pk is slow, this will be better. Otherwise I'm happy to give a positive review.

Last edited 4 years ago by zimmerma (previous) (diff)

comment:8 Changed 4 years ago by git

  • Commit changed from 8fda9641f3527c3cff3f049ecc0e619415b7798f to 74733709b81eb1a2235f4620b357d10e4f05ec34

Branch pushed to git repo; I updated commit sha1. New commits:

​7473370trac 13825 better code for roots in all Zmod(N)[x]

comment:9 Changed 4 years ago by chapoton

Here is a slightly better version, that works also for non-square 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 zimmerma

  • 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 vbraun

  • Branch changed from public/13825 to 74733709b81eb1a2235f4620b357d10e4f05ec34
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.