Factors of integers of the form $p-2^\lambda n$.

Question

Here $p$ is an odd prime, $n$ is uniform on $[0, 2^\lambda]$, and $\lambda$ is a constant. We define distribution $\mathcal{D}$ by: $$x \xleftarrow{\$} p-2^\lambda n$$

Assume $p \approx 2^{4\lambda}$, $\lambda \in \{128, 256\}$, and $0 \leq k \leq \log_2 \lambda$. Do a non-negligible fraction of samples from $\mathcal{D}$ contain a (possibly composite) factor within $\left[2^{3\lambda+k}, 2^{3\lambda+k+2}\right]$? A sample contains an appropriate factor if any subset product of the prime factors satisfies the range requirement.

I'd like to obtain some lower bound on the density of choices of $n$ which lead to an appropriate subset of factors. I'm not sure how to attack this problem.

Answer 1

So you know $\log2\lambda = \{7,8\}$. And $p−2\lambda n \approx 2^{4\lambda} - 2^{\lambda}n$, so the first thing you need to do is establish your domain. Although its too large to calculate individually, perhaps you can look up a very large prime somewhere, and take a ballpark figure for $n=1/$.

You need to find a way to get a prime factorization for $p-2^\lambda$, put it in a totient function and show that it (maybe) has a product in your range.

Good luck, hopefully somebody else knows more than me

Answer 2

So I've been thinking this all day, read an article on wired. https://www.wired.com/2014/12/mathematicians-make-major-discovery-prime-numbers/

If you consider the prime number theorem, $ \pi(n)~ N/logN $ it says that the distribution of primes increases with the $log(N)$.

Because you have a static distribution over your domain that is not exponential, the probability of the range being coprime will have even distribution, would be my hypothesis.

And we have from wikipedia

"the probability of two randomly chosen numbers being relatively prime is $6/π^2$."

So if I were to choose a value for $E>φ(n)$, I would try $N/loglog(N)$ or $N/2loglogN$.

You may be able to look at the probable distribution and infer your conclusions from that. Is it even feasible to factor $ 2^λ$ (very large) integers? Thinking about it, if you go to the trouble of factoring each integer then there is no need for a totient.