home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17225 < prev    next >
Encoding:
Text File  |  1992-12-21  |  2.8 KB  |  81 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!hellgate.utah.edu!fcom.cc.utah.edu!news
  3. From: NAHAJ@CC.UTAH.EDU (John B 'Nahaj' Halleck, UUCC)
  4. Subject: Q on new(?) simple factoring algorithm.
  5. Message-ID: <1992Dec20.053421.2258@fcom.cc.utah.edu>
  6. Sender: news@fcom.cc.utah.edu
  7. Organization: UNIVERSITY OF UTAH COMPUTER CENTER
  8. Date: Sun, 20 Dec 92 05:34:21 GMT
  9. X-News-Reader: VMS NEWS 1.24
  10. Lines: 69
  11.  
  12. While investigating Fermat-like factoring algorithms, I derived the following
  13. algorithm.  (Sorry folks, it's run time is the same as fermat's, no major
  14. breakthrough.)  It, like Fermat's method, has only additions and tests in
  15. the loop, but produces it's factors directly instead of generating quantities
  16. that are used to [trivially] produce the factors.
  17.  
  18. I am unable to find this one in the literature, nor am I able to think of
  19. any reason it ought not to be prefered to fermat's method.
  20.  
  21. SO.... Could some kind soul please refer me to where and by what name this
  22. algorithm is already known? (And where to read up on it?)
  23. Given the normal implimentation of Fermat's method (For example Knuth's Vol 2
  24. code) also has an integer square root in the set up, could someone give
  25. me a reason that this method should not always be prefered to Fermat's?
  26.  
  27. Please e-mail answers, as I don't really read this group.
  28. I'll post a summary.
  29.  
  30. - John Halleck
  31. nahaj@cc.utah.edu
  32.  
  33.  
  34. ---- Simple form of the algorithm (as C code) without any of the obvious ---
  35. ---- speedup's applied -----------------------------------------------------
  36.  
  37. #include <math.h>
  38. long isqrt(long x) { return (long) sqrt((double) x); }
  39.   /* This is a hack, a real integer square root would be much better */
  40.  
  41.  
  42. #include <stdio.h>
  43. main () {
  44.  long p, q, n, guess;
  45.  
  46.  printf ("Input a positive non-zero number to be factored\n");
  47.  scanf ("%ld",&n); printf ("We will try to factor %ld\n",n);
  48.  
  49.  q=p=isqrt(n); guess = p*q;
  50.  
  51.  while (guess != n) {
  52.    if (guess>n) { guess -= p; q--; }
  53.    else         { guess += q; p++; }
  54.  }
  55.  
  56.  printf ("two possibly non-prime factors are %ld, %ld.\n",q,p);
  57.  return 0;
  58. }
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66. ------------- For the curious, why does this work? ------
  67.  
  68. A number to be factored can be represented in the form  SS+R
  69. where S is the integer square root.   The two factors are of the form:
  70.   (S+A)*(S-B) = p*q = n
  71. multiplying out the expression gives:
  72.   SS + SA - SB -AB = n
  73. Adding one to A increases the expression on the left hand side by (S-B) which
  74. is positive because S>A when we are talking about the factors.
  75. Adding one to B decreasses the value of the LHS by (S+A).
  76. So incrementing A increases our value, incrementing B decreases our value,
  77. So we just go up and down till we hit the number...
  78. The termination argument is about the same as it is for Fermat's method.
  79.  
  80. And yes, I know that there are lots of obvious speedups...
  81.