In one of the most hilarious papers we have read this year, two scientists challenged some famous quantum factorization records, pointing out how these approaches are only possible using very specific numbers or by changing the problem into an altogether easier-to-solve one. The team calls it sleight of hand, and are calling it out using old computers, an abacus, and even a dog!
You most likely learned factorization in elementary school. You take a number and, using some known rules and some trial and error, you can work out its prime factors: the prime numbers you can multiple together to get the original number. Let’s have an example.
If I were to ask you the factors of the number 30, you would immediately know that one has to be 2, because 30 is even. To find the next factors, we would divide 30 by 2, which gives us 15. The number 15 is not prime, so we need to do the process again. There are multiple ways to find another factor. We know that numbers that end in 5 and 0 are divisible by 5. So that’s our next factor, and we are left with the number 3. The bigger the number, the more complicated and longer the process gets. Even for the most powerful computers.
Factorization is incredibly important in cryptology, the science of secure communication. The authors, Peter Gutmann and Stephan Neuhaus, are experts in the field. An encryption algorithm, for example, uses large prime numbers multiplied together to create public key components, given how difficult it is to solve such a problem.
Quantum computers have the potential to be exponentially faster at solving such problems than regular computers. But so far, that potential has not borne fruit. Algorithms have factorized 15 and 21, but failed to factorize 35, for example.
There was also the factorization of a much larger number, the so-called RSA-2048 number; it has 617 decimal digits (which I will not write here), but the team points out there was sleight of hand there too. The number is the product of two consecutive primes, and it can be solved with a square root method. Take the example of the numbers 328 and 5,183. The square root of the first is 17.92, very close to 18, the number between its two factors, 17 and 19. The square root of the second one is 71.99. No stars for guessing that its two factors are 71 and 73.
Alfredo, we were promised a dog! I’m getting to it, do not worry! Knowing that the numbers selected for these tests are chosen for how well they can be solved, the team decided to point out that they can do the same in several ridiculous ways. First, they used a computer from 1981 and an algorithm from 1945 to do the same work. Even more impressive is that you can do the same with an abacus.
But the cherry on top is the use of one of the author’s dogs: Scribble. Scribble was employed in the factorization process by barking three times, being able to find the number of factors for both 15 and 21. Obviously, we had to try this ourselves.
Our canine computer, Llywelyn ‘Clue’ Orpheus Carpineti, is a lot more barky than the well-behaved Scibble. We picked the number 187 to be factorized and Clue delivered 11 barks, the correct number to factorize 187. The other factor is 17. One of the points that the team raises in the paper is that the factors should be unknown to the experimenter.
Due to the sheer number of barks necessary to solve the RSA-2048 number and given that “Scribble is very well behaved and almost never barks,” the authors did not attempt to factorize that number. But they point out algorithms that you can use to have barky dogs solve even enormous numbers without the need of a huge number of barks. It all comes down to picking the right number to factorize.
The moral of the story is that quantum computing is hard. The potential of this technology is incredible, but there are many major challenges to overcome before it will be at a useful level.
The study is available via the Cryptology ePrint Archive.
Source Link: Dog Named Scribble Replicates Quantum Factorization Records – So We Tried It Too
