Refined Analysis and Improvements on Some Factoring Algorithms
Abstract
By combining the principles of known factoring algorithms we obtain some improved algorithms which by heuristic arguments all have a time bound O(exp sq. root of (cln n ln ln n) for various constants c greater than or equal to 3. In particular, Miller's method of solving index equations and Shanks method of computing ambiguous quadratic forms with determinant -n can be modified in this way. We show how to speed up the factorization of n by using preprocessed lists of those numbers in (-u, u) and (n - u, n + u), 0 < < u < < n which only have small prime factors. These lists can be uniformly used for the factorization of all numbers in (n - u, n + u). Given these lists, factorization tasks O(exp(2(ln n)(to the 1/3 power)(ln ln n) to the 2/3 power)) steps. We slightly improve Dixon's rigorous analysis of his Monte Carlo factoring algorithm. We prove that this algorithm with probability 1/2 detects a proper factor of every composite n within O(exp sq. root of (6ln n ln ln n) steps. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1980
- Accession Number
- ADA096348
Entities
People
- C. P. Schnorr
Organizations
- Stanford University