Integer Factorization, Determinism, and Time’s Arrow


A positive integer m greater than 1 has a representation as the product of powers of distinct prime numbers that is unique except for the order in the representation of m’s prime factors. One can establish uniqueness by requiring that the prime factors, regardless of their exponents, appear in ascending numerical order.

If m = ab for positive integers a, b both greater than 1, we can speak of the processes of multiplication and integer factorization, processes by which we can work out the product m given a and b, and produce a factorization ab given m. But even though we can speak of these processes, the best known fixed, deterministic, and immediate processes for factorization are nowhere nearly as compact or deterministic as “how to multiply two integers.”

What I am wondering today is just *how* difficult developing an integer factorization formula or method is, and whether it is as difficult as, say, reversing entropy, or becoming able to un-stir the cream from a cup of coffee, or to shake Thursday Next’s Entroposcope (hat-tip to author Jasper Fforde) so that the white and black beans separate neatly.

Lord, I hope not. But just as humanity does not yet know how simple and effective the next good formula for integer factorization will be, we also do not know whether or not we’ll come up with anything for factorization that is as straightforward, automatic, and deterministic as our processes for multiplication.

Knowledge is a truly interesting concept to try to trace forward – or backward – in time. Memory is different in nature from prediction, and with different limits and evidential bases (our objectively accurate prediction of the future is simply based on evidence – trends, etc. – from our past), they do share a distant commonality that they can both introduce inaccuracy and error in our thought processes.

Good thing we have computers and hard drives and language and writing and other storage mechanisms so that we in the present can look at a record of the past (not, at this time 😀 ) the future).

Leave a ReplyCancel reply