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?
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.