• The account by E. T. Bell, of Cole standing up and wordlessly carrying out a multiplication on the blackboard, ending with applause, is, in my opinion after considering all the facts available, almost certainly a "dramatization" by Bell.[1] However, I'm inclined to believe that Cole basically followed the structure of his paper[2], which does have a dramatic end and there would have been applause (even if his talk was not wordless). Also, the "three years of Sundays" seems about right.
• Unlike the implication of Bell's story, M_67 = 2^67 - 1 was already known to be composite by 1903, as Lucas[3] had already shown it (and Cole cites him in his paper). What was not known was a factorization, which is what Cole did.
• Cole's paper is very elliptically written and only focuses on his original contribution, but if you read it carefully for the factorization method, the true hero of this story IMO is Paul Peter Heinrich Seelhoff (1829–1896). This Seelhoff (does not have an article on Wikipedia, even on the German one) was a high-school teacher in Mannheim, and he wrote some papers that have many great ideas but are also full of computation errors. No one seems to have paid his work much attention before Cole (his name shows up in only very few histories of mathematics / number theory from that period).
• Seelhoff's method, which Cole used, is basically what we now call the Quadratic Sieve[4], “still the fastest for integers under 100 decimal digits or so”. It's amazing how many modern algorithmic ideas Seelhoff anticipated, even things like optimization tweaks and when to stop. (After Cole only Kraitchik seems to have read Seelhoff closely, and it's via Kraitchik that the modern methods like CFRAC and quadratic sieve came to be, after the advent of computers.)
• The idea at heart is a generalization of Fermat's factorization method, and goes back to Lagrange (and Gauss): to factor N, if you can find a solution to x^2 ≡ y^2 (mod N), where x ≢ ±y (mod N), then you're done, because N divides (x-y)(x+y) and taking gcd(N, x-y) and/or gcd(N, x+y) will give a nontrivial factor.
• If you have some magical method that tends to give small quadratic residues mod N, that will help, in two ways: the very fact that (say) 7 is a quadratic residue mod N (and therefore mod its residues) will impose some condition (by quadratic reciprocity) on the prime factors of N, which will knock out half the possible values. So with k quadratic residues you need to try only 1/2^k of the primes. The second way it helps (due to Seelhoff) is that your method may end up giving you two ways the same quadratic residue can be achieved, i.e. a nontrivial solution to x^2 ≡ y^2 (mod N).
• The idea of the quadratic sieve (and Seelhoff's innovation) is to find such residues by doing the following: first, try to find "smooth" residues mod N, by looking for conditions on x to make a=x^2-N be divisible by several chosen small primes. Then, whichever of these these residues you can fully factorize, write it as (basically) a bit vector of the primes that divide it. Keep track of these bit vectors (write them down as rows one below the other, say) and do row reduction: the moment you get a "cycle" (nontrivial linear relation), you're likely done, as you have x^2 = y^2 (mod N).
• Cole did come up with an idea or two of his own, which cut the search space down (in the third phase) by a factor of 4 (instead of 2) for each residue: thus, estimating that it was doable, he had the persistence to carry out this project of hand calculation. But the bulk of this calculation was finding quadratic residues and using the resulting congruence conditions, not trial division.
I'll stop here as I have the sense this comment has become super long, but you can get a good idea of all this in Factoring Integers Before Computers (1994) by H. C. Williams and J. O. Shallit (cited in the page below).
———
[0]: https://shreevatsa.github.io/site/cole.html [see my comments on https://mathoverflow.net/a/207354 — 2016, 2019, 2021 :P])
[1]: I reach this conclusion from a careful reading of E. T. Bell's biography by Constance Reid, which BTW is an amazing book. The first part of it reads like a detective story (her own work unearthing details about Bell). Also, at one point there's a cameo appearance by Arthur C. Clarke, as a fellow science-fiction writer (E. T. Bell wrote some SF novels as John Taine) who happened to live in Sri Lanka. BTW Bell was almost certainly not present at that New York meeting of the AMS where Cole read his paper. Also, Cole was likely Bell's PhD advisor later (surprising we can't be sure of advisor-advisee relationships this late).
[2]: http://projecteuclid.org/euclid.bams/1183417760 -> https://projecteuclid.org/journalArticle/Download?urlId=bams...
[3]: Lucas is another hero; you can read H. C. Williams's book about him. He wrote papers on agriculture etc and randomly turned to math and did an amazing amount of work (on factoring etc — and it was he who made Fibonacci numbers a worthy object of study and gave them that name) in just a few short years, before abruptly abandoning math completely after someone gave a bad review to one of his papers.