Loading ...
Sorry, an error occurred while loading the content.

Functions for primality tests

Expand Messages
  • newjack56
    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
      any positive thoughts and/or comments would be helpful.

      -Matt
    • Alan McFarlane
      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
        > any positive thoughts and/or comments would be helpful.
        >
        > -Matt
        >
        >
        >
        >
        >
        > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        > The Prime Pages : http://www.primepages.org/
        >
        >
        > Yahoo! Groups Links
        >
        >
        >
        >
        >
        >
        >
        >
      • Chris Caldwell
        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
          > this, but any positive thoughts and/or comments would be helpful.
          >
          > -Matt
          >
          >
          >
          >
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://www.primepages.org/
          >
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
          >
          >
          >
        • primemind@bluewin.ch
          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.