mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-11-08, 11:28   #1
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default N! modulo for large N

Is there a fast algorithm to calculate N! modulo?

It is known that (N-1)! = -1 mod N -=*ONLY WHEN*=- N is prime itself. This identity is much better than the small Fermat theorem a^(N-1) = 1 mod N, which allows to find primes probabilisticly.
But N! modulo finds them deterministicly and doesn't requir many
tries with different witnesses.
Cyclamen Persicum is offline   Reply With Quote
Old 2003-12-10, 00:22   #2
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default (N-2)! == 1 mod N iff N is prime.

I keep expecting one of the math gurus to field this one . . .

Actually, we can take it a step further:
(N-1)! = -1 mod N iff N is prime
(N-1)! == -1 mod N == (N-1) mod N
(N-1)!/(N-1) == 1 mod N
(N-2)! == 1 mod N iff N is prime

Let M = N-2
The slowest way to calculate M! is 2*3*4*5*...*(M-2)(M-1)M. Using mod N will speed it up alot, but it's still really slow for large M.

The three fastest algorithms use the prime factorization of M! to calculate it, which is all of the primes less than M each to a specific power. But to factor M you only need primes up to square root M. So in this case you would almost be factoring M^2 to generate M! to determine if M+2 is prime!

If you're going to take the time to generate N!, it would be nice it end up with a prime ~= N!, rather than ~= N. That is why there is more interest in finding primes of the form N! +/- k, or N# +/- k, rather than using your equation.

Now, if there is a fast algorithm to generate M! mod N in balanced base N, perhaps that would work.
k = 2,3,..,M/2; F = F * -k*k mod N.
hmm, unless you can cancel out some of the iterations, I don't see much speed-up.

I'm not trying to shoot you down, your idea does work. It's just not the fastest way, unless I'm missing something.
Maybeso is offline   Reply With Quote
Old 2003-12-10, 10:52   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

25×331 Posts
Default Re: N! modulo for large N

Quote:
Originally posted by Cyclamen Persicum
Is there a fast algorithm to calculate N! modulo?

It is known that (N-1)! = -1 mod N -=*ONLY WHEN*=- N is prime itself. This identity is much better than the small Fermat theorem a^(N-1) = 1 mod N, which allows to find primes probabilisticly.
But N! modulo finds them deterministicly and doesn't requir many
tries with different witnesses.
If there were, there would be a fast algorithm to factor N into primes.

Think about it.

(Hint: calculate (2^i)mod N for i = 1, 2, ...,)


Paul
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Solving systems of equations modulo n carpetpool carpetpool 2 2017-02-05 20:40
Factorial modulo a prime axn Computer Science & Computational Number Theory 66 2011-09-01 21:55
modulo operation for polynomials? smslca Math 3 2011-04-18 17:18
Order of 3 modulo a Mersenne prime T.Rex Math 7 2009-03-13 10:46
The modulo operation, how is it computed? eepiccolo Math 7 2003-01-08 03:07

All times are UTC. The time now is 20:49.

Fri Mar 5 20:49:17 UTC 2021 up 92 days, 17 hrs, 0 users, load averages: 1.74, 1.86, 2.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.