On generating squarefree integers and primes?

Question

1. Given an $\alpha\in(0,1)$ and $n\in\Bbb N$ what are some known deterministic algorithms to sample $O(n^\alpha)$ (not just get one) square free integers of $n$ bits? Is it $O(n^{\alpha})$ complexity? By sample I mean can we get certain number so that atleast some fraction of them are some distance from each other.

2. Given an $\alpha\in(0,1)$ and $n\in\Bbb N$ what are some known probabilistic algorithms to sample $O(n^\alpha)$ square free integers of $n$ bits that need not be primes? Is it $O(n^{\alpha})$ complexity?

3. Is it known if testing a given interval $[a,b]$ contains a prime is in $BPP$ (assume each $a$ and $b$ have $n$ bits)?

I want the certificate for square free numbers that are generated to be in poly time. Note we may not have a square free certificate without factoring but that does not preclude certification for outputs of particular algorithms to be in poly time (these numbers could be output in special ways or specially constructed).

Answer 1

Here is a naive idea which has much room for improvement (and still might not do what you want). Choose $k$ such that $\binom{2k}k\sim n^{\alpha}.$ Then find $2k$ distinct primes with $\frac{n}k$ bits and take the $k$-wise products of them.

Here is an example with $n=10000$ and $\alpha=1.$ So I want $10000$ square free integers, each of $10000$ bits. Since $\binom{16}8=12870,$ I will be fine with $16$ primes each with $\frac{1000}{8}=1250$ bits. Maple tells me in $1.2$ seconds that the first 16 primes larger that $2^{1250}$ are $2^{1250}+j$ for $j \in \{1447, 3879, 7243, 8545, 8937, 11433, 11445, 12045, 13999, 15055, 15595, 16105, 16377, 16897, 17593, 18285\}.$ Now one just needs to step through the products of them $8$ at a time.

I imagine that those are probable primes and am not sure how hard it would be to find certificates.

I realize this is short of an analysis of the complexity as $n$ increases but I'll leave it there since there might be simple modifications which would be much more efficient.

For example the calculation above was fast enough, but one might instead find $400$ distinct primes with $50$ bits each (which took Maple under $0.2$ seconds), split them into $16$ groups of $25,$ and use the products in place of the $16$ primes above. -OR- One could generate $202$ primes that big, so the full product has $10100$ bits. There are $\binom{202}2=20301$ ways to leave out $2$ of those primes (or $10201$ if one comes from the first $101$ and the other form the last $101$.)

Answer 2

1. A square-free number with about $n$ bits that we can compute in $\tilde{O}(n)$ time is $n\#$, the primorial. Maybe it can be done in $O(n)$ but that's going to depend even more on the model.
2. We can guess one and almost certainly be right with $\tilde{O}(1)$ time complexity ($O(1)$ if in this model we can check for divisibility by a constant in constant time). But to verify it the best I can think of is subexponential expected time by factoring it with GNFS.
3. Apparently not as of 2011 (see page 3).