0
$\begingroup$

If $q$ is a prime what is the best method to compute roots of a quadratic polynomial $f(x)\equiv0\bmod q^2$ which is of form $x^2+bx+c\equiv0\bmod q^2$ where $b^2-4c\equiv0\bmod q$ and $gcd(b,q)=1$ and the cases are

  1. $b^2-4c\equiv0\bmod q^2$ (most interested) and
  2. $b^2-4c\not\equiv0\bmod q^2$?

If $q$ is composite with prime factorization known what is the best way?

If factorization of $q$ is unknown I believe the problem is at least as hard as factoring.

Improve this question
$\endgroup$
9
  • $\begingroup$ mathoverflow.net/questions/54936 is a duplicate $\endgroup$
    – Chris Wuthrich
    Commented Oct 5, 2021 at 8:30
  • $\begingroup$ ... which links to mathoverflow.net/questions/52081 $\endgroup$
    – Chris Wuthrich
    Commented Oct 5, 2021 at 8:38
  • $\begingroup$ After edit: The case when $p$ divides the discriminant isn't harder. To find the square root in $\mathbb{Q}_p$ the valuation has to be even and then use Hensel's lemma on the unit part. Which by the way is the usual algorithm $x \to 1/2(x+a/x)$ to find square roots. $\endgroup$
    – Chris Wuthrich
    Commented Oct 7, 2021 at 7:38
  • $\begingroup$ $\mathbb{Q}_p$ is the field of $p$-adic numbers. I don't think your question is asked at the right forum. $\endgroup$
    – Chris Wuthrich
    Commented Oct 7, 2021 at 7:40
  • $\begingroup$ So can you explain the answer explicitly for computational number theory purposes? I believe the problem is not exact duplicate. So perhaps reopenable? So is root mod $q^2$ computable in polynomial time? Is there a reference to what you are talking about? $b$ and $q$ may be assumed coprime. $\endgroup$
    – Turbo
    Commented Oct 7, 2021 at 7:41

1 Answer 1

Reset to default
0
$\begingroup$

If $q$ is prime then first solve $f(x) \equiv 0 \pmod q$ using the standard expression $\frac{-b \pm \sqrt{b^2-4ac}}{2a}$; there are three cases for $\sqrt{y} \pmod q$:

  1. If $y$ is not a quadratic residue $\operatorname{mod} q$, there are no solutions;
  2. If $q \equiv 3 \pmod 4$ then $\sqrt{y} \equiv y^{(q+1)/2} \pmod q$;
  3. Otherwise use Tonelli-Shanks.

Then lift the solution(s) from $\operatorname{mod} q$ to $\operatorname{mod} q^2$ using Hensel's lemma.

If $q$ is composite with known factorisation, I don't expect there to be a better solution than solving the equation for each prime factor and using the Chinese remainder theorem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you explain the Hensel lifting process for the two solutions? $\endgroup$
    – Turbo
    Commented Mar 16, 2022 at 0:22
  • $\begingroup$ @Turbo, it is described in great detail in en.wikipedia.org/wiki/Hensel%27s_lemma $\endgroup$
    – Peter Taylor
    Commented Mar 16, 2022 at 7:44
  • $\begingroup$ $f(x)$ for me is quadratic and the discriminant mod $q$ is $0$ while discriminant mod $q^2$ is not $0$. Are there any complications to applying the technique? Is there anything that would be different? $\endgroup$
    – Turbo
    Commented Mar 16, 2022 at 18:44
  • $\begingroup$ In my case $q|f'(root)$ and so there is no inverse of $f'(root)$ where $f(root)\equiv 0\bmod q$ holds and $disc\equiv0\bmod q$. Posted in math.stackexchange.com/questions/4405084/…. $\endgroup$
    – Turbo
    Commented Mar 16, 2022 at 21:46
  • $\begingroup$ Is it possible to avoid Hensel lifting? My equation is of form $$x^2-(a+b)x + ab = 0 \bmod q^2$$ where $a+b=0\bmod q$ and so I get $(x-r)^2=0\bmod q$. I know the answer is not $a,b$ for my purpose but one of the Hensel lifts. So there is no canonical uniqueness conditions for root modulo $q^2$? $\endgroup$
    – Turbo
    Commented Mar 23, 2022 at 13:53

Not the answer you're looking for? Browse other questions tagged .