Conference rusure::math

Just got this press release...
        excuse typos...
        
        COMPUTER FACTORS 100 DIGIT NUMBER FOR FIRST TIME.
        
        CHICAGO, OCT 11 Reuter.. Researchers in the United States, Europe
        and Australia have combined their computer power to factor a
        100-digit number for the first time, the University of Chicago
        announced today.
        
        The number factored -- that is, broken down into the numbers which
        when multiplied produce the figure was 11 to the 104th power plus
        one.
        
        It has been known for years that the number was divisible by 2,17,
        and 6,304,673, the University said.
        
        The computer Factoring identifed two remaining factors, one with
        41 digits and one with 60 digits.
        
        Arien Lenstra of the Chicago faculty designed a program which
        produced the result by employing hundreds of computers in the
        United States, Europe and Australia working during hours when the
        computers would normally be idle.
        
        THe results, which took 26 days to generate were sent out by
        electronic mail and compiled at the Systems research Centre of the
        Digital Equipment Corporation in Palo Alto, California.
        
        The 100 digit number is the the largest ever factored, the
        announcement said.
        
        IT was accomplished years earlier than expected. By contrast a
        Single Cray SuperComputer would have taken nearly a year to come
        up with the answer, the university said.
        
        Lenstra said researchers were now trying to factor a number with
        102 digits. He said that the use of combined computer power to
        factor numbers had implications for the security of cryptographic
        systems used in commerce, industry and by Government.
        
        He said the ability to factor is the way to breach the security of
        key public cryptosystems, which are widely used to protect the
        integrity of wire transfers of funds...
        
        

>        The 100 digit number is the the largest ever factored, the
>        announcement said.

    Not exactly.  .0 said it more correctly.

    This quite an achievement, it made the front page of the Los Angeles
    Times. It is also a strong testament to network resource management.
    Can we find out more about how the mission was accomplished?
    Algorithms? Software environment? TNX - Dave Drake 

    
    It seems to me this is the kind of thing that the government will
    send guys in trenchcoats to visit.  Have they classified your algorythm?
    Can it be publised or has it been publised?
    
    I remember hearing for years that the NSA had methods to factor
    huge numbers fast but it was all classified.
    
    Jon

     This has all been fairly public.  If you want to donate some
     spare CPU cycles to them, just get in touch and they'll even
     send the code to be run.
     
     Dan

     Related notes are in 30.6-30.9 and perhaps in 259.0.
     
     Dan

The first draft of a paper about the factorization techniques
we used is now available in a note in the conference
CIRCUS::SRCNOTES.  I'll be posting the final version there, as
well as periodic reports of our progress.

Mark

     It was in note 28.0, "Factoring by electronic mail" by
     CIRCUS::BROWN.  Press Select or KP7 to add the conference to
     your notebook, or use
     
          Notes> ADD ENTRY CIRCUS::SRCNOTES
     
     When the full paper is ready, it will appear as a reply to
     the same topic.
     
     Dan

Hmmm nobody seems to have noticed ...

From a press release last fall:

Carl Pomerance and W.R. "Red" Alford of the University of Georgia 
have succeeded in factoring some pretty hefty numbers with PC's. 

Quoting the press release:

	All of the factoring was done on PC clones (three or four AT 
	clones were also used) except for the matrix reduction. The 
	matrix reduction step was done on a Sun 3 workstation 
	using a new matrix reduction algorithm of J.W. Smith 
	and Carl Pomerance.
	
	Result:
	
	2^332+1 =
	
	17*
	11953*
	14767689550320172808742174828062347720350769*
	2915547797343721112173446482628529057775979692132113
	
	The C95 factored was theproduct of the last two numbers.
					Red & Carl

John F.

Also from the doors of Carl Pomerance and 'Red' Alford:

  13
  12
  11
  10
   9
   8
   7
   6
   5
   4
   3
   2
   1


We have a FACTORING!!!


2783415704056554985941269027566547436008362462334209
6856531741041792239054980342217258517995521

----------
Graphitti on the paper:

After 'We have a FACTORING' someone wrote: (of what?)
To which someone else wrote: Multiply the two numbers, dummy.
To which someone has responded: C95 of 7^128+1

This is a couple of months old.

John F.

I got the marvelous opportunity to talk to both Carl Pomerance 
and 'Red' Alford the week at Georgia. They are polishing up the 
PC algorithm and are getting ready for another factoring. Look 
for a 100+ digit PC factoring in the near future.

Red is doing the PC programming and was explaining that in order 
to get the factor base, some 50,000 or so known primes onto the 
PC he had to remove a lot of the operating system from memory, 
and from the disk. and actually has code where the software
interrupt vector table ought to be. The data for the latest 
factoring was stored on a shoebox-full of about 200 floppies. (2
meg I think he said). 

BTW, the first PC factoring of a C95 number is also published in 
'Science' December 23, 1988 pp 1634-1635 Vol 242.

Cheers,

John F.

>> .7	The first draft of a paper about the factorization techniques
>>	we used is now available in a note in the conference
>>	CIRCUS::SRCNOTES.  I'll be posting the final version there, as
>>	well as periodic reports of our progress.

>> .8	     It was in note 28.0, "Factoring by electronic mail" by
>>	     CIRCUS::BROWN.  Press Select or KP7 to add the conference to
>>	     your notebook, or use
>>     
>>	          Notes> ADD ENTRY CIRCUS::SRCNOTES
>>     
>>	     When the full paper is ready, it will appear as a reply to
>>	     the same topic.
        
        The reply is there, 28.1, 1469 lines, by Mark S. Manasse
        and Arjen K. Lenstra.  You can extract it from there or
        copy circus::SRC$notes:t28_1.ps.
        
        Dan