uniformly distributed over the interval {1, . . . , M }, but instead of the usual

output format for such a number r, the output consists of the prime factor-

ization of r.

As far as anyone knows, there are no e¬cient algorithms for factoring large

7.7 Generating a random factored number 171

numbers, despite years of active research in search of such an algorithm.

So our algorithm to generate a random factored number will not work by

generating a random number and then factoring it.

Our algorithm will use Algorithm RS in §7.6 as a subroutine. In addi-

tion, as we did in §7.5, we shall assume the existence of a deterministic,

polynomial-time primality test IsPrime. We denote its running time on

—

input n by Wn , and set WM := max{Wn : n = 2, . . . , M }.

In the analysis of the algorithm, we shall make use of Mertens™ theorem,

which we proved in Chapter 5 (Theorem 5.13).

On input M ≥ 2, the algorithm to generate a random factored number

r ∈ {1, . . . , M } runs as follows:

Algorithm RFN:

repeat

Run Algorithm RS on input M , obtaining (n1 , . . . , nt )

(—) Let ni1 , . . . , ni be the primes among n1 , . . . , nt ,

including duplicates

Set r ← j=1 nij

(——)

If r ¤ M then

s ←R {1, . . . , M }

if s ¤ r then output ni1 , . . . , ni and halt

forever

Notes:

(—) For i = 1, . . . , t’1, the number ni is tested for primality

algorithm IsPrime.

(——) We assume that the product is computed by a simple

iterative procedure that halts as soon as the partial

product exceeds M . This ensures that the time spent

forming the product is always O(len(M )2 ), which sim-

pli¬es the analysis.

Let us now analyze the running time and output distribution of Algorithm

RFN on input M . Let k := len(M ).

To analyze this algorithm, let us ¬rst consider a single iteration of the

main loop as a random experiment in isolation. Let n = 1, . . . , M be a ¬xed

integer, and let us calculate the probability that the variable r takes the

particular value n in this loop iteration. Let n = p¤M pep be the prime

factorization of n. Then r takes the value n i¬ Ep = ep for all primes p ¤ M ,

172 Probabilistic algorithms

which by the analysis in §7.6, happens with probability precisely

U (M )

p’ep (1 ’ 1/p) = ,

n

p¤M

where

(1 ’ 1/p).

U (M ) :=

p¤M

Now, the probability that this loop iteration produces n as output is equal

to the probability that r takes the value n and s ¤ n, which is

U (M ) n U (M )

· = .

n M M

Thus, every n is equally likely, and summing over all n = 1, . . . , M , we

see that the probability that this loop iteration succeeds in producing some

output is U (M ).

Now consider the expected running time of this loop iteration. From the

—

analysis in §7.6, it is easy to see that this is O(kWM ). That completes the

analysis of a single loop iteration.

Finally, consider the behavior of Algorithm RFN as a whole. From our

analysis of an individual loop iteration, it is clear that the output distri-

bution of Algorithm RFN is as required, and if H denotes the number of

loop iterations of the algorithm, then E[H] = U (M )’1 , which by Mertens™

theorem is O(k). Since the expected running time of each individual loop

—

iteration is O(kWM ), it follows that the expected total running time is

—

O(k 2 WM ).

7.7.1 Using a probabilistic primality test (—)

Analogous to the discussion in §7.5.1, we can analyze the behavior of Algo-

rithm RFN under the assumption that IsPrime is a probabilistic algorithm

which may erroneously indicate that a composite number is prime with

probability bounded by . Here, we assume that Wn denotes the expected

—

running time of the primality test on input n, and set WM := max{Wn :

n = 2, . . . , M }.

The situation here is a bit more complicated than in the case of Algorithm

RP, since an erroneous output of the primality test in Algorithm RFN could

lead either to the algorithm halting prematurely (with a wrong output),

or to the algorithm being delayed (because an opportunity to halt may be

missed).

Let us ¬rst analyze in detail the behavior of a single iteration of the main

7.7 Generating a random factored number 173

loop of Algorithm RFN. Let A denote the event that the primality test

makes a mistake in this loop iteration, and let δ := P[A]. If T is the number

of loop iterations in a given run of Algorithm RS, it is easy to see that

δ ¤ E[T ] = (M ),

where

M ’1

1

¤ 2 + log M.

(M ) := 1 +

j

j=1

Now, let n = 1, . . . , M be a ¬xed integer, and let us calculate the probability

±n that the correct prime factorization of n is output in this loop iteration.

Let Bn be the event that the primes among the output of Algorithm RS

multiply out to n. Then ±n = P[Bn § A](n/M ). Moreover, because of

the mutual independence of the Ej , not only does it follow that P[Bn ] =

U (M )/n, but it also follows that Bn and A are independent events: to see

this, note that Bn is determined by the variables {Ej : j prime}, and A is

determined by the variables {Ej : j composite} and the random choices of

the primality test. Hence,

U (M )

(1 ’ δ).

±n =

M

Thus, every n is equally likely to be output. If C is the event that the

algorithm halts with some output (correct or not) in this loop iteration,

then

P[C] ≥ U (M )(1 ’ δ), (7.7)

and

P[C ∨ A] = U (M )(1 ’ δ) + δ = U (M ) ’ δU (M ) + δ ≥ U (M ). (7.8)

The expected running time of a single loop iteration of Algorithm RFN is

—

also easily seen to be O(kWM ). That completes the analysis of a single loop

iteration.

We next analyze the total running time of Algorithm RFN. If H is the

number of loop iterations of Algorithm RFN, it follows from (7.7) that

1

E[H] ¤ ,

U (M )(1 ’ δ)

and assuming that (M ) ¤ 1/2, it follows that the expected running time

—

of Algorithm RFN is O(k 2 WM ).

Finally, we analyze the statistical distance ∆ between the output distri-

bution of Algorithm RFN and the uniform distribution on the numbers 1

174 Probabilistic algorithms

to M , in correct factored form. Let H denote the ¬rst loop iteration i for

which the event C ∨ A occurs, meaning that the algorithm either halts or

the primality test makes a mistake. Then, by (7.8), H has a geometric

distribution with an associated success probability of at least U (M ). Let Ai

be the event that the primality makes a mistake for the ¬rst time in loop

iteration i, and let A— is the event that the primality test makes a mistake in