一种快速分解大整数的小因子的优化分解树OFT算法

分解大整数的小因子是解决IFP，DLP问题的诸多攻击方法中的重要运算模块．本文在目前分解大整数小因子算法的基础上，提出的优化分解树(Optimized Factorization Tree)算法，利用树型数据结构和相应的构造算法与回溯算法，配合以作者提出的分解表截支方法和优化分组策略，可以将分解大整数小因子的速度提高50％以上．该算法还可以为大整数素性判别做高效过滤，快速识别大部分合数．

A Fast Algorithm OFT to Factorize Small Factors of Big Integer

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.