Editing Trial division (section)

{{Short description|Integer factorization algorithm}}
{{About|the mathematical algorithm|the judicial chamber of the International Criminal Court|Judges of the International Criminal Court}}
{{citations|date=March 2014}}
'''Trial division''' is the most laborious but easiest to understand of the [[integer factorization]] algorithms.  The essential idea behind trial division tests to see if an integer {{mvar|n}}, the integer to be factored, can be divided by each number in turn that is less than or equal to the [[square root]] of {{mvar|n}}. 

For example, to find the prime factors of {{math|1=''n'' = 70}}, one can try to divide {{math|70}} by successive primes: first, {{math|1=70 / 2 = 35}}; next, neither {{math|2}} nor {{math|3}} evenly divides {{math|35}}; finally, {{math|1=35 / 5 = 7}}, and {{math|7}} is itself prime. So {{math|1=70 = 2 × 5 × 7}}.

Trial division was first described by [[Fibonacci]] in his book ''[[Liber Abaci]]'' (1202).<ref>{{cite journal |last=Mollin |first=Richard A. |year=2002 |title=A brief history of factoring and primality testing B. C. (before computers) |journal=Mathematics Magazine |doi=10.2307/3219180 |jstor=3219180 |mr=2107288 |volume=75 |issue=1 |pages=18–29}}</ref>