Preprint: Efficient probabilistic factorization of F(x,y)=g(x,y) f(x,y) modulo composite integers n assuming the solution is unique.

[Georgi Guninski <gguninski@gmail.com>]

I hope someone improve this.

We give efficient probabilistic factorization of F(x,y)=g(x,y) f(x,y)
modulo composite integers n assuming the solution is unique.

The main contribution is the observation that `Ideal(J).groebner_basis()`
is efficient for overdetermined `J` and it works modulo n

The preprint is at [1] and the code is at [2] and on mathoverflow's
answer [3]

Sage session:

sage: %runfile factor_groebner2.sage
sage: set_random_seed(1);p1=random_prime(2**1000);p2=random_prime(p1);n=p1*p2
sage: Kxy.<x,y>=Integers(n)[]
sage: D2,D3=2,3
sage: g2=Kxy.random_element(degree=D2);f2=Kxy.random_element(degree=D3);F2=g2*f2
....:
sage: time gg=factorgroebner2(F2,D2,D3)
CPU times: user 232 ms, sys: 12.8 ms, total: 245 ms
Wall time: 2.68 s
sage: gg[0]*gg[1]==F2
True
sage: gg[0].degree(),gg[1].degree()
(2, 3)


[1] https://www.researchgate.net/publication/380720202_Efficient_probabilistic_algorithm_for_factoring_bivariate_polynomials_modulo_composite_integers_with_unknown_factorization_assuming_the_solution_Fxygxy_fxy_is_unique
[2] https://www.guninski.com/factor_groebner2.sage
[3] https://mathoverflow.net/questions/471255/on-a-efficient-algorithm-for-factoring-bivariate-polynomials-modulo-composite-mo