Analysis of a Simple Factorization Algorithm

Abstract

The probability that the k-th largest prime factor of a number n is at most n to the (x) power is shown to approach a limit F sub K(x) as n approaches infinity. Several interesting properties of F sub K(x) are explored, and numerical tables are given. These results are applied to the analysis of an algorithm commonly used to find all prime factors of a given number. The average number of digits in the k-th largest prime factor of a random m-digit number is shown to be asymptotically equivalent to the average length of the k-th longest cycle in a permutation on m objects.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1976
Accession Number
ADA024416

Entities

People

  • Donald Knuth
  • Luis Trabb Pardo

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Asymptotic Series
  • Difference Equations
  • Differential Equations
  • Distribution Functions
  • Equations
  • Integrals
  • Military Research
  • Normal Distribution
  • Number Theory
  • Numbers
  • Permutations
  • Prime Numbers
  • Probability
  • Probability Distributions
  • Random Variables
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Linear Algebra
  • Mathematics or Statistics