From: rab@stallion.oz.au
Date: Mon, 25 Aug 1997 22:59:47 -0700 (PDT)
To: dlv@bwalk.dm.com
Subject: RE: Mathematics > NSA + GCHQ
Message-ID: <B1921E08F1F0D011BFE200000103803103E0EA@mallory.stallion.oz.au>
MIME-Version: 1.0
Content-Type: text/plain


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
>