We found and implemented in sage efficient algorithm for factoring
bivariate polynomials modulo composite modulus assuming the solution
is unique up to a constant factor.
More formally let $K=\mathbb{Z}/n\mathbb{Z}[x,y]$.
Given $F \in K$ in general we can find solution $f,g$ such
that $F=f g$ assuming $f,g$ are unique up to a constant factor
(by constant factor we mean if $f,g$ is solution then another
solution is $g_1=C g,f_1=C^{-1} f$).
The algorithm was tested on 2000 bits integers by generating
random $f,g$ and then tried to recover them given $F$.
Probably the algorithm may fail on some cases.
>Q1 Is this result known?
>Q2 Is it of interest?
--
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/CAGUWgD-VJknvg0rNLcWZ1mX7gJoT06udK86DHud67-N7rehjtg%40mail.gmail.com.
