1
$\begingroup$

I tried to prove that $\text{FACTORING} \le_P \text{SQROOT}$ in a general setting, so $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$.

THEOREM:Let $n$ be a composite number and let $x$ and $y$ be integers such that $x^2 \equiv y^2 \pmod n$ and $x \not \equiv \pm y \pmod n$ holds. Then $\gcd(x+y, n)$ and $\gcd(x-y, n)$ are non-trivial divisors of $n$.

My attempt:

$\text{FACTORING} \le_P \text{SQROOT}$: Suppose we have an algorithm $\mathcal{A}$ that solves $\text{SQROOT}$. We show that we can then factor $n$ with prime factorisation $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$. Select a random $x \in Z/nZ$ with $\gcd(x,n) = 1$. Compute $a = x^2 \pmod n$ and use $\mathcal{A}$ to find a square root $y$ of $a$ modulo $n$. If $y \equiv \pm x \pmod n$ choose another $x$ and repeat this process until a $y$ with $y \not \equiv \pm x \pmod n$ is found. Since there are $2^k$ distinct square roots of $a$ modulo $n$ the chance that said procedure needs to be repeated is $\frac{1}{2^{k-1}}$. So by the theorem above we can find two non-trivial divisors of $n$ in expected polynomial time. Repeating this procedure for the thus found factors of $n$ we can find the prime factorisation of $n$ in expected polynomial time.

I am a bit unsure about the whole "expected polynomial time" thing. I have only heard informal definitions of it until now. Could you please have a look at my proof?

EDIT: I initially accepted the answer of Meir Maor below, but there was a gap in it as I just realised:

$k=2$ is the worst case. But this implies only that $n=p_1^{\alpha_1}p_2^{\alpha_2}$, not $n=p_1 p_2$. So we still have to find some non-trivial divisors of the thus found factors of $n$ to get $p_1$ and $p_2$. I would like to keep the rigour of Meir Maor's answer, but I do not know how to determine the runtime of this procedure. Could you help me?

$\endgroup$
3
  • 1
    $\begingroup$ Can you compute the probability that the factoring algorithm succeeds in terms of the probability that $\mathcal A$ succeeds? Interpret a series of independent trials as a negative binomial distribution; what's the expected number of trials, or the expected cost to execute the machine for that many trials? $\endgroup$ Nov 27, 2019 at 23:31
  • $\begingroup$ Sorry but I do not get what you are trying to say. What is a NEGATIVE binomial distribution? $\endgroup$
    – 3nondatur
    Nov 28, 2019 at 8:58
  • 1
    $\begingroup$ The negative binomial distribution is the distribution on the number of independent Bernoulli trials before a certain number of successes (or the number of failures before a certain number of successes, depending on how you parametrize it; beware fence posts). Here a Bernoulli trial is a run of your algorithm, which has some specific success probability that you can compute in terms of the success probability of $\mathcal A$, and you want to know the expected number of trials before a single success of the combined algorithm. $\endgroup$ Nov 28, 2019 at 14:41

1 Answer 1

1
$\begingroup$

Your proof is essentially correct. You may improve rigor by either calculating exactly or giving a bound on it's expected runtime.

If we take the simple case(which is also the worst case) where k=2 we get a probability of 1/2 to get a different root.

It should be noted that since our root x was uniformly random over Z/nZ it is also uniformly random over the roots of a. And therefor the probability of success at each attempt is 1/2 regardless of how our SQROOT algorithm chooses which root to provide.

If the probability is 1/2 per iteration the expected number of iterations is 2. This can be as 1/2+1/4+1/8... With probability 1/2 it takes 1 iteration with probability 1/4 it takes exactly 2 (fail, success) with probability 1/8 it takes exactly 3 (fail,fail, success) etc.

For k>2 the probability of success only increases and the expected invocation count is lower.

Therefor the expected runtime is 2 invocations of SQROOT + O(log(n)). The additional element is for the gcd and random selection part (or even receiving input and giving output).

$\endgroup$
3
  • $\begingroup$ I am sorry to bother you again but there is a gap in your argumentation. You are right that $k=2$ is the worst case. But this implies only that $n=p_1^{\alpha_1}p_2^{\alpha_2}$, not $n=p_1 p_2$. So we still have to find some non-trivial divisors of the thus found factors of $n$ to get $p_1$ and $p_2$. But how could I express this with a bit more rigour? $\endgroup$
    – 3nondatur
    Dec 8, 2019 at 23:00
  • 1
    $\begingroup$ Though we still have multiple roots. We have at least 2 roots which is sufficient. $\endgroup$
    – Meir Maor
    Dec 9, 2019 at 4:53
  • $\begingroup$ Ok I think I got it now thanks again. $\endgroup$
    – 3nondatur
    Dec 9, 2019 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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