## Functions for primality tests

Expand Messages
• I was wondering if this expression or algorithm woud be of any use in primality tests in use today. If n 4 n is composite if the value of the expresion (n-1)!
Message 1 of 4 , Feb 20, 2006
• 0 Attachment
I was wondering if this expression or algorithm woud be of any use in
primality tests in use today.

If n>4
n is composite if the value of the expresion
(n-1)! (mod n) = 0
otherwise, n is prime because when p is prime, the value of the
expression
(p-1)! (mod p) = (p-1).

I haven't a clue what software would be good for determining this, but

-Matt
• For even moderate values of n, calculating (n-1)! in my opinion becomes darned tricky. For large values of n, say around 10,000 digits I m not sure if it is
Message 2 of 4 , Feb 20, 2006
• 0 Attachment
For even moderate values of n, calculating (n-1)! in my opinion becomes
darned tricky. For large values of n, say around 10,000 digits I'm not
sure if it is even possible. And as for the current largest primes -
forget it!

There are far better (and quicker) tests to check for primality:
fermats' little theorem, miller-rabin, baillie PSW etc are all used
however whilst they will guarantee a number is composite, they cannot
verify a number is prime.

For certain forms of numbers, mersenne primes being an obvious one,
there are good tests which can prove primality, albeit in some not
inconsiderable time.

newjack56 wrote:
> I was wondering if this expression or algorithm woud be of any use in
> primality tests in use today.
>
> If n>4
> n is composite if the value of the expresion
> (n-1)! (mod n) = 0
> otherwise, n is prime because when p is prime, the value of the
> expression
> (p-1)! (mod p) = (p-1).
>
> I haven't a clue what software would be good for determining this, but
>
> -Matt
>
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
>
>
>
>
• On Behalf Of newjack56 ... No, because it takes too long too calculate n!
Message 3 of 4 , Feb 20, 2006
• 0 Attachment
On Behalf Of newjack56
> I was wondering if this expression or algorithm would be of
> any use in primality tests in use today.

No, because it takes too long too calculate n!

> If n>4
> n is composite if the value of the expresion
> (n-1)! (mod n) = 0
> otherwise, n is prime because when p is prime, the value of
> the expression
> (p-1)! (mod p) = (p-1).
>
> I haven't a clue what software would be good for determining
>
> -Matt
>
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
>
>
>
>
• Hi all, just read about primality test problems and decided to work again on a test. Perhaps in the next weeks my primenumbersieve will be published soon in
Message 4 of 4 , Feb 25, 2006
• 0 Attachment
Hi all,

just read about primality test problems and decided to work again on a test.

Perhaps in the next weeks my primenumbersieve will be published soon in Germany.

Hope to tell you more soon.

Good luck

S.Hakan
Your message has been successfully submitted and would be delivered to recipients shortly.