0

Pow(x,2)=13 (mod N)

For figuring out the x value in huge numbers N, any fastest method? N is a square number and the range 1<N<pow(10,30)

eagleofnorth
  • 29
  • 4
  • What means "N begins from 1 to pow(10,30)"? Do you want to solve "Pow(x,2)=13 (mod n)" for a huge n? Can you give an example for n? Why do you need to solve this equation? – miracle173 Jan 05 '22 at 08:28
  • If n is prime, you can use [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm). If n is not prime, solving for x is equivalent to factorising according to that page. – Jaap Scherphuis Jan 05 '22 at 08:38
  • I need to solve a binary quadraric form problem and to search x values in a loop, but for sure I need a fast calculation algorithm. N is a square number in a loop . The loop starts from 1 and ends pow (10,30) – eagleofnorth Jan 05 '22 at 08:38
  • 2
    Do you mean : What are the solutions (if there are some) for $$x^2\equiv 13\mod n$$ for $1\le n\le 10^{30}$ ? – Peter Jan 05 '22 at 08:48
  • @JaapScherphuis Fortunately, in the range the author needs, factorization is absolutely routine. – Peter Jan 05 '22 at 08:50
  • 1
    Yes and n is a square number, exactly. Thanks – eagleofnorth Jan 05 '22 at 08:50
  • Pleas could you rewrite your post so that it is understandable? Is N and n the same number? – miracle173 Jan 05 '22 at 08:53
  • So the module n is a square number? – miracle173 Jan 05 '22 at 08:54
  • 1
    So you could factorise $N$ (you only need factorise its square root, a 15 digit number), use a generalisation of Tonelli-Shanks to solve the equation modulo each prime power that is in the factorisation of $N$, and then use the Chinese remainder theorem to combine those to get the solutions to the original modulo $N$ equation. A computer could do all this in milliseconds. – Jaap Scherphuis Jan 05 '22 at 09:11
  • Thanks :) checking that algorithm. – eagleofnorth Jan 05 '22 at 09:13
  • [Wolfram Alpha](https://www.wolframalpha.com/input/?i=x%5E2%3D13+modulo+123456789012342%5E2) can solve this easily. – Jaap Scherphuis Jan 05 '22 at 09:16

0 Answers0