RSA leak bits to factor N Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q.

Then, you would like to actually let me factor N, except you should tell me as few bits of information as possible. Say p and q are 4096 bits, then how many bits do you need to tell me in order for me to factor N in feasible amount of time?

Note that you can arbitrarily design how these bits are derived, as long as there is a PPT algorithm to compute these bits and there is a PPT algorithm to use these bits to factor N.
I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the $n/4$ least or $n/4$ most significant bits of $p$ where $n$ is the size of the modulus $N=pq$, $N$ can be efficiently factored. Additionally, given the $n/4$ least significant bits of $d$, one can reconstruct $d$ (and therefore factor $N$), if $e&lt;\sqrt{N}$. See Boneh's 20 year survey of attacks on RSA. See that paper and the reference within for the algorithms, etc. 

Since then, the bounds for $e$ have been update somewhat, but still requires leaking the same number of bits. Also, random subsets of bits are sufficient to factor where $(1-\frac{H_r}{r})\log{N}$ bits of $p$ are known ($H_r$ is the r-th harmonic number).