A tale of three machines

The Fundamental Theorem of Arithmetic tells us that any positive integer can be factored into a product of prime factors.¹ Given a positive integer $n$ , this leads naturally to several questions:

What is the prime factorization of $n$ ?

This is the most obvious question we could ask. The Fundamental Theorem tells us such a prime factorization must exist (and must be unique up to the order of the factors), so we can simply ask what it is. For example, if $n = 101500$ , then the answer would be $n = 2^2 \cdot 5^3 \cdot 7 \cdot 29$ . What we really want is some sort of machine (let’s call it a factorization machine) where we can put a positive integer in one end, the machine makes whirring, grinding, and beeping sounds for a while, and then a factorization pops out the other end:

import Machines

dia = machine $ Machine
  { machineW = 5
  , machineH = 2
  , label    = text "Z"
  , inputLabel    = text "101500"  strutX 3
  , outputLabel   = text "2×2×5×5×5×7×29"  strutX 6
  , machineColor  = lightblue
  }

Another question we could ask about $n$ would be:

What is one prime factor of $n$ ?

An answer to this question is a similar sort of machine, except instead of getting the entire prime factorization out, we just get one prime factor; let’s call this a factor machine. For example, it might work like this:

import Machines

dia = machine $ Machine
  { machineW = 5
  , machineH = 2
  , label    = text "F"
  , inputLabel    = text "101500"  strutX 3
  , outputLabel   = text "7"  strutX 1
  , machineColor  = lightblue
  }

These first two machines are very closely related. If we have a factorization machine we can easily use it to build a factor machine: just run $n$ through the factorization machine, pick one of the factors to return, and throw the rest away.

Slightly less obviously, we can also use a factor machine to build a factorization machine: run $n$ through the factor machine to get a prime factor $p_0$ . Now we can compute $n_1 = n/p_0$ (by definition, $p_0$ must evenly divide $n$ ); to get the rest of the factorization of $n$ we just need to factor $n_1$ . So we run $n_1$ through the factor machine to get a prime factor $p_1$ ; we compute $n_2 = n_1/p_1$ ; and so on. We are done when putting $n_i$ into the factor machine returns $n_i$ itself; that means $n_i = p_i$ is prime. Finally, we return the factorization $p_0 \cdot p_1 \cdot \dots \cdot p_i$ .

For example, if we run $101500$ through the factor machine and get $7$ , then we compute $101500/7 = 14500$ . Next we run $14500$ through the factor machine again and get, say, $5$ , and then compute the remaining part that needs to be factored, $14500/5 = 2900$ ; and so on.

Finally, here’s a third question we could ask:

Is $n$ prime?

In answer to this we could imagine another similar machine which outputs a simple yes/no answer. Let’s call this a primality machine:

import Machines

dia = machine $ Machine
  { machineW = 5
  , machineH = 2
  , label    = text "P ?"
  , inputLabel    = text "101500"  strutX 3
  , outputLabel   = text "NO"  strutX 1.5
  , machineColor  = lightblue
  }

Given a factor machine, we can easily use it to build a primality machine: take the input $n$ and run it through the factor machine. If the answer is $n$ , then $n$ is prime so output “YES”; otherwise, $n$ is not prime (since it is divisible by the output factor), so output “NO”.

But what about the converse? If we have a working primality machine, can we use it to build a factor machine? Given some $n$ , if the primality machine says YES then $n$ is prime, so the factor machine should output $n$ . But what if the primality machine says NO? On the face of it, the mere fact of knowing that $n$ is composite does not help us find a factor. But what is the primality machine doing on the inside? If it knows that $n$ is not prime, it must have figured out a way to factor $n$ , right? That is, somewhere in the internals of the machine, there must have been a factor that it simply isn’t telling us about:

import Machines

dia =
  mconcat
  [ text "7" # fc red
    # fontSizeL 0.5
    # translate (6 ^& (-0.5))
  , machine $ Machine
    { machineW = 5
    , machineH = 2
    , label    = text "P ?"
    , inputLabel    = text "101500"  strutX 3
    , outputLabel   = text "NO"  strutX 1.5
    , machineColor  = lightblue
    }
  ]

If this is true, it means we could rip open the guts of the primality machine and use it to build a factor machine. Or, put more simply, this would be saying that the only way to make a primality machine is to build it out of a factor machine. This seems intuitively reasonable: how could you know that $n$ is composite without factoring it?

The punchline is that this is not true!! That is,

It is possible to make working primality machines that truly do not know anything about any factors of $n$ .

Not only that, but we know how to make primality machines that run much faster than the fastest known factor machines!

Let that sink in for a minute. It is really quite surprising that we can find out whether $n$ has any prime divisors without actually finding out what they are, and that moreover it is much faster if you don’t care what the prime factors are. Think of it as a sort of “computational loophole” in our universe.

This is no mere curiosity; it turns out that this “loophole” is actually the basis of almost all of modern cryptography. When your browser makes an encrypted connection to a website in order to securely transmit your credit card information, it is relying on this loophole: your browser needs to pick some numbers and make sure that they are prime, which it can do quickly; but for anyone intercepting the messages to steal your credit card, they would have to factor another number, which (as far as we know) cannot be done quickly. (This is really cool and a topic for another post.)

It gets stranger, though: you may have noticed that I keep using phrases such as “fastest known”, “seems”, and “as far as we know”. It turns out that no one has been able to prove that making faster factor machines can’t be done! So it’s possible that the “loophole” isn’t a loophole at all; perhaps with a clever enough idea it will turn out to be possible to factor numbers just as fast as we can test whether they are prime. But most people don’t believe that.

In some upcoming posts I plan to talk a bit more about what we actually mean when we are talking about these machines being “fast” or “slow”, and then finally get around to explaining some different ways of building fast primality machines.

Possibly a product of no prime factors, which accounts for $1$ .↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

11 Responses to A tale of three machines

Naren Sundar says:

January 3, 2018 at 10:53 pm

Super!
Mr Kit says:

January 4, 2018 at 10:06 pm

This has always fascinated me and I wonder if there’s a way to incorporate this idea into the prime time unit about factors and multiples with my 6th graders to help them see that the idea of factors is actually a really big, important idea, rather than a meaningless skill from middle school…
- Brent says:
  
  January 5, 2018 at 10:24 am
  
  Which idea exactly are you referring to when you say “this idea”? Incorporating some of this in a 6th grade class indeed sounds like fun.
  - Mr Kit says:
    
    January 7, 2018 at 9:54 am
    
    Sorry, that was very unclear. I’ve always been fascinated by prime factorizations and the idea that we can know whether a number is prime or NOT without actually knowing the prime factorization. I find the cryptography applications fascinating, and I wonder if there’s a way to share with students in 6th grade the deeper applications of primes and prime factorization beyond just the numbers. We don’t even name the fundamental theorem of arithmetic, even though we essentially teach it – and I question why!
    - Brent says:
      
      January 7, 2018 at 10:05 am
      
      Ah, makes sense. I think it might be doable to teach 6th graders the basics of RSA, though I guess it might be hard to get them to understand why it works, and why its security depends on the supposed difficulty of factoring.
      
      One thing I have come to appreciate more through writing this series is how Fermat’s Little Theorem is a sort of gateway to all sorts of more interesting things. Once you understand FLT you can understand why RSA works as well as some of the more basic primality testing algorithms.
      - Mr Kit says:
        
        January 7, 2018 at 10:58 am
        
        Oh, I’ll not super familiar with Fermat’s little theorem, though I do know the basics of why RSA works. Can you say more about the connection & the role of FLT?
        
        Brent says:
        
        January 7, 2018 at 9:12 pm
        
        Well, FLT (or some generalization of it such as Euler’s Theorem or Carmichael’s Theorem) is used to prove that encryption and decryption work in RSA, i.e. $m^{ed} \equiv m$ . Perhaps this is a subject for another blog post.
Juan Valera (@juanvalera) says:

January 5, 2018 at 5:30 pm

>> we know how to make primality machines

I’m lost, what are you referring to? What algorithm is this?
- Brent says:
  
  January 5, 2018 at 8:23 pm
  
  Oh, don’t worry, I haven’t actually said what I’m referring to yet! When I said that “we” know how to make such primality machines I just meant “humans as a species”, not “we” as in “readers of my blog”. I’m going to explain some primality testing algorithms in future posts (that’s really what I’ve been building up to with this whole series).
leemck says:

January 7, 2018 at 3:06 am

I am enjoying your puzzle. How about a follow up article on the Fundamental Theorem. Are there alternate expressions of it, together with alternate kinds of example that may provide energy to other areas of inquiry?
One of the ways I am enjoying your puzzles is by taking note of the feelings and memories that are triggered. When I read ” this “loophole” is actually …” I laughed and I felt delight as your words began matching up with the puzzlement that had arisen a few sentences before.
___
I mention this because you are a teacher. I work with severely disabled kids and I have been exploring the proposition that some kinds of learning have something to do with a memory tree. The time delay in a laugh has something to do with the location and length of the branch of the memory tree and the processing time as a piece of current sensory data travels through the memory tree.

Best wishes and keep writing. Thank you.
Pingback: Fast and slow machines | The Math Less Traveled