A Fast Algorithm OFT to Factorize Small Factors of Big Integer
Jing Cui · Chinese Journal of Computers · 2003
This paper proposes a new algorithm OFT(Optimized Factorization Tree) based on GCD method to factorize small factors more quickly. OFT replaces the gcd operation in GCD method by modular operation, and constructs a 2-branch tree by modular multiplication on these remainders, then computes the gcd of the product of all prime numbers in each branches and the target big integer with much fewer cost (about 1/9 of normal gcd operation) from the root to the leaves in recursion. OFT algorithm usually (above 95 percent) finds out all of the target's small factors without visiting all the nodes of the tree in the backtrace process, because the process is often shortened by two methods: FT(Factor Table) and OGD(Optimized Group Division), which are proposed in this research. FT cuts off most branches of the tree in backtrace process, and OGD makes the condition to be true earlier that the FT method must have to be applied. Only one gcd operation is needed for each 2-branch in the backtrace process. This article also provides the full proof of the correctness of OFT. The testing results between OFT algorithm, GCD method and Trial Division show that OFT algorithm is faster than GCD method by 50%. At the same time, OFT can be applied to aid primitive judgement, and speedly identify most of random composite numbers. It's very useful to speed up prime finding in realtime application environments.