Factorization of Odd Integers with a Divisor of the Form 2au±12au±12^au \pm 1

摘要

The paper proves that an odd composite integer NNN can be factorized in at most O(0.125u(log2N)2)O(0.125u(log2N)2)O( 0.125u(log_2N)^2) searching steps if NNN has a divisor of the form 2au+12au+12^a{u} +1 or 2au−12au−12^a{u}-1 with a>1a>1a > 1 being a positive integer and u>1u>1u > 1 being an odd integer. Theorems and corollaries are proved with detail mathematical reasoning. Algorithms to factorize the kind of odd composite integers are designed and tested by factoring certain Fermat numbers. The results in the paper are helpful to factorize the related kind of odd integers as well as some big Fermat numbers