## Fwd: Re: fast alg for calculating factorial mod m

Expand Messages
• 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
• 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@...
• ... 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
• 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 |
+------------------------------------+
• ... 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
• 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
• ... (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
• 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
• ... 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
• 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
• ... 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
• 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...
• ... 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
• 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.