[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected], [email protected] (Mike Duvos)*Subject*: Re: Fast Modular Factorial?*From*: Matthew J Ghio <[email protected]>*Date*: Fri, 23 Sep 1994 13:13:02 -0400 (EDT)*In-Reply-To*: <[email protected]>*References*: <[email protected]>*Sender*: [email protected]

[email protected] (Mike Duvos) wrote: > A small question about large integer math... > > We are all familar with the fact that x^(2^n) mod p may be > evaluated with only n modmults which accumulate > geometrically increasing powers of x. > > Does a similar fast algorithm exist for computing (2^n)! mod p? > > The only difference here is that one is accumulating a huge > product of consecutive integers instead of the same integer > multiplied many times. I am interested in values of n > around several hundred. > > I have played with this quite a bit and am unable to see any > easy exploitable symmetry which would lead to an efficient > algorithm. > > Any ideas? Nope. The ability to take fast modular factorials as you suggest implies the ability to factor large numbers in polynomial time. If (n!)mod x = 0 then there is a factor of x which is less than n. If you can solve modular factorials, then you can solve for the largest factor of x in logarithmic time. Obviously, nobody has found a method to do either.

**Follow-Ups**:**Re: Fast Modular Factorial?***From:*Jim choate <[email protected]>

**Re: Fast Modular Factorial?***From:*[email protected] (Mike Duvos)

**References**:**Fast Modular Factorial?***From:*[email protected] (Mike Duvos)

- Prev by Date:
**RE: IBM-Led Consortium. Any thoughts?** - Next by Date:
**Re: National Research Council** - Prev by thread:
**Fast Modular Factorial?** - Next by thread:
**Re: Fast Modular Factorial?** - Index(es):