# If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $$A$$ which takes $$y \in \{0, 1, \ldots , N − 1\}$$ as input, and outputs $$x \in \{0,1,\ldots,N − 1\}$$ such that $$x^2 \equiv y \pmod{N}$$. Design an efficient, randomized procedure that uses $$A$$ to get prime factors.

This is a homework problem for the graduate algorithm course.

It's similar to this question. The difference is that we don't have a specific number 51733469. My idea is that we can randomly pick a number $$a$$ between $$[1,n-1]$$, use $$A$$ to calculate it's modular square root and do exactly like the solution here? Or the randomly-picked number $$a$$ should satisfy any sort of condition?

• This is rather do a research question. See factor base. Nov 18 '19 at 20:26
• Hint: the problem with your idea of picking a random $a\in\{0,1,\ldots,N−1\}$ and submitting it to the algorithm is that you end up with a single $x\in\{0,1,\ldots,N−1\}$ with $x^2\equiv a\pmod n$. You want to have another. Asking again to the algorithm is of no help, for it can return the same $x$. You want to come up with that (hopefully) other $\tilde x$ with $\tilde x^2\equiv a\pmod n$ by yourself. Be lazy, and let the algorithm do the hard work.
– fgrieu
Nov 18 '19 at 20:34
• @fgrieu I suppose 𝑥^2 ≡ 𝑎 (mod 𝑛) should return multiple results (x1, x2, x3, x4), instead of a single one. Nov 18 '19 at 20:55
• @CarenLai: the equation $x^2\equiv a\pmod n$ (written as $x^2\equiv a\pmod n$BTW) does not return anything. It has solutions. The algorithm $A$ returns an $x$ with $x^2\equiv a\pmod n$ when given $a$. But assume the worse: that $A$ will always return the same result for a given input, even if there are several possible solutions. Hint: decide $a$ in a way such that you know a solution before the algorithm gives one, and notice that the algorithm can't read your mind.
– fgrieu
Nov 18 '19 at 22:05
• @fgrieu Yeah, That's true. What I forgot to mention is that I would do the algorithm $A$ multiple times, until I found the "correct" factors. The "correct" here means that the result of both gcd(f1 - f2, n) and gcd(f1 + f2, n) are prime numbers. Nov 19 '19 at 5:06

## 1 Answer

How many solutions are there for equation $$x^2\equiv y\pmod N$$?

That problem is easier when $$N$$ is odd and $$\gcd(y,N)=1$$ (notice that when either does not hold, we have a factor of $$N$$): there are either $$0$$ or $$2^k$$ solutions, where $$k$$ is the number of distinct primes $$p_i$$ dividing $$N$$. Proof starts with $$N$$ prime (see Legendre symbol), then a power of a prime, then the product of powers of distinct primes (using the Chinese Remainder Theorem).

Why the algorithm $$A$$ would always return the same output?

The proof thought to answer the question should work including when the algorithm $$A$$ always return the same output $$x$$ for input $$(y,N)$$, because nothing in the question's assumption "Suppose.." says that $$A$$ will return all solutions, or would eventually return all solutions when invoked repeatedly. Many algorithms are deterministic, that is always perform the same operations for a given input, including producing the same result. Actually, in cryptography, we often implicitly restrict to such deterministic algorithms, considering that a random behavior must come from an explicit extra random input.

Hint: you want to have two solutions: one you know beforehand, and one that the algorithm will give you. The algorithm can't read your mind, thus there's a chance that it will return another solution, and perhaps that will be helpful.

• Thank you very much. That helps. I'll try to understand. Nov 21 '19 at 22:22