| Trial Division |
Article Index for Trial |
Website Links For Trial |
Information AboutTrial Division |
| CATEGORIES ABOUT TRIAL DIVISION | |
| integer factorization algorithms | |
| primality tests | |
|
Given a Composite Integer ''n'' (throughout this article, ''n'' means "the integer to be factored"), trial division consists of trial-dividing ''n'' by every Prime Number less than or equal to . If a number is found which divides evenly into ''n'', a factor of ''n'' has been found. Trial division is guaranteed to find a factor of ''n'', since it checks all possible prime factors of ''n''. Thus, if the algorithm fails, it is proof that ''n'' is prime. In the Worst Case , trial division is a very inefficient algorithm. If it starts from 2 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 . If 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 takes : trial divisions. This means that for ''n'' with large prime factors of similar size (like those used in Public Key Cryptography ), trial division is computationally infeasible. 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 91% have a factor under 1000. For most significant factoring concerns, however, other Algorithm s are more efficient and therefore feasible. |
|
|