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

building factoring routines

Expand Messages
  • Kermit Rose
    I m slowly building my factoring subroutines. I can factor numbers in the 12 digit range pretty quickly now, but it still took over a minute to find a factor
    Message 1 of 4 , Jun 2, 2006
    • 0 Attachment
      I'm slowly building my factoring subroutines.

      I can factor numbers in the 12 digit range pretty quickly now, but it still
      took over a minute to find a factor of 10^15 + 3.


      >>> for z in range(10**15+1,10**15+15):
      w = getordfac(z,m)
      print z,w


      1000000000000001 1001
      1000000000000002 2
      1000000000000003 67103479
      1000000000000004 2
      1000000000000005 255
      1000000000000006 2
      1000000000000007 2773
      1000000000000008 2
      1000000000000009 179
      1000000000000010 2
      1000000000000011 3477
      1000000000000012 2
      1000000000000013 1091
      1000000000000014 2


      Kermit < kermit@... >



      [Non-text portions of this message have been removed]
    • hecht
      I can factor numbers in the 12 digit range pretty quickly now, but it still took over a minute to find a factor of 10^15 + 3. Why so long? It takes me 24 ms
      Message 2 of 4 , Jun 3, 2006
      • 0 Attachment
        I can factor numbers in the 12 digit range pretty quickly now, but it still
        took over a minute to find a factor of 10^15 + 3.

        Why so long? It takes me 24 ms (Pollard Rho, HIT library, PIII 700 MHz)

        [Non-text portions of this message have been removed]
      • Jud McCranie
        ... For numbers in that range (fewer than 64 bits), I wouldn t use HIT or any other such package. Just use the native data types. Also, Shank s method is
        Message 3 of 4 , Jun 3, 2006
        • 0 Attachment
          At 09:42 AM 6/3/2006, hecht wrote:
          >I can factor numbers in the 12 digit range pretty quickly now, but it still
          >took over a minute to find a factor of 10^15 + 3.
          >
          >Why so long? It takes me 24 ms (Pollard Rho, HIT library, PIII 700 MHz)

          For numbers in that range (fewer than 64 bits), I wouldn't use HIT or any
          other such package. Just use the native data types. Also, Shank's method
          is probably better for that application than Pollard's method. My program
          on a 2.4 GHz factors 10^15+3 in 0.01 second.
        • Phil Carmody
          ... Now I ve decomissioned my PPro/200, I don t have a machine slow enough to measure my native double reimplimantation of Lenstra s (LIP) version of Shanks
          Message 4 of 4 , Jun 3, 2006
          • 0 Attachment
            --- Jud McCranie <j.mccranie@...> wrote:
            > At 09:42 AM 6/3/2006, hecht wrote:
            > >I can factor numbers in the 12 digit range pretty quickly now, but it still
            > >took over a minute to find a factor of 10^15 + 3.
            > >
            > >Why so long? It takes me 24 ms (Pollard Rho, HIT library, PIII 700 MHz)
            >
            > For numbers in that range (fewer than 64 bits), I wouldn't use HIT or any
            > other such package. Just use the native data types. Also, Shank's method
            > is probably better for that application than Pollard's method. My program
            > on a 2.4 GHz factors 10^15+3 in 0.01 second.

            Now I've decomissioned my PPro/200, I don't have a machine slow
            enough to measure my native double reimplimantation of Lenstra's
            (LIP) version of Shanks' SQUFOF on that number! (And I gave away
            my ARM dev board yesterday - that would have been really slow.)

            However, I found two Sparcs, with their notoriously underpowered FPUs,
            in America, and indeed they are slow enough for it to be measurable:
            SunBlade100 - 0.007s
            SunUltra5 - 0.010s
            (no idea what clock speed they may be).

            Paul - may I post the code? It's Lenstra's copyright, but you seem
            to be the guardian of it presently?

            Phil

            () ASCII ribbon campaign () Hopeless ribbon campaign
            /\ against HTML mail /\ against gratuitous bloodshed

            [stolen with permission from Daniel B. Cristofani]

            __________________________________________________
            Do You Yahoo!?
            Tired of spam? Yahoo! Mail has the best spam protection around
            http://mail.yahoo.com
          Your message has been successfully submitted and would be delivered to recipients shortly.