156 points by paulpauper 11 days ago | hide | past | favorite | 31 comments

 Fascinating stuff! How was it demonstrated that 2^67 - 1 was composite without providing a factorization?
 svat 11 days ago The brilliance of Édouard Lucas: see "Lucas primality test" (for general N, when you can factor N-1) and "Lucas–Lehmer primality test" (for Mersenne numbers N). Both work for M_67. There's a nice account somewhere of how Lucas carried out the latter test with a 127x127 chessboard to prove that M_127 is prime. For M_67, Lucas had done the calculations and declared it composite, and there was confirmation from another author. And Cole seems to have trusted this too. (I mention this because Shallit and Williams point out that on some occasions Lucas seems to have wavered in his confidence, for some reason….)
 > "Lucas–Lehmer primality test"Familiar to overclockers because that's what many use for stability testing of CPUs!
 throwaway81523 11 days ago A Fermat test with base 3 shows the number to be composite. I think that could be done in a day or so of hand calculation. That amounts to a brute force method and as svat says, there are better ways. The Fermat test only shows that it can be done without much subtlety.
 bo1024 11 days ago This is fantastic. You could add it to the MO site as an additional answer?
 svat 11 days ago I've already left it as a comment (actually, three comments!) on the OP's MathOverflow (self-)answer. I'd like to be a little more sure that I've understood everything perfectly (e.g. implement the algorithm myself), and put it in a more coherent form, before posting as an answer on MathOverflow. :-)
 Being sure you give a correct & coherent answer is important. You mention "as it's unlikely I'll write that post anyway", so I'd just hate if perfect were the enemy of the good and the answer was never written.Maybe write it now and revise it as your understanding grows? Also, posting it now might encourage others to evaluate it for you, doing the work you may never get to.Just a suggestion. Thanks for your deep dive into this and writing it up in the HN comment! Very insightful.
 helf 11 days ago Posts like this are why I love HN. Thank you for the interesting read!
 Times are so crazily different. I tried what a really bad algorithm would take in CommonLisp. It is seconds it took.`````` (defun find-factor-aux(n div stop) (cond ((= 0 (rem n div)) div) ((> div stop) nil) (t (find-factor-aux n (+ 2 div) stop)))) (defun find-factor(n) (find-factor-aux n 3 (floor (sqrt n)))) (compile 'find-factor-aux ) ; need tail recursion to avoid stack overflow (find-factor (1- (expt 2 67))) ; this takes just a few seconds on my laptop ; 193707721 (find-factor (/ (1- (expt 2 67)) 193707721)) ; check for more ; nil (/ (1- (expt 2 67)) 193707721) ; get second factor ; 761838257287 (* 193707721 761838257287) ; check result ; 147573952589676412927 (1- (expt 2 67)) ; 147573952589676412927``````
 This is mentioned in one of the William Dunham books, how Cole was presenting at a conference and silently multiplied two by itself 67 times, subtracted one, and then multiplied the two factors he'd found and got the same number. And apparently received a standing ovation. Until then, it was not known whether it was prime (it's of the form 2^p-1 with p prime which iirc are potential Mersenne primes)
 Yeah this story originates from E. T. Bell, who I'm now fairly convinced just… made it up. (Possibly based on a kernel of truth about the conference presentation involving a lot of calculation, and ending in applause.) He is known for doing that sort of thing.(And Mersenne's list was already known to be inaccurate because of missing M_61 which is prime, and this number M_67 had been independently declared composite by Fauqembergue in 1894 and by Lucas, so was already believed to be composite.)
 E. T. Bell also has an amusing story about Condorcet. Condorcet was a French aristocrat and during the Revolution had to disguise himself as a commoner to escape France. However, when he was stopping at an inn, the innkeeper asked him how many eggs he would like in his omelette. An an aristocrat, he had no idea how many eggs went into an omelette so he said a dozen, thereby outing himself and ending up in prison.But as far as I can tell, Bell just made that story up, too.
 svat 11 days ago Great story, thank you :) This one seems to precede Bell's writing, though: it's mentioned in the 1911 Britannica biography https://en.wikisource.org/wiki/1911_Encyclop%C3%A6dia_Britan... and this 1905 book: https://www.gutenberg.org/files/24492/24492-h/24492-h.htm so it may be older.
 eesmith 11 days ago The 1902 Britannica as well - https://archive.org/details/encyclopaediabri06kell/page/254/... .Also, October 29, 1896 "The Youth's Companion" p 583 at https://archive.org/details/sim_youths-companion_1896-10-29_... . The details have changed a bit from the Britannica story.That in turn cites Edith Lichel's 1895 "The Story of Two Salons." https://archive.org/details/storytwosalons00sichgoog/page/n1... , which does not give further citations.The Britannica biography says 'On the evening of the 7th April 1794 — not, as Carlyle says, on a " bleared May morning,"'. Using Carlyle" and "bleared May morning" as search terms finds it comes from "The French Revolution" by Thomas Carlyle, first published in 1837.However, while that does describe the story of how Condorcet was identified, it does not mention omelettes or eggs only "asks breakfast". Quoting https://archive.org/details/frenchrevolutio16carlgoog/page/n...> Condorcet has lurked deep, these many months; Argus-eyes watching and searching for him. His concealment is become dangerous to others and himself; he has to fly again, to skulk, round Paris, in thickets and stone-quarries. And so at the Village of Clamars, one bleared May morning, there enters a Figure, ragged, rough-bearded, hunger-stricken; asks breakfast in the tavern there. Suspect, by the look of him! "Servant out of place, sayest thou?" Committee-President of Forty-Sous finds a Latin Horace on him: "Art thou not one of those Ci-devants that were wont to keep servants? Suspect!" He is haled forthwith, breakfast unfinished, towards Bourg-la-Reine, on foot: he faints with exhaustion; is set on a peasant's horse; is flung into his damp prison-cell: on the morrow, recollecting him, you enter; Condorcet lies dead on the floor. They die fast, and disappear: the Notabilities of France disappear, one after one, like lights in a Theatre, which you are snuffing out.
 Chinjut 11 days ago Was it not known by the Lucas test to be composite?
 codeflo 11 days ago Figuring out that a number is composite is sometimes a lot easier than actually factoring it (see RSA encryption).
 soon to be a major hollywood motion picture
 Admittedly it's quite dramatic when 45 minutes into the movie, Cole forgets whether he's on 2^42 or 2^43 and has to start over.
 kccqzy 11 days ago In elementary school having just learned exponentiation several friends of mine and I challenged each other to see who could find 2^64 the fastest. Two among the group independently discovered the classic exponentiation-by-squaring method, even though none of us could prove it right. Cole definitely would not have multiplied by two repeatedly.
 Someone 11 days ago He also would have known the final decimal digit of powers of 2 (starting at 2^1) is 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6…So, 2^42 ends with the same digit as 2^38, 2^34, …, 2^2, so its last digit is a 4.
 madcaptenor 10 days ago For some reason, the first method that came to mind for me was to find 2^60 as (1000 + 24)^6 (or at least I thought it would be until I realized finding powers of 24 wasn't that easy) and then double that seven times.I would guess that Cole found 2^67 by multiple methods, because obviously it would be tragic if it turned out he was factoring the wrong number.
 version_five 11 days ago I can picture it being the 1903 equivalent to finding a collision in a modern hashing algorithm, or beating RSA or something. So maybe Sneakers(I also wanted to acknowledge I found your comment funny)
 Title should be 2^67-1
 Interesting bits there:Detective work using intuition and assumptions.The existence of mechanical computers as given in another answer.The use of language in the linked paper (1). A mix of formal and informal. After all there is nothing to prove, just an explanation of how he did it. Examples:> The conclusion was inevitable> It is well known that every factor of 2^n — 1, p being a prime, is of the form…
 He may possibly have been assisted by generous applications of his eponymous Cole's Law.[1]
 Is that the number-theorist equivalent of Rickrolling?
 Does anybody know of a book that's a good introduction to pre-computer mathematics?I love factoring primes manually, and reading these kind of answers make me feel some "I was born in the wrong generation" vibes.
 Number theory is where I would start.
 I wonder if any of the remaining RSA Factoring Challenge numbers will be factored via "human insight", in a similar fashion.
 They won't. The algorithm he used was basically just a quadratic sieve which can be quickly run on a computer (i.e. seconds). Simple algorithms (polard rho eg) can factor numbers of this size in fractions of a second. Humans are hopelessly outclassed here.

Search: