<p>Consider the integer factoring problem with exactly 2 prime factors <span class="math-container">$p.q=N$</span>. Given <span class="math-container">$N$</span> find the prime factors <span class="math-container">$p$</span> and <span class="math-container">$q$</span>. The problem is notoriously difficult (on classical computers) and is the basis of many widely used cryptographic algorithms including RSA.</p>
<p>Now, consider two restricted version of the problem.</p>
<p><strong>Instance:</strong> Given <span class="math-container">$N$</span> such that it has 2 prime factors <span class="math-container">$p, q$</span> and <span class="math-container">$p&lt;q$</span>:</p>
<p><strong>Problem 1:</strong> Recover the <span class="math-container">$2^{nd}$</span> last/least bit of smaller prime factor <span class="math-container">$p$</span> (instead of a complete factorization) with 100% certainty.</p>
<p><strong>Problem 2:</strong> Recover the <span class="math-container">$2^{nd}$</span> last/least bit of smaller prime factor <span class="math-container">$p$</span> (instead of a complete factorization) with at most 50% one sided error. For example: If we say the bit is 1 then its 100% provably correct. But if we say the bit is 0 then there is a 50% chance of being correct.</p>
<p>What is the computational complexity of these 2 problems. And how are they related to the original factoring problem?</p>
<p>I did some search here but couldn't find an answer to this on this forum. Can someone please comment?</p>

CC BY-SA 4.0
2024-08-13T04:41:58.707Z
I'd guess this is just as hard as factoring, but I don't see a way to prove that
Command Master
CC BY-SA 4.0
2024-08-14T15:54:06.927Z
can someone please help?
TheoryQuest1
<cc.complexity-theory><ds.algorithms><factoring>
Complexity of single bit recovery version of Integer Factorization problem
TheoryQuest1
# Complexity of single bit recovery version of Integer Factorization problem

(Asked by: username_0 on 2024-08-12)

Consider the integer factoring problem with exactly 2 prime factors $p.q=N$. Given $N$ find the prime factors $p$ and $q$. The problem is notoriously difficult (on classical computers) and is the basis of many widely used cryptographic algorithms including RSA.

Now, consider two restricted version of the problem.

**Instance:** Given $N$ such that it has 2 prime factors $p, q$ and $p:

**Problem 1:** Recover the $2^{nd}$ last/least bit of smaller prime factor $p$ (instead of a complete factorization) with 100% certainty.

**Problem 2:** Recover the $2^{nd}$ last/least bit of smaller prime factor $p$ (instead of a complete factorization) with at most 50% one sided error. For example: If we say the bit is 1 then its 100% provably correct. But if we say the bit is 0 then there is a 50% chance of being correct.

What is the computational complexity of these 2 problems. And how are they related to the original factoring problem?

I did some search here but couldn't find an answer to this on this forum. Can someone please comment?

**Tags:** cc.complexity-theory, ds.algorithms, factoring
> **Comments:**
> **username_1**: I'd guess this is just as hard as factoring, but I don't see a way to prove that  
> **username_0**: can someone please help?  

---

## 0 answers

