Loading ...
Sorry, an error occurred while loading the content.
 

RE: [PrimeNumbers] Possibly the least impressive factoring breakthrough in the history of mankind

Expand Messages
  • Phil Carmody
    ... Oh indeed. I was contrasting the almost-only-addition fermat family to the one-division and several mults per step squfof. Oh my goodness - it s evolving
    Message 1 of 5 , May 30, 2002
      --- Paul Leyland <pleyland@...> wrote:
      >
      > > > Check out Lehman's method. It's asymptotically n^{1/3}
      > >
      > > That's the trial-divide + repeatedly use fermat on scaled-up
      > values?
      > > If so, then my technique is applicable to that algorithm too, but
      > > can't have quite the boost as it does in plain Fermat.
      >
      > That's the one.
      >
      > I thought Knuth's implementation was also essentially
      > division-free.
      > Algorithm D in the second edition uses division only to set up the
      > initial sieve tables and pointers therein, and for the supposedly
      > rare
      > occurrences of checking a value which is a quadratic residue modulo
      > all
      > the the moduli

      Oh indeed. I was contrasting the almost-only-addition fermat family
      to the one-division and several mults per step squfof.

      Oh my goodness - it's evolving as we speak...
      Gonna be one fun bus-ride home...

      Phil

      =====
      --
      "One cannot delete the Web browser from KDE without
      losing the ability to manage files on the user's own
      hard disk." - Prof. Stuart E Madnick, MIT.
      So called "expert" witness for Microsoft. 2002/05/02

      __________________________________________________
      Do You Yahoo!?
      Yahoo! - Official partner of 2002 FIFA World Cup
      http://fifaworldcup.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.