Lehmer Factor Stencils: A paper factoring machine before computers

In 1929, Derrick N. Lehmer published a set of paper stencils used to factor large numbers by hand before the advent of computers. We explain the math behind the stencils, which includes modular arithmetic, quadratic residues, and continued fractions, including my favourite mathematical visualization for continued fractions.

*VIDEO CORRECTION*: I made a copying error when setting up the recurrences and doing out the computations (so some intermediate values are incorrect). I'm so sorry about this! See the PDF User's Guide below for full details and correction of this issue.

DO IT YOURSELF!
PDF user's guide: https://math.colorado.edu/~kstange/st...
Accompanying Python & SVG files to make your own: https://github.com/katestange/lehmerf...

Original stencils:
Derrick N. Lehmer, Factor Stencils, Washington, DC: Carnegie Institution of Washington, 1929.
Worldcat link:
https://www.worldcat.org/title/factor...
Smithsonian Link: https://americanhistory.si.edu/collec...

Updated on Hollerith cards:
D. N. Lehmer, Factor Stencils, rev. John D. Elder, Washington, D.C.: Carnegie Institution of Washington, 1939.
Worldcat Link: https://www.worldcat.org/title/factor...
Smithsonian Link: https://americanhistory.si.edu/collec...

Lehmer's essay on his factoring machine that I quote from in the video:
D. N. Lehmer, Hunting Big Game in the Theory of Numbers, Scripta Mathematica, September, 1932.
http://ed-thelen.org/comp-hist/Lehmer...

A great video about homemade factor stencils by Chris Staecker:
   • Factor Stencils Review / HowTo  

Videos on modular arithmetic, done visually:
   • Modular Arithmetic Visually  

*Chapters*:
00:00 intro
00:50 demo of the stencils
02:27 history
04:11 overview
04:34 difficulty of factoring
09:14 relationship to cryptography
09:50 Lehmer quote
11:40 sieving for primes
12:04 quadratic residues and modular arithmetic
14:23 sieving for primes with quadratic residues
15:37 how many stencils are needed
16:47 recurrence relations and how to find quadratic residues
17:29 geoboard demo and rubber band points
20:31 Farey subdivision
22:55 Continued fractions
24:45 summary and runtime

*Thanks to*:
Glen Whitney, of MOMATH, for help with paper cutter
3blue1brown and LeiosOS, for motivation (Summer of Math Exposition, SoME1 https://www.3blue1brown.com/blog/some1)
Edmund Harriss and Steve Trettel, for collaboration on some lattice images
Jonathan Wise, as always

Image credits:
Lehmer on piano – Konrad Jacobs – CC-BY-SA 2.0 DE
https://commons.wikimedia.org/wiki/Fi...
Lehmer’s machines – Marcin Whichery – CC-BY 3.0 https://commons.wikimedia.org/wiki/Fi...
RSA keyfob – Alexander Klink – CC-BY 3.0
https://commons.wikimedia.org/wiki/Fi...
Farey subdivision – collaboration with Edmund Harriss
and Steve Trettel

If you like, subscribe and comment, it does encourage me :)

Personal notes: This was my first real YouTube video project. I learned a lot of lessons, including that my voice is different on different days even with the same microphone setup! It was a fun adventure. I'm not going to be the next big YouTube star, but your comments and feedback make it feel worth the time and energy! #SummerOfMathExposition #SoME1 #3b1b

Licensed under CC BY-SA 4.0