From: bs@gauss.mitre.org (Robert D. Silverman) Newsgroups: sci.math Subject: Re: Research Group Announces Factoring Algorithms Date: 14 Jul 1994 12:50:42 GMT Organization: Research Computer Facility, MITRE Corporation, Bedford, MA Lines: 99 Message-ID: <303cb2$a7l@linus.mitre.org> References: <301tuq$kk4@search01.news.aol.com> In article <301tuq$kk4@search01.news.aol.com> bobbyt0929@aol.com (Bobbyt0929) writes: :FOR IMMEDIATE RELEASE 07/14/1994 : :Math Research Group Announces New Factoring Algorithms : :The Currin Research Group, a private team of individuals, today announced :the availability of computer programs and related documentation for the :demonstration of number theory :discoveries involving matrix structures in real integers. The programs are :models of factoring :algorithms that reveal previously undocumented relationships between :integers and their integer :factors. Before anyone gets too excited, let me say that I have looked at their code. They appear to have discovered a variant of Fermat's method. Fermat's method factors an integer N by representing it as a difference of two squares. It works best when the number being factored is the product of two factors VERY close together. It is ineffective for anything much beyond 25 digits. Yes, one can construct VERY (i.e. 1000's of digits) large numbers for which the method works quickly. For example, assume p and p+2 are both 1000 digit primes. You can factor p(p+2) quickly. Their claim about "undocumented relationships" may be true. While I do not denigrate their work, it appears that these relationships were undocumented because they are simple; within reach of a junior high algebra student. I doubt whether they would be published anywhere. :Barton College has contributed to this process by providing classroom :space and meeting rooms :to the Wilson-based group. Also, Dr. Zhixiong Cai of the Barton math :department has served as :a consultant to the group by permission of the College. All computing was :performed on IBM- :compatible personal computers owned by individuals comprising the group. : :Fletcher Currin, number theorist for the Group, has been investigating :these discoveries for the :past four years. After initial theory work was completed, Currin and Bob :Watson, general :manager of the group, joined with Bob Beaman to finalize computer program :demonstrations of :the discoveries. Though the programs released today are factoring :algorithms, they are a result :of the discoveries by Currin and not the initial focus of his work. : :"We are releasing this work publicly because we feel that much more :progress can be made by :having minds in various number theory disciplines work on these :discoveries," said Watson. "We :are truly excited to think of the many professional and academic :researchers that may now take :up this work. We want to exchange ideas about progress we and others may :make." : :Currin Research Group originally pursued patent applications incorporating :its work before :deciding to release the work publicly. The group continues work on :additional number theories, :algorithms, programs, and documentation. The following materials are :available immediately on :the Internet : : :ftp char.vnet.net; change directory to pub/currin - : : :1 PRESSDOC.txt This press release copy :2 UBNOTES.txt tech notes for the UBASIC programs :3 SOURCE.txt source code listing of UBASIC programs :(items 4,5,6,7,8) :4 NEWALG01.ub UBASIC program - CURRIN factoring :5 NEWALG02.ub UBASIC program - CURRIN factoring :6 PFACTORS.ub UBASIC program - CURRIN prime factoring :7 RAND4272.ub UBASIC program - large random factors :8 RSA129XX.ub UBASIC program - RSA 129 factor solution Please note: The program listed just above factors RSA-129 (and it really does; I verified it) ONLY because they used the already known factors of RSA-129 to choose a good "starting point" for Fermat's method. Their method and code can NOT factor anything very big. Note also, that IMO their method is slower than it need be. Fermat's method can be implemented with just addition and subtraction. Their code performs quite a few multiplications and square roots on multi-precise numbers. These people are NOT cranks. They are interested amateurs. But they do seem to have ignored the existing work on the subject. In particular, I believe they would benefit greatly from reading Knuth, Vol 2. Please do not construe these remarks as criticism. I am trying to be helpful. However, claims about a "new algorithm for factoring" are not correct. I believe it is irresponsible to make such claims without checking the existing work on the subject. -- Bob Silverman These are my opinions and not MITRE's. Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"