search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 480 forks source link

CRT for polynomials mod n #31731

Open roed314 opened 3 years ago

roed314 commented 3 years ago

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))
True

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

Component: number theory

Branch: u/roed/poly_crt

Issue created by migration from https://trac.sagemath.org/ticket/31731

roed314 commented 3 years ago

Branch: u/roed/poly_crt