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

*To*: [email protected] (Matthew J Ghio), [email protected]*Subject*: Re: Fast Modular Factorial?*From*: [email protected] (Mike Duvos)*Date*: Fri, 23 Sep 1994 12:23:05 -0700 (PDT)*In-Reply-To*: <[email protected]> from "Matthew J Ghio" at Sep 23, 94 01:13:02 pm*Sender*: [email protected]

Matthew J Ghio <[email protected]> writes: > 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. I should mention that I am interested in the case (2^n)! mod p where p is a prime and (2^n) << p. In this case no individual term of the factorial will be equal to zero mod p, and since the non-zero residues form a group under multiplication, the result can never be zero either. The ability to solve this special case may also imply the ability to factor large numbers in polynomial time, but in some less obvious way. -- Mike Duvos $ PGP 2.6 Public Key available $

**References**:**Re: Fast Modular Factorial?***From:*Matthew J Ghio <[email protected]>

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