1
$\begingroup$

Are there any software tools to find modular square roots of $y$ in $$x^2\equiv y\bmod p^t$$ where $p$ is a prime $\geq2$?

Are there any special techniques which can speed up at $p=2$?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Hensel's lemma will be easiest, once you've got a square root for $t = 1$ with $p > 2$ or (if I remember correctly) $t = 3$ with $p = 2$. $\endgroup$
    – LSpice
    Commented Jun 17, 2022 at 22:32
  • $\begingroup$ @LSpice Thank you. Any software tools? $\endgroup$
    – Turbo
    Commented Jun 17, 2022 at 22:33
  • 3
    $\begingroup$ Having custom software for Hensel's lemma seems like overkill. I am sure it is built in to any system that can do modular arithmetic. For example, Mathematica has PowerModList. $\endgroup$
    – LSpice
    Commented Jun 17, 2022 at 22:35
  • $\begingroup$ Ah that is good information. $\endgroup$
    – Turbo
    Commented Jun 17, 2022 at 22:36

1 Answer 1

Reset to default
6
$\begingroup$

All square roots of $y$ are obtained by taking any particular square root of $y$ and multiplying it by a square root of 1. So, the problem is split into two:

  • find one (any) square root of $y$;
  • find all square roots of 1.

In PARI/GP, both problems are solved more or less easily. E.g., for the first problem one can employ p-adic numbers and compute sqrt(y + O(p^t)).

This script computes all square roots, even modulo composite numbers.

Improve this answer
$\endgroup$

You must log in to answer this question.

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