Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist?
Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of deciding if there are $n$ pairwise coprime integers each of $m$ bits?
What exactly interests you? It might be more interesting to ask about finding $m$ pairwise relatively prime numbers between $s$ and $t$ when $ts$ is "small" with respect to $s.$ The case $s=2^n$ and $t=2^{n+1}$ seems too broad. The best you can do is to take all the primes and prime powers in that range and augment that with some products $p\cdot p'$ where $p$ ranges over the primes less than $\sqrt{2^{n}}$ not used so far and, for each one, an appropriate prime cofactor $p'$.
Let me first discuss $n=20.$
The number of primes with exactly $20$ bits is $N=\pi(2^{21})\pi(2^{20}) =73586$. Given that, the answer to your question 2 with $n=20$ is definitely yes for $m$ below $N+1$ Then you can use just primes. One can stuff in $234$ more using prime powers and semiprimes (detals below). Doing question 1 for $m=70000$ would be tedious. If you wanted $n=20$ and $m=481$ then one could find $k$ , a $20$ bit multiple of $2\cdot 3\cdot 5\cdot 7\cdot 11=2310$ and take it along with $k+j$ for the $480$ numbers $j$ less than $2310$ and relatively prime to it.
What about finding the absolute largest size set of pairwise relatively prime $20$bit integers? I claim that it is not hard to find that it is $N+57+5+6+166$ the extra terms are for
 $57$ prime squares, $p^2$ for $1331 \leq p \leq 1447$.
 $5$ prime cubes, $p^3$ for $p=103,107,109,113,127$
 $6$ more: $37^4 ,17^5 ,11^6, 5^9,3^{13}$ and $2^{20}.$
 $166$ primes under $1024$ not yet used (we will give each one a prime cofactor)
If we pair each of the $166$ small ones with the largest possible large prime we get
$7 \cdot 299569, 13\cdot 161309, 19\cdot 110359, 23\cdot 91163, 29\cdot 72313, 31\cdot 67631, 41\cdot 5113$
and continue on to $991\cdot 2113, 997 \cdot 2099, 1009 \cdot \mathbf{2069},1013 \cdot 2069,1019 \cdot \mathbf{2053},1021 \cdot 2053 $
The only overlaps are the two shown in bold which can be replaced with somewhat smaller primes such as $1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039.$
The only "hard" step was perhaps that of computing $N=\pi(2^{21})\pi(2^{20})=15561182025=73586.$ Without that we wouldn't know exactly for what $m$ we pass from possible to not possible. But we would know how to get about where. For example easy estimates give $81519 \lt \pi(2^{20}) \lt 82158$ and $154701 \lt \pi(2^{21}) \lt 155852.$

$\begingroup$ There are so many issues with this obvious answer that everyone is first aware of 1. What is the gap between primes? 2. What is the complexity of choosing a prime? 3. What is the gap between coprime versus gap between prime numbers? 4. It is easier to choose two coprimes in $m+1$ time complexity while it is unclear how to choose even two primes and many other issues such as not quantifying 'might be as good as it gets'. $\endgroup$ – Brout Oct 8 '18 at 7:47


$\begingroup$ What is the complexity of picking one prime of $m$ bits? $\endgroup$ – Brout Oct 9 '18 at 0:49

$\begingroup$ To find $m$ pairwise relatively prime $n$ bit integers is not hard for manageable size $m.$ For $m=1$ anything will do. For $m=3$ use $\{2^n+j \mid j=1,2,3\}.$ Instead of primes take probable primes (or numbers with no small prime factors) and just check gcds. Or find $km$ primes each with $n/k$ bits and take products. $\endgroup$ – Aaron Meyerowitz Oct 9 '18 at 3:46

$\begingroup$ Please answer my question. Do you know the complexity of choosing a probable prime? Are you aware of polymath project on deterministic selection of primes? Please take a look. The last point you mention is the most relevant. $\endgroup$ – Brout Oct 9 '18 at 7:18