Let me know if this can be contributed to sage.
We implemented algorithm for factorization of bivariate polynomials
modulo composite integers with unknown factorization [1].
The main idea is that sage can compute groebner basis modulo composite
integers and for overdetermined systems it returns the unique
solution.
Main idea:
Given F(x,y)=f(x,y)*g(x,y), make the coefficients of g,f variables
a_i, equate the coefficients in a_i in F. We get overdetermined
nonlinear system in a_i. Experimentally the system in most cases can
be solved with groebner basis. If F is irreducible, we get basis
$(1)$, which might be of interest. This can be generalized to
multivariate polynomials.
In some cases, mainly related to integer factorization like factoring
$x^2-a$ the algorithm fails.
Attached is a very early implementation, we have better implementation.
We get experimental support for the algorithm.
Also I am looking for co-developers and co-authors for a short note
about the algorithm.
[1]
https://mathoverflow.net/questions/471255/on-a-efficient-algorithm-for-factoring-bivariate-polynomials-modulo-composite-mo
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/sage-devel/CAGUWgD-vn-KC6NcOHQPbFZj8zz4ByK0PMyjivCbvURvM1weK4A%40mail.gmail.com.
def factorgroebner2(F,D_g,D_f,asol=1,retg=False):
"""
unique solution modulo n up to constant factor
the factorization of n is not known
may fail, at least in cases when the polynomial factorization
leads to factorization of n
f(x,y)*g(x,y)=F, deg(g)=D_g,deg(f)=D_f
Author Georgi Guninski, Tue May 14 12:01:23 PM UTC 2024
Example usage:
set_random_seed(1);p1=random_prime(2**140);p2=random_prime(p1);n=p1*p2
Kxy.<x,y>=Integers(n)[]
D2,D3=2,3
g2=Kxy.random_element(degree=D2);f2=Kxy.random_element(degree=D3);
F2=g2*f2
time gg=factorgroebner2(F2,D2,D3)
#Wall time: 1.64 s
F2==gg[0]*gg[1]
"""
#assert D_g != D_f,"deg(f)=deg(g) currently not supported due to
non-uniquess"
Ko=F.parent()
Kp=F.base_ring()
XF,YF=F.parent().gens()
varsx="%s,%s,"%(XF,YF)+",".join(["a_"+str(i) for i in range(1000)])
Kxy=PolynomialRing(Kp,varsx) #XXX compute
ge=Kxy.gens()
X,Y=ge[:2]
geai=ge[2:]
F=Kxy(F)
moxy=Kxy.monomial_all_divisors((X*Y)**max(D_g,D_f))
moxy += [Kxy(1)]
mo1=[i for i in moxy if i.degree()<=D_g]
mo2=[i for i in moxy if i.degree()<=D_f]
ga=iter(geai)
g=sum([i*next(ga) for i in mo1])
f=sum([i*next(ga) for i in mo2])
G=f*g-F
J=[]
D=D_g+D_f
for dx in range(D+1):
for dy in range(D+1):
h=G.coefficient({X:dx,Y:dy})
if h != 0: J += [h]
lg=len([i*j for i,j in g])
lf=len([i*j for i,j in f])
gb1=Ideal(J).groebner_basis()
if gb1==[1]:
#no solution
return False
deg2=[i for i in gb1 if i.degree() != 1]
if len(deg2) > 1:
if retg:
print("error in groebner")#XXX
return gb1 #XXX
raise Exception("Fail in grobner basis")
if deg2:
ai0=deg2[0].variables()[0]
J += [ai0-asol] #XXX
gb1=Ideal(J).groebner_basis()
sol={}
for h in gb1:
v=h.variables()[0]
co0=h.constant_coefficient()
co1=h.coefficient({v:1})
sol[v]= -co0/Kp(co1)
gs=g.subs(sol)
fs=f.subs(sol)
gr=Ko(str(gs)) #XXX
fr=Ko(str(fs)) #XXX
return gr,fr
