I am working on Quadratic Sieve and at some stage I need to find $$ \sqrt{\prod_{k=1}^n y_k} \pmod{N} $$
Now the Product (inside square root) getting bigger and bigger (up to few hundred numbers) and I can't apply mod before square root operation. My question is, can I apply some sort of modulus inside square root to keep the product term down. Ultimately the result will be between 0 to N-1.
What I'm doing now, dividing the product by some $p^2$ and letting $p$ out of square root and applying the mod outside root when possible.
For an example, $$ \begin{split} s &= \sqrt{625 \cdot 117649\cdot 529\cdot 707281\cdot 2565726409\cdot 2809} \pmod{1113911}\\ &= 25 \sqrt{117649\cdot 529\cdot 707281\cdot 2565726409\cdot 2809} \pmod{1113911} \quad \text{as } 625 = 25^2 \\ &= 25\cdot 343 \sqrt{529\cdot 707281\cdot 2565726409\cdot 2809} \pmod{1113911} \quad \text{as } 117649 = 343^2 \\ &= 25\cdot 343 \cdot 23 \sqrt{707281\cdot 2565726409\cdot 2809} \pmod{1113911} \quad \text{as } 529 = 23^2 \\ &= 25\cdot 343 \cdot 23 \cdot 841 \sqrt{2565726409\cdot 2809} \pmod{1113911} \quad \text{as } 707281 = 841^2 \\ &= 165866225 \sqrt{2565726409\cdot 2809} \pmod{1113911} \\ &= 1007397 \sqrt{2565726409\cdot 2809} \pmod{1113911}, \\ \end{split} $$ the last step being so since $165866225 \pmod{1113911} \equiv 1007397$, and so on.
Is there any better way to do this?
Thank you.