home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17755 < prev    next >
Encoding:
Text File  |  1993-01-06  |  2.2 KB  |  52 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!agate!dog.ee.lbl.gov!hellgate.utah.edu!fcom.cc.utah.edu!news
  3. From: NAHAJ@CC.UTAH.EDU (John B 'Nahaj' Halleck, UUCC)
  4. Subject: SUMMARY of answers:  What is this factoring algorithm called?
  5. Message-ID: <1993Jan6.185027.3219@fcom.cc.utah.edu>
  6. Sender: news@fcom.cc.utah.edu
  7. Organization: UNIVERSITY OF UTAH COMPUTER CENTER
  8. Date: Wed, 6 Jan 93 18:50:27 GMT
  9. X-News-Reader: VMS NEWS 1.24
  10. Lines: 40
  11.  
  12. [I posted a factoring algorithm, and asked what it was called, and where
  13.  I could read up on it.]
  14.  
  15. Algorithm in question:   (C version)
  16.  
  17.            q=p=(long) sqrt(n); guess = p*q;
  18.  
  19.            while (guess != n) {
  20.                  if (guess>n) { guess -= p; q--; }
  21.                  else         { guess += q; p++; }
  22.            }
  23.            printf ("two possibly non-prime factors are %ld, %ld.\n",q,p);
  24.  
  25. Summary:
  26.  
  27.   Every single reply, without exception, received to date has pointed out
  28.   that it can't be used to factor large numbers.    I thought this was
  29.   self evident, but since everyone that answered pointed this out, I'm
  30.   putting it in the summary.
  31.  
  32.   Nobody had a specific name or literature references for the algorithm
  33.   itself.   Although several people miss-identified it as Fermat's method.
  34.   Since it factor's by addition and subtraction, and there is a square
  35.   root in the setup, and it adjusts two parameters, it does have superficial
  36.   resemblance to Fermat's method.   But a closer look will show that it is
  37.   not.
  38.  
  39.   The most generally usefull answer was that this is one of the infinite
  40.   class of "potential function" factoring algorithms.   These are in form
  41.   identical to certain potential function curve drawing algorithms.  The
  42.   graphics routines draw curves by trying to stay as close to the zero 
  43.   curve of the function as they can, while staying on the latitice.  The
  44.   factoring algorithms do the same (for a curve known to go through the
  45.   factors) but also check to see if we are on a lattice point.
  46.   This point is somewhat obscured in the form given by the test
  47.      guess == n
  48.   if one rewrites the test as   guess - n  =  0   then the potential function
  49.   character of the algorithm becomes more clear.
  50.   [Answer provided by LeRoy Eide <lneide@cc.utah.edu> in a phone call]
  51.  
  52.