Browse Groups

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

(7)
• NextPrevious
• 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
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
View Source
> >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
View Source
> > >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
View Source
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
View Source
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
View Source
> 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.