42 views

Skip to first unread message

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

Search

Clear search

Close search

Google apps

Main menu