Skip to main content
Post Undeleted by user124864
Post Deleted by user124864
added 16 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

SupposeWhat is maximum $p\in(0,\frac12)$ such that if we know $2p\in(0,1)$ fraction of the bits of $PQ$ exactly where $P$ andwith $Q$ are$P,Q$ primes is it is possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in polynomial time?

Suppose we know $2p\in(0,1)$ fraction of the bits of $PQ$ exactly where $P$ and $Q$ are primes is it possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in polynomial time?

What is maximum $p\in(0,\frac12)$ such that if we know $2p\in(0,1)$ fraction of bits of $PQ$ with $P,Q$ primes it is possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in polynomial time?

Post Undeleted by user124864
Post Deleted by user124864
added 12 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Suppose we know $4/5$$2p\in(0,1)$ fraction of the bits of $PQ$ exactly where $P$ and $Q$ are primes is it possible to identify $P,Q$ within $2/5$$p$ fraction of bits in each of $P$ and $Q$$P,Q$ with certainty in polynomial time?

Suppose we know $4/5$ of the bits of $PQ$ exactly where $P$ and $Q$ are primes is it possible to identify $P,Q$ within $2/5$ of bits of $P$ and $Q$ with certainty in polynomial time?

Suppose we know $2p\in(0,1)$ fraction of the bits of $PQ$ exactly where $P$ and $Q$ are primes is it possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in polynomial time?

Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Uncertainty in semiprime factors

Suppose we know $4/5$ of the bits of $PQ$ exactly where $P$ and $Q$ are primes is it possible to identify $P,Q$ within $2/5$ of bits of $P$ and $Q$ with certainty in polynomial time?