This thread touches a memory of mine from 18 years ago when I was at university. While studying for a mathematics exam I became sidetracked by one of Fermat's Theorems (Last? or Little?) and am convinced to this day that I came up with an algorithm for determining if a number was prime by a "simple" combination of shifts and logical operations. The beast part was that the amount of calculation was linearly related to the number of bits in the binary representation of the number. I only ever spent a couple of hours on it, working through it on paper, and after the exams were finished and I went back to it I could not find the original notes and I could not remember exactly what I had done. However it seems like someone else has...
---------- From: Dr.Dimitri Vulis KOTM[SMTP:dlv@bwalk.dm.com] Sent: Saturday, 23 August 1997 7:12 To: cypherpunks@toad.com Subject: Re: Mathematics > NSA + GCHQ
John Young <jya@pipeline.com> writes:
Along this line:
A few days ago we received an 8-page excerpt from "Shift Register Sequences," by Solomon W. Golomb (at USC), Holden-Day, Inc., no date, with a handwritten note:
NSA has tried to suppress knowledge of this stuff. Nearly all NSA 'good' algorithms are based on this technology.
IANAM, so would any of the mathematicians here give any credibility to this claim? We'll scan and put the excerpt on our Web site if worthwhile. It's composed of the book's 3 page preface and 5 pages of text and diagrams of Chapter 2 on The Shift Register as a Finite State Machine, with principal focus on de Bruijn diagrams for shift registers.
The NSA certainly did try to suppress much shift-register-related stuff.
The recent Sandia lawsuit is over shift register stuff.
There are increasingly persistent rumor of a fast factoring algorithm based on shift registers.
Therefore anything mentioning them is of interest.
But: Was there any info in the package other than the passages from the book?
I don't think it's a good idea to put up chunks of the book - the publisher might cry copyright infringement, and everybody probably has it anyway.
[I'm about to turn off this box, so I won't see any responses in a while.]
---
Dr.Dimitri Vulis KOTM Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps