2025-10-07 –, Krakow/ Business Value & Enterprise Adoption
This talk presents implementations that match and, where possible, exceed current quantum factorisation records using a VIC-20 8-bit home computer from 1981, an abacus, and a dog. We hope that this work will inspire future efforts to match any further quantum factorisation records, should they arise.
Quantum factorisation has the potential to fatally weaken current public-key algorithms, mainly through an algorithm called Shor's algorithm, provided that suitably large quantum computers can be engineered. In recent years, a number of authors have claimed records in quantum factorisation, sometimes with, sometimes without using Shor's algorithm. We review the history of factorisations with Shor's algorithm and point out that the largest number factorised with that algorithm is 21, a record which has stood since 2012, thirteen years ago. We analyse some of the recently publicised factorisation records and find that they invariably use what we call "sleight-of-hand numbers", which are numbers that are specially constructed so as to be easy to factorise on current physics experiments (calling them quantum computers really doesn't do them justice). We can replicate these records with a VIC-20 home computer from 1981 (6502 assembler code publicly available). These factorisations can even be done with just an abacus, given a large enough abacus. And since in many cases, one of the prime factors in use is 3, we even show how to factorise these numbers with a dog, trained to bark three times. We suggest evaluation criteria to prevent the publication of more quantum factorisation records that can be matched with canine technology.
Stephan has been working in security since 1993, when he was loosely associated with the team that developed PGP 2.0. Until about ten years ago, he was interested in any and all facets of security, but the field has both broadened and deepened, so he sadly concedes that he can no longer keep up with everything. So he is now focusing on IoT security and on poking holes in security fashion statements.