I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$.

Given : $g_k(x,y)$, where $deg_y(g_k(x,y)) < y^{2^{k}}$ and $deg_x(g_k(x,y)) < d $.

Find : $G(x,y)$ and $l_k(x,y)$. (non trivial)

I know that $G(x,y) = g_k(x,y) l_k(x,y)$ forms a linear system with $y^{2^{k +1}} \times 2d $ many equations and I can solve those equations. But I don't know how to solve correctly $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$.

Here is a problem, suppose after multiplying $g_k(x,y)$ and $l_k(x,y)$, I got a term $y^{2^{k}}$, but after doing mod operation this term is going to become $0$. So my question is, how to resolve this issue.

  • 1
    $\begingroup$ Choose $G = g_k$ and $l_k = 1$. I think you're missing something. $\endgroup$ – Yuval Filmus Mar 18 '17 at 8:26
  • $\begingroup$ @Yuval Filmus yes, I have edited my question. I am looking for non trivial $G$ and $l_k$ $\endgroup$ – aaag Mar 18 '17 at 8:29
  • 1
    $\begingroup$ You can solve the equation for every $l_k$ by calculating $G$ using the formula $G = g_k l_k \bmod{y^{2^k}}$. $\endgroup$ – Yuval Filmus Mar 18 '17 at 8:40
  • $\begingroup$ But sill there is a problem that I have mentioned in the second last line. $\endgroup$ – aaag Mar 18 '17 at 8:49
  • $\begingroup$ Why is terms being 0 a problem? Do you know how to compute modular inverses? $\endgroup$ – Discrete lizard Mar 27 '17 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.