(*Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.*)

**A: A conventional perspective on why the prime divisors of an integer are not mutually independent**

In a post *Getting to the Roots of Factoring* on the blog *Gödel’s Lost Letter and P = NP* (hosted jointly by him and Professor of Computer Science at Georgia Tech College of Computing, *Richard Lipton*) Professor of Computer Science and Engineering at the University of Buffalo, *Kenneth W. Regan* `revisits’ a 1994 paper on factoring by his co-host.

What I find intriguing in the above post is that the following extract subsumes, almost incidentally, a possibly implicit belief which may be inhibiting not only a resolution of the computational complexity of Integer Factoring (see *this investigation*) by conventional methods but, for similar reasons, also resolution of a large class of apparently unrelated problems (see, for instance, *this investigation* and *this previous post*):

“Here is the code of the algorithm. … the input is a product of two prime numbers, is a polynomial in just one variable, and refers to the greatest-common-divisor algorithm expounded by Euclid around 300 B.C. …

Repeat until exit:

a random number in ;

;

if then exit.

Exiting enables carrying out the two prime factors of …

How many iterations must one expect to make through this maze before exit? How and when can the choice of the polynomial speed up the exploration? …

Note that we cannot consider the events and to be independent, even though and are prime, because and may introduce bias.”

The following reasoning shows why it is not obvious whether the assertion that:

“… we cannot consider the events and to be independent”

is intended to narrowly reflect a putative proof in the particular context of the assertion, or to echo a more general belief.

**B: Defining the probability that a given integer is divisible by a given smaller integer**

(1) We consider the questions:

(a) What is the probability for any given and , where , that:

?

(b) What is the compound probability for any given , where , , and , that:

, and ?

(c) What is the compound probability for any given , where , , and , that:

divides , and divides ?

**C: Why the prime divisors of an integer are mutually independent**

(2) We note that:

(a) The answer to query (1a) above is that the probability the roll of an -sided cylindrical die will yield the value is by the probability model for such an event as definable over the probability space ;

(b) The answer to query (1b) above is that the probability the simultaneous roll of one -sided cylindrical die and one -sided cylindrical die will yield the values and , respectively, is by the probability model for such a simultaneous event as defined over the probability space .

(3) We trivially conclude that:

The compound probability of determining and correctly from the simultaneous roll of one -sided cylindrical die and one -sided cylindrical die, is the product of the probability of determining correctly from the roll of an -sided cylindrical die, and the probability of determining correctly from the roll of a -sided cylindrical die.

(4) We further conclude non-trivially that the answer to query (1c) above is given by:

(a) If and are co-prime, the compound probability of correctly determining that divides and divides from the simultaneous roll of one -sided cylindrical die and one -sided cylindrical die, is the product of the probability of correctly determining that divides from the roll of an -sided cylindrical die, and the probability of correctly determining that divides from the roll of a -sided cylindrical die.

(b) The assumption that and be co-prime is also necessary, since 4(a) would not always be the case if and were not co-prime.

For instance, let . The probability that an -sided cylindrical die will then yield —and allow us to conclude that divides —is , and the probability that a -sided cylindrical die will then yield —and allow us to conclude that divides —is ; but the probability of determining both that divides , and that divides , from a simultaneous roll of the two cylindrical dice is , and not .

(5) We thus conclude non-trivially that, if and are two unequal primes, the probability of determining whether divides is independent of the probability of determining whether divides .

## Leave a comment

Comments feed for this article