Is precomputation of the prime-factor-decomposition feasible?

97 Views Asked by At

It is well-known that the prime-factor-decompositions (PFDs) of the positive integers are useful in a range of mathematical problems. There are a number of algorithms to compute these decompositions for a specific integer. Since this query is so ubiquitous in mathematics and computing, I have always wondered whether it would be feasible to precompute a large repository of the prime-factor-decompositions for all integers $n = 1,...,N$ up to some large number $N$, to allow the prime-factor-decompositions to be obtained via a simple "lookup" query, rather than being computed during run-time.

In theory, such a thing could be done by some large company/institution, which could then allow public queries of its repository. That is, you send through a list of integers no greater than $N$ and they send back the PFDs for those integers, in some appropriate syntax. In computing terms, the runtime computation of the PFD would be replaced by a lookup query to an external repository. The time taken would consist of sending the query, processing and lookup by the PFD repository, and receiving the answer. If this time is smaller than the time needed to compute the PFD by an efficient algorithm, then there would be a speed advantage. I'm just not sure whether this is something that would actually be feasible in practice.


Questions: Assuming this were done by some large company/research institution (i.e., with plenty of money and storage space), would it be feasible to precompute the prime-factor-decomposition for all integers up to some reasonably large number $N$, such that lookup queries to this institution would be faster than runtime computation? Roughly speaking, how big would $N$ need to be to get a computing advantage, and how big a value of $N$ would be feasible?

1

There are 1 best solutions below

4
On

The problem is storage space. The total amount of harddrives ever produced by humanity can store around $10^{21}$ numbers.* But twenty-one-digit numbers are easy to factorise. So we could never store enough factorisations to make this plan worthwhile.

*For citation see here: https://www.zdnet.com/article/what-is-the-worlds-data-storage-capacity/ That's an old article, but it doesn't really matter. Thirty-digit numbers are also easy to factorise.