0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is rather do a research question. See factor base. $\endgroup$ – kelalaka Nov 18 '19 at 20:26
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Nov 18 '19 at 20:34
  • $\begingroup$ @fgrieu I suppose 𝑥^2 ≡ 𝑎 (mod 𝑛) should return multiple results (x1, x2, x3, x4), instead of a single one. $\endgroup$ – Caren Lai Nov 18 '19 at 20:55
  • 2
    $\begingroup$ @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. $\endgroup$ – fgrieu Nov 18 '19 at 22:05
  • $\begingroup$ @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. $\endgroup$ – Caren Lai Nov 19 '19 at 5:06
0
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thank you very much. That helps. I'll try to understand. $\endgroup$ – Caren Lai Nov 21 '19 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.