-1
$\begingroup$

Closely related: what is the smallest known composite which has not been factored? If these numbers cannot be specified, knowing their approximate size would be interesting. E.g. can current methods factor an arbitrary 200 digit number in a few hours (days? months? or what?). Can current methods certify that an arbitrary 1000 digit number is prime, or composite in a few hours (days? months? not at all?).

Any broad-brush comments on the current status of primality proving, and how active this field is would be appreciated as well. Same for factoring.


Edit: perhaps my header question was something of a troll. I am not interested in lists. But if anyone could shed light on the answers to the portion of my question starting with "E.g.". it would be appreciated. (I could answer it in 1990, but what is the status today?)

$\endgroup$
1
  • 8
    $\begingroup$ Since we're talking about knowledge, we might wonder whether every even number, and every multiple of 5, count as numbers that are known not to be prime, even if they are numbers that no one has ever happened to write down. If we do count those as known, what about multiples of 7, or 137? There will definitely be some clear cases, but I suspect that at most points in time, there will be some medium-largish number that no one has ever bothered to test for primality, that would take only a moderately long time to test (say, a few hours). Of course, that doesn't address your main question $\endgroup$ Oct 21, 2009 at 5:42

7 Answers 7

11
$\begingroup$

Yes factoring is an active area. I think there are ranges (maybe $80$ digits?) where factoring is reasonably tractable but many integers have never been examined.

Hueristic tests tell us with extremely high confidence if much larger integers are prime. An actual proof certificate by ECM is never a problem in practice.

Some people care about numbers like $n!+1$ skipping many lower numbers. A large integer needs something interesting to make it desirable to crack

So I'll take your question as

What size are the smallest composite integers that people are trying to factor?

.

I'd guess around $200$ digits. I base this on the venerable and ongoing Cunningham project which started before 1925, and is still going strong. It is concerned with Factorizations of $b^n \pm 1$, $b = 2, 3, 5, 6, 7, 10, 11, 12$, up to High Powers Here are the $10$ most wanted composites. Also on that page are the slightly less desirable $24$ more wanted composites.

Most seem to be in $200$ to $300$ digit range.

The number one most wanted is $2,1207$- $C337$ This means that

$$2^{1207}-1=(2^{17}-1)(2^{71}-1)C337$$

The first two factors (of which the first is prime and the second a product of three primes) are explained by algebra and the fact that $1207=17\cdot71.$ The final factor has 337 digits and is know to be composite , but that is it (other than probably no easy factors).

That most wanted list is from $2016.$ Among the more wanted is a $278$ digit composite factor of $7^{359}+1.$ On the New factors received from July 3, 2017 to January 30, 2018O page one finds that a $70$ digit prime was extracted leaving a $208$ digit composite.

7, 359+ c278 2411303103482828219339285233829803927599026677829066502451625793020443. c208 NFS@Home snfs

This was a result from the distributed NFS@Home project using the special number field sieve.

Finally, on the new factorizations since January 30 2018 page one finds that this composite is the product of two primes. One listed and the other deducible from the given information.

7, 359+ c208 19792929490897848580163051528461396921535266011583367339063480695499122468294419091343065854809576593. p108 NFS@Home snfs

Browse those pages to see who decides what is wanted and why and much more.

$\endgroup$
1
  • 1
    $\begingroup$ Actually, for 2,1207- one has that a prime factor is 1 more than a multiple of 2414, and since finding such prime factors less than a trillion is quickly accomplished by computer, you are likely right in that no easy factor is present for the C337. Gerhard "Maybe There Are Moderate Factors" Paseman, 2018.03.26. $\endgroup$ Mar 27, 2018 at 2:34
9
$\begingroup$

Kenny's point in the comments is a good one as well, and it's also worth keeping in mind that the number of atoms in the observable universe is at most a few orders of magnitude more than 10^80, so writing down all the numbers with 100 or fewer digits is a hopeless task. (Certainly we haven't checked them all for primality!) That said, I'll try to give a rather rough answer to your questions.

1 terabyte, which is a good estimate for the size of a good commercially-available hard drive, is about 2^40 bits. Testing a number that small for primality is very easy (in fact, it's not terribly slow even with naive methods), so you could quite easily and cheaply list all the primes between about 1 and 2^35. Pushing higher than that, things start to get problematic -- there's just not enough space to hold all these numbers! If you gave a 1 TB hard drive to everyone on earth, there wouldn't be enough space to list all the primes between 1 and 2^70, which has about 23 digits. If you pick a random 25-digit number, odds are that it's never been tested for primality before. But it's easy to test such numbers for primality quickly, so this isn't a problem about primes so much as it is about the fact that the exponential function is big. So what about prime testing? How fast can we do that?

In practice, the best general method for primality testing seems to be elliptic curve primality proving, probably combined with trial division by small integers. To give you some idea of how efficient it is, the biggest number that's been proved prime by ECPP methods has around 20,000 digits, and the proof took 9 months via a distributed computing project (equivalent to several years on a top-of-the-line general-purpose processor.) A rough back-of-the-envelope calculation suggests that if you want to test for primality in at most a couple of weeks on a single machine, 10000 digits is probably too much, although 1000 seems very reasonable.

Factoring seems much harder. 200 digits is reasonable with a wide distributed computing project, but 2000 is likely to be way out of reach.

$\endgroup$
7
$\begingroup$

I don't think this is the right question to be asking. People aren't going to store long lists of primes. You might be able to store the first 10^12 or so primes (in some compressed form) on your hard drive; but testing the first number not on your table for primality, or factoring it, would be trivial.

There are similar questions you could ask where people actually do keep such lists -- for example, what's the smallest Mersenne number (number of form 2^n-1) whose primality is not known? This looks to be somewhere in the neighorhood of n = 15 million.

$\endgroup$
5
$\begingroup$

What is the smallest integer whose even/odd status is not known?

$\endgroup$
1
  • 4
    $\begingroup$ Ian, I get what you're trying to say here, but you're cheating just a little bit: any reasonable way of encoding positive integers leads to a O(1) or at worst O(log n) test to check whether n is even or odd. This isn't true for primes. $\endgroup$ Oct 21, 2009 at 7:44
5
$\begingroup$

Closely related: what is the smallest known composite which has not been factored?

As others have pointed out, this question can't be answered, even if you understand it as 'What is the smallest known composite none of whose factors are known?' (I can easily generate an enormous number none of whose factors are known). But there is an ongoing effort at FERMATSEARCH to factorise the Fermat numbers F_m = 2^2^m + 1, which gives you an idea of the state of the art.

Currently (October 2009) the smallest known-composite factor of a Fermat number which has no known factors is the 1187-digit number C1187 given by

F_12 = 114689 · 26017793 · 63766529 · 190274191361 · 1256132134125569 · C1187

$\endgroup$
3
$\begingroup$

What you're asking is (or will be after a slight change of question) essentially a form of "what's the smallest number that cannot be written in words" paradox.

$\endgroup$
2
  • $\begingroup$ Not really - the question is asking for the smallest number whose primality status isn't currently known, not the smallest number whose primality status can't be known. At every time there is a smallest number whose primality status isn't currently known, and we could even have a centralized computer that kept track of what that number was if we wanted. There's no paradox. $\endgroup$ Oct 21, 2009 at 5:37
  • 4
    $\begingroup$ I agree with Ilya -- given current processing power, this feels something like asking "What's the smallest number that has never been written down on the Internet?" $\endgroup$
    – Tom Church
    Oct 21, 2009 at 6:49
2
$\begingroup$

Back in 1990, whatever answer would have been given to the question would likely correspond to the processing power of single (possibly large) computer. Today, the best algorithms are ones that can be efficiently distributed, leading to successful factorizations performed by networks of computers.

With the General Number Field Sieve, one can expect to factor a 200-(decimal)-digit integer in several months of computer time. See here for some records.

Primality testing - even with certificates - extends to much higher numbers, and I'm not sure what the current state of the art is. Integers of special form (Mersenne primes and similarly constructed numbers, mostly) were tested up to 2^millions or so, but I'm not sure how high you can push the tests for general integers.

$\endgroup$

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