# Accession Number:

## ADA024416

# Title:

## Analysis of a Simple Factorization Algorithm

# Descriptive Note:

# Corporate Author:

## MASSACHUSETTS INST OF TECH CAMBRIDGE

# Personal Author(s):

# Report Date:

## 1976-01-01

# Pagination or Media Count:

## 51.0

# 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 Kx as n approaches infinity. Several interesting properties of F sub Kx 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.

# Descriptors:

# Subject Categories:

- Statistics and Probability