From gw@harriet.informatik.Uni-Koeln.DESat Mar 2 09:25:52 1996 Date: Fri, 1 Mar 1996 20:36:19 EST From: Georg Wambach To: Multiple recipients of list NMBRTHRY Subject: One more 116 decimal digit "general number" factored Cologne Feb 13, 1996 We - Alexandra Schmidt and Georg Wambach - hereby announce the succesful factorization of a 116 decimal digit composite of the Cunnigham project using the hypercube variation of the multiple polynomial quadratic sieve (hmpqs). The number is a remaining cofactor of 7^194 + 1, and the special number field sieve is _not_ applicable to it. - The whole factorisation took place in Cologne and it's neighborhood using 4 (four) machines. 70% of the relations have been produced by the Parsytec GCel1024 at the Center of Parallel Computing (http://www.zpr.uni-koeln.de/) at Cologne. - The factors are primes of 34 and 82 digits, which means we have been quite unlucky with the elliptic curve method. :-( Again, the running time of hmpqs depends on the size of the number to be factored and _not_ on the size of the smallest factor. - The whole computation could be reproduced on e.g. a 512 node IBM SP2 in about 3 (three) days. Although we estimate a speedup of 1.5 to the classical mpqs, we don't claim to be faster than a general number field sieve implementation (our's coming soon :-). - It is the third biggest number ever factored by mpqs of the Cunningham project (the others have 116 decimal digits, too). - The whole code has been written by ourselves (based on an initial implementation by F.-D. Heider, F. Damm and G. Wambach [1], extensively rewritten by G. Wambach and H. Wettig [2]). - Special thanks go the Center of Parallel Computing (70% + 8%), the ZIAM Zentrum f"ur Industrielle Anwendungen massiver Parallelit"at GmbH (http://www.ziam.de/) (14%), and Prof. Speckenmeyer (7%) for offering computing time. More information on request. Comments are welcome! Alexandra Schmidt Georg Wambach Universitaet zu Koeln/Institut fuer Informatik/Pohligstrasse 1/D-50969 Koeln Tel: +49 221 470-5308/Fax:+49 221 470-5317/E-Mail:gw@informatik.uni-koeln.de Germany [1] F. Damm, F.-P. Heider, G. Wambach, ``MIMD-Factorisation on Hypercubes'', {\it Advances in Cryptology -- EUROCRYPT '94}, Springer Lecture Notes in Computer Science 950 (1995), S.400-409. [2] G. Wambach, H. Wettig, ``Block Sieving Algorithms'', {\it Working Paper 95-190}, Center of Parallel Computing, University of Cologne, Cologne, 1995. I am for rent (hopefully) October 1st. If you are looking for a postdoc in cryptography or scheduling, I'll be glad to hear from you.