Trial Division - Speed

Speed

In the worst case, trial division is a laborious algorithm. If it starts from two and works up to the square root of n, the algorithm requires

trial divisions, where denotes the prime-counting function, the number of primes less than x. This does not take into account the overhead of primality testing to obtain the prime numbers as candidate factors. A useful table need not be large: P(3512) = 32749, the last prime that fits into a sixteen-bit signed integer and P(6542) = 65521 for unsigned sixteen-bit integers. That would suffice to test primality for numbers up to 655372 = 4,295,098,369. Preparing such a table (usually via the Sieve of Eratosthenes) would only be worthwhile if many numbers were to be tested. If instead a variant is used without primality testing, but simply dividing by every odd number less than the square root of n, prime or not, it can take up to about

trial divisions, which for large n is worse.

Even so, this is a quite satisfactory method. Difficulty arises only when large numbers are being considered. Typical talk is not of n but of the number of bits in n, such as 1024. Thus, n is a number around 21024 which is about 10308 so that factors up to about 10154 would have to be tested, and even if only prime numbers were to be considered as factors, there are about 10151 candidates. Further, because such large numbers far exceed the integer sizes of typical computers, arbitrary precision arithmetic techniques are required, at an enormous cost in time for each trial division. Thus in public key cryptography, values for n, chosen to have large prime factors of similar size, cannot be factored by any publicly known method in a useful time period on any available computer system or collective. Suppose that 1010 computers could be set to the task (more than one per person on the entire globe), and that each could perform 1010 trial divisions a second (well beyond current abilities); the collective could eliminate 1020 factors a second. Then only 10134 seconds (about 10126 years) would be required to exhaust all candidates.

However, for n with at least one small factor, trial division can be a quick way to find that small factor. For n chosen uniformly at random from integers of a given length, there is a 50% chance that 2 is a factor of n, and a 33% chance that 3 is a factor, and so on. It can be shown that 88% of all positive integers have a factor under 100, and that 92% have a factor under 1000. Thus, when confronted by an arbitrary large n, it is worthwhile to check for divisibility by the small primes. With a binary (or decimal) representation, it should be immediately apparent whether the number is divisble by two, for example.

For most significant factoring concerns, however, other algorithms are more efficient and therefore feasible.