(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 x is a product of two prime numbers, \phi is a polynomial in just one variable, and \gcd refers to the greatest-common-divisor algorithm expounded by Euclid around 300 B.C. …

\star Repeat until exit:

\star\ a := a random number in 1,\dots, x-1;

\star\ b := \phi(a)\ mod(x);

\star if (\gcd(b,x) > 1) then exit.

Exiting enables carrying out the two prime factors of x

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

Note that we cannot consider the events b \equiv 0\ mod(p) and b \equiv 0\ mod(q) to be independent, even though p and q are prime, because b = \phi(a) and \phi may introduce bias.”

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

“… we cannot consider the events b \equiv 0\ mod(p) and b \equiv 0\ mod(q) 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 n>i>1 and i \geq 0, where i>u \geq 0, that:

n+u \equiv\ 0\ (mod\ i)?

(b) What is the compound probability for any given n>i,\ j>1, where i \neq j, i>u \geq 0, and j>v \geq 0, that:

n+u \equiv\ 0\ (mod\ i), and n+v \equiv\ 0\ (mod\ j)?

(c) What is the compound probability for any given n>i,\ j>1, where i \neq j, i>u \geq 0, and j>v \geq 0, that:

i divides n+u, and j divides n+v?

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 i-sided cylindrical die will yield the value u is \frac{1}{i} by the probability model for such an event as definable over the probability space (0, 1, 2, \ldots, i-1);

(b) The answer to query (1b) above is that the probability the simultaneous roll of one i-sided cylindrical die and one j-sided cylindrical die will yield the values u and v, respectively, is \frac{1}{i.j} by the probability model for such a simultaneous event as defined over the probability space \{(u, v): i > u \geq 0, j > v \geq 0\}.

(3) We trivially conclude that:

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

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

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

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

For instance, let j=2i. The probability that an i-sided cylindrical die will then yield 0—and allow us to conclude that i divides n—is \frac{1}{i}, and the probability that a j-sided cylindrical die will then yield 0—and allow us to conclude that j divides n—is \frac{1}{j}; but the probability of determining both that i divides n, and that j divides n, from a simultaneous roll of the two cylindrical dice is \frac{1}{j}, and not \frac{1}{i.j}.

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Advertisements