Trial division is the most laborious but easiest to understand of the integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
A graphing calculator typically refers to a class of handheld calculators that are capable of plotting graphs, solving simultaneous equations, and performing numerous other tasks with variables...
.
Basic idea
Trial division tests to see if an integer n, the integer to be factored, can be divided by any integer greater than one but less than n.
Method
Given an integer n (throughout this article, n refers to "the integer to be factored"), trial division consists of testing whether n is divisible by any number. Clearly, it is only worthwhile to test candidate factors less than n, and in order from two upwards because an arbitrary n is more likely to be divisible by two than by three, and so on. With this ordering, there is no point in testing for divisibility by four if the number has already been determined not divisible by two, and so on for three and any multiple of three, etc. Therefore, effort can be reduced by selecting only prime numbers
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
as candidate factors. Furthermore, the trial factors need go no further than because, if n is divisible by some number p, then n = p×q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.
A definite bound on the prime factors is possible. Suppose P(i) is the ith prime, so that P(1) = 2, P(2) = 3, P(3) = 5, etc. Then the last prime number worth testing as a possible factor of n is P(i) where P(i + 1)2 > n; equality here would mean that P(i + 1) is a factor. Thus, testing with 2, 3, and 5 suffices up to n = 48 not just 25 because the square of the next prime is 49, and below n = 25 just 2 and 3 are sufficient. Should the square root of n be integral, then it is a factor and n is a perfect square
Square number
In mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
.
An example of the trial division algorithm, using a prime sieve for prime number generation, is as follows (in Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
):
def trial_division(n):
"""Return a list of the prime factors for a natural number."""
if n
0:
prime_factors.append(p)
n //= p
if n > 1: prime_factors.append(n)
return prime_factors
Trial division is guaranteed to find a factor of n if there is one, since it checks all possible prime factors of n. Thus, if the algorithm finds one factor, n, it is proof that n is a prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
. Another way of saying this, which is more advantageous computationally, is that if any prime whose square does not exceed n divides it without a remainder, then n is not prime.
Worst Case is the 3rd book in the Michael Bennett series from James Patterson and Michael Ledwidge.-Plot summary:NYPD Detective Mike Bennett and his new partner FBI Special Agent Emily Parker are on the trail of Francis Mooney, a Manhattan trusts and estates lawyer with terminal lung cancer...
, 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
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
) 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
Arbitrary-precision arithmetic
In computer science, arbitrary-precision arithmetic indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most ALU hardware, which typically...
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 would be required to exhaust all candidates. Which is about 10126 years.
However, for n with at least one small factor, trial division can be a quick way to find that small factor. It is worthwhile to note that for random n, 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.
because, if n is divisible by some number p, then n = p×q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.
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