4

Are there functions or algorithms which can generate integers which are necessarily composite, yet not yield any information about what factors it has?

For example, $f(x):=x^2-1$ is not what I'm after, as you immediately know it has factors of $x-1$ and $x+1$.

Closer are Sierpinski numbers and primefree sequences, but my understanding is that both of them are fundamentally built on top of small, finite covering sets, such that it would be trivial to spit out an element of that covering set which would divide any of those numbers.

The only approach I know of that would work is to simply pick some arbitrarily large number at random and do a Miller-Rabin test or similar to confirm compositeness and then return it, so I'll go ahead and say that's not what I'm looking for either. It's hacky, and ideally the generating function would work for any input, not just spot-check and prune.

Trevor
  • 6,022
  • 15
  • 35
  • related https://math.stackexchange.com/questions/1430189/formula-for-composite-numbers – Mirko Nov 22 '19 at 03:48
  • Given any prime number $p$, $p+1$ is composite without any information about its factors. – Klangen Nov 22 '19 at 09:31
  • 2
    In fact, using elliptic curves, a number was constructed which is even known to be semiprime (exactly two prime factors) without explicitely multiplying two primes. This number could be impossible to be factored in practice. I was very surprised that such a construction is possible. – Peter Nov 22 '19 at 10:24
  • 3
    @Klangen, $p+1$ is even and so divisible by 2. so we get some information about at least one factor. – user25406 Nov 22 '19 at 13:53
  • @Peter Do you have a link or search term for that? – Trevor Nov 23 '19 at 03:00

0 Answers0