3
$\begingroup$

At Factors of 1000 numbers up to googolplex, it's shown that for $G$=googolplex and $k \in (57, 101, 143, 167, 173, 219, 231, 257, 279, 303, 387, 587, 719, 741, 789, 813, 941, 971)$, the number $G-k$ has no prime factors under $3.5 \times 10^{14}$. I started wondering if any similarly gigantic numbers could be proven composite without the benefit of a known factor.

In 2005, Don Reble constructed an interesting semiprime with elliptic pseudo-curves and the Goldwasser-Kilian ECPP theorem. No factors are known, but we know the Reble number has exactly 2 prime factors.

Can a gigantic provably-composite number be constructed without the benefit of knowing any factors? Other than finding divisors, are there any primality tests that can quickly show that some carefully designed gigantic number isn't prime?

The number should have no "small" divisors.

Alternately, perhaps a provable-composite might be in a list of extremely rough numbers. A sample fake proof: "Assume for $k\in{1..1000}$ that all values $(10^{100}+k)! +1$ are prime. That would allow the construction of a Blahblah curve. By the Someguy theorem, such a construction is impossible. Therefore, at least one $k$ value yields a composite number". Are there any proofs similar to that useful for giving an example of a huge provable composite with no known divisors?

$\endgroup$
  • $\begingroup$ What's your criterion for gigantic? Most modern primality tests don't produce a factor. $\endgroup$ – Robert Israel Jan 13 '17 at 19:22
  • $\begingroup$ Robert, I'll assume you'll use some neat trick and primality test X to produce some huge composite number. It should be large enough that alternate primality test Y would take an inconveniently long time to check. $\endgroup$ – Ed Pegg Jan 13 '17 at 19:55
  • 1
    $\begingroup$ I will? I have my doubts about your assumption. $\endgroup$ – Robert Israel Jan 13 '17 at 20:50
  • $\begingroup$ I think elliptic curves with entries with magnitude about $(10^{100})!$ cannot be handled. Probably the only way to show compositeness for such numbers is finding a non-trivial factor. For the much smaller Fermat-number $\large F_{33}=2^{2^{33}}+1$, it is not known whether it is prime or composite $\endgroup$ – Peter Jan 14 '17 at 13:39

Your Answer

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

Browse other questions tagged or ask your own question.