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).

  • $\begingroup$ Please explain what you mean by BPP, and how that depends on $a$ and $b$. Also, try to ask one question at a time to avoid awkward situations when someone answers one part and someone else answers another part. $\endgroup$
    – GH from MO
    Dec 16 '17 at 2:52
  • $\begingroup$ From: oeis.org/A019565 Check the link to see if the spread of square frees is sufficient for your needs. Mathematica recursion to create some square free numbers. b[0] := {1}; b[n_] := Flatten[{ b[n - 1], b[n - 1] * Prime[n] }]; a = b[6] (* Fred Daniel Kline, Jun 26 2017 *) $\endgroup$
    – Fred Kline
    Dec 16 '17 at 8:15
  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).
  • $\begingroup$ Sorry actually I was thinking more of sampling. let me update appropriately. $\endgroup$
    – Mr.
    Dec 16 '17 at 3:37

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$.)

  • $\begingroup$ So we need to start with some primes. correct? No other seem obvious. If there is another way would it be interesting? $\endgroup$
    – Mr.
    Dec 16 '17 at 11:41
  • $\begingroup$ It is probably less efficient, but one could find integers $m$ with no divisor less than $\sqrt[3]{m}$ i.e.each either a prime or a product of two not so small primes. Now as long as you check that they are pairwise relatively prime (and none is a square) you can use them as above. Maybe there is a repository of RSA semiprimes.... $\endgroup$ Dec 16 '17 at 12:34
  • $\begingroup$ I am looking for a mathematical construction that does not start with primes or semi-primes but naturally produces them from some governing principles. $\endgroup$
    – Mr.
    Dec 16 '17 at 12:42
  • $\begingroup$ Turbo, what you're looking for might be too hard to do deterministically. $\endgroup$ Dec 16 '17 at 17:48
  • $\begingroup$ @AaronMeyerowitz Do you know the current best $c$ that is in arxiv.org/pdf/1009.3956.pdf? Can $c\rightarrow\frac12$ be possible? $\endgroup$
    – Mr.
    Dec 20 '17 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.