On a efficient algorithm for factoring bivariate polynomials modulo composite modulus assuming the solution is unique
43 views
Skip to first unread message
Georgi Guninski
May 14, 2024, 9:53:12 AMMay 14
to sage-...@googlegroups.com
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?
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?
Reply all
Reply to author
Forward
0 new messages