Opened 14 months ago

Last modified 8 weeks ago

#31731 new enhancement

CRT for polynomials mod n

Reported by: roed Owned by:
Priority: major Milestone: sage-9.7
Component: number theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/roed/poly_crt (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges


I implemented this for #31548 but ended up not using it, so I made this ticket.

sage: moduli = [4, 9, 25, 49]
sage: N = prod(moduli)
sage: S.<x> = Zmod(N)[]
sage: polys = [Zmod(m)['x']([sqrt(m)] + [0]*(sqrt(m)-1) + [1]) for m in moduli]
sage: f = polys[0].crt(*polys[1:])
27000*x^7 + 15876*x^5 + 34300*x^3 + 11025*x^2 + 40530
sage: all(g == f.change_ring(Zmod(m)) for (g, m) in zip(polys, moduli))

The interface should probably also support CRT in k[x] and specifying polynomial moduli.

Change History (4)

comment:1 Changed 14 months ago by roed

  • Branch set to u/roed/poly_crt

comment:2 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:3 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:4 Changed 8 weeks ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.