Sorry for offtopic. 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] 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 -- 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 on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD9xxLe5vkmFp40hesFbNrdnOz_rh2gpsWMEMDZsLm51uA%40mail.gmail.com.
