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

Fwd: Re: fast alg for calculating factorial mod m

Expand Messages
  • Jim Fougeron
    This is cross posted from coderpunks email list. I thought there might be some people with insite here (I am also curious). Jim.
    Message 1 of 7 , May 15, 2001
    View Source
    • 0 Attachment
      This is cross posted from coderpunks email list. I thought there might be some
      people with insite here (I am also curious).

      Jim.

      At 05:11 PM 5/15/01 -0600, you wrote:
      >Is there a fast algorithm for calculating (n! mod m) for large
      >(hundreds of bits) k,n? If so, is there an optimization for n choose
      >k mod m?
      >--
      >Mike Stay
      >Programmer / Crypto Guy
      >AccessData Corp.
      >staym@...
    • Jud McCranie
      ... Start doing the multiplication and reduce mod m any time the current product becomes m. This is faster than calculating n! first and then reducing mod
      Message 2 of 7 , May 15, 2001
      View Source
      • 0 Attachment
        > >Is there a fast algorithm for calculating (n! mod m) for large
        > >(hundreds of bits) k,n?

        Start doing the multiplication and reduce mod m any time the current
        product becomes > m. This is faster than calculating n! first and then
        reducing mod m.


        +------------------------------------+
        | Jud McCranie |
        | |
        | former temporary part-time adjunct |
        | instructor of a minor university |
        +------------------------------------+
      • Paul Leyland
        ... I think by fast the author meant by using significantly fewer than n mulmod operations. IF we had a fast (read: polynomial) way of calculating n! mod m,
        Message 3 of 7 , May 16, 2001
        View Source
        • 0 Attachment
          > > >Is there a fast algorithm for calculating (n! mod m) for large
          > > >(hundreds of bits) k,n?
          >
          > Start doing the multiplication and reduce mod m any time the current
          > product becomes > m. This is faster than calculating n!
          > first and then
          > reducing mod m.

          I think by "fast" the author meant by using significantly fewer than n
          mulmod operations.

          IF we had a fast (read: polynomial) way of calculating n! mod m, we'd
          have an equally fast method of factoring integers.


          Paul
        • Phil Carmody
          ... (Rumours of my disappearance are to be quashed henceforth, or at least as soon as I ve emptied over a week (i.e. hundreds) of mails from my inbox. Looks
          Message 4 of 7 , May 20, 2001
          View Source
          • 0 Attachment
            On Wed, 16 May 2001, "Paul Leyland" wrote:
            > > > >Is there a fast algorithm for calculating (n! mod m) for large
            > > > >(hundreds of bits) k,n?
            > I think by "fast" the author meant by using significantly fewer than n
            > mulmod operations.
            >
            > IF we had a fast (read: polynomial) way of calculating n! mod m, we'd
            > have an equally fast method of factoring integers.
            >

            (Rumours of my disappearance are to be quashed henceforth, or at least as soon as I've emptied over a week (i.e. hundreds) of mails from my inbox. Looks like Andy isn't the only one who can suffer e-mail problems.)

            Paul is (of course) right.
            The fastest I know of is a 'constant factor' speedup:

            http://www.mathsource.com/MathSource/NumberedItems/0203-331-0011

            Phil

            Mathematics should not have to involve martyrdom;
            Support Eric Weisstein, see http://mathworld.wolfram.com
            Find the best deals on the web at AltaVista Shopping!
            http://www.shopping.altavista.com
          • d.broadhurst@open.ac.uk
            ... But Phil, you have done, telepathically, what was needed: see how moderate we were while you were not moderating:-) David
            Message 5 of 7 , May 20, 2001
            View Source
            • 0 Attachment
              Phil Carmody wrote:
              > Rumours of my disappearance are to be quashed henceforth
              But Phil, you have done, telepathically, what was needed:
              see how moderate we were while you were not moderating:-)
              David
            • d.broadhurst@open.ac.uk
              ... Edward Gibbon has a good quote, which Richard Feynman ... Hold on, like Feynman, to that almost , It s my mealticket, as a teacher...
              Message 6 of 7 , May 20, 2001
              View Source
              • 0 Attachment
                > see how moderate we were while you were not moderating:-)
                Edward Gibbon has a good quote, which Richard Feynman
                recalls in the intro to his 1963 CalTech lectures in physics:
                > The power of instruction is seldom of much efficacy except in
                > those happy dispositions where it is almost superfluous.
                Hold on, like Feynman, to that "almost",
                It's my mealticket, as a teacher...
              • Phil Carmody
                ... Ah, but moderation is done via a HTTP interface, and my mail was blocked by a SMTP problem. While seeing if I was bouncing I went in as moderator, noticed
                Message 7 of 7 , May 21, 2001
                View Source
                • 0 Attachment
                  On Sun, 20 May 2001, d.broadhurst@... wrote:
                  > Phil Carmody wrote:
                  > > Rumours of my disappearance are to be quashed henceforth
                  > But Phil, you have done, telepathically, what was needed:
                  > see how moderate we were while you were not moderating:-)

                  Ah, but moderation is done via a HTTP interface, and my mail was blocked by a SMTP problem. While seeing if I was bouncing I went in as moderator, noticed that I wasn't bouncing, but noticed that someone else was - which I've already followed up on. So I was moderating, just not reading the messages (or sending any).

                  So it's my _postings_ that cause the problems, then.
                  Hmmm...

                  Phil

                  Mathematics should not have to involve martyrdom;
                  Support Eric Weisstein, see http://mathworld.wolfram.com
                  Find the best deals on the web at AltaVista Shopping!
                  http://www.shopping.altavista.com
                Your message has been successfully submitted and would be delivered to recipients shortly.