From: don@cs.byu.edu
Date: Wed, 13 Sep 95 17:39:41 PDT
To: cypherpunks@toad.com
Subject: Factoring Software (fwd)
Message-ID: <199509140039.SAA00376@wero.byu.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Just saw this on Usenet, was wondering who knows this guy. Obviously not
a cpunk or it would have hit the list right away. Not in the mood to run
code on my account without knowing that I know what it will do.


From: bobs@mathworks.com (Bob Silverman)
Newsgroups: sci.math,sci.crypt,alt.security.pgp,sci.math.num-analysis,comp.arch.arithmetic
Subject: Factoring Code
Date: 13 Sep 1995 09:22:38 -0400
Organization: The MathWorks, Inc., Natick, MA 01760
Lines: 41
Distribution: inet
Message-ID: <436luu$3lu@puff.mathworks.com>
NNTP-Posting-Host: puff.mathworks.com

Several people have requested factoring code recently. After thinking
about it I have decided to offer a deal.

I do not have the machine resources I once had, and have some numbers
that I would like factored. They are in the 80-90 digit range. My
code will do an 85 digit number in about 500 hours on a single Sparc-10.
The code is perfectly parallelizable, so 40 machines will do 85 digits
overnight.
Run time for QS can vary by a factor of 2.5 depending on how "rich" 
the number being factored is in small quadratic residues.


I will make available my complete Multiple Polynomial Quadratic Sieve
code, along with instructions, to anyone who will factor at least one
of these numbers. This code includes the siever, the code to combine
large primes, the matrix solver (a naiive Gaussian elim over GF(2), but
one which solves a 25K x 25K system in 15 min on a single Sparc), and
the code to multiply everything together and find the factors. I will
also throw in a routine which reads the output file and scans for bad
relations. Sometimes, when running on many machines, I/O errors creep
into the output files. A machine can go down when writing a record, or
there can be a network problem etc. I also have a program which
excizes bad records in the output files And one which sets up multiple
sub-directories with the proper data files so one can run in parallel.

Also included is a program which scans the output files in these
multiple sub-directories and counts the number of relations found.
There is also a program to predict (fairly accurately!) how close to
done you are based on output from the counting program.

This code will also include a decent collection of fast, very portable
multiple precision routines.

All this is for the taking if you guarantee to factor just one number for
me.

- -- 
Bob Silverman
The MathWorks Inc.
24 Prime Park Way
Natick, MA


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQB1AwUBMFd5fsLa+QKZS485AQELHAL/QS2LizHGSzT7h3b8cU78GiR9QLoaQ6zf
FEEyt8XRDFqlUe7CKFfDKB1SPPviAZeBPM4XDfswfvfXpKNLamZQUNc7VYgzPIC0
3knFeQf2A/zWuGBZQp/TM0xBcwKW5lW7
=Zyke
-----END PGP SIGNATURE-----
<don@cs.byu.edu>           fRee cRyPTo!   jOin the hUnt or BE tHe PrEY
PGP key - http://bert.cs.byu.edu/~don     or PubKey servers (0x994b8f39)
  June 7&14, 1995: 1st amendment repealed.  Death threats ALWAYS pgp signed
* This user insured by the Smith, Wesson, & Zimmermann insurance company *