Direct Search Factorization
المؤلف:
المرجع الالكتروني للمعلوماتيه
المصدر:
www.almerja.com
الجزء والصفحة:
...
12-9-2020
1082
Direct Search Factorization
Direct search factorization is the simplest (and most simple-minded) prime factorization algorithm. It consists of searching for factors of a number by systematically performing trial divisions, usually using a sequence of increasing numbers. Multiples of small primes are commonly excluded to reduce the number of trial divisors, but just including them is sometimes faster than the time required to exclude them. Direct search factorization is very inefficient, and can be used only with fairly small numbers.
When using this method on a number 
, only divisors up to 
(where 
is the floor function) need to be tested. This is true since if all integers less than this had been tried, then
 |
(1)
|
In other words, all possible factors have had their cofactors already tested. It is also true that, when the smallest prime factor 
of 
is ![>RadicalBox[n, 3]](https://mathworld.wolfram.com/images/equations/DirectSearchFactorization/Inline6.gif)
, then its cofactor 
(such that 
) must be prime. To prove this, suppose that the smallest 
is ![>RadicalBox[n, 3]](https://mathworld.wolfram.com/images/equations/DirectSearchFactorization/Inline10.gif)
. If 
, then the smallest value 
and 
could assume is 
. But then
 |
(2)
|
which cannot be true. Therefore, 
must be prime, so
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
