View Single Post
Old 2017-12-28, 12:08   #39
jnml
 
Feb 2012
Prague, Czech Republ

22×32×5 Posts
Default

Quote:
Originally Posted by gophne View Post
The algorithm is this:

For x=n (n being an element of the set of odd (positive) number/integers, n=>1), (2^n-1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and non-congruant for all composites (barring false positives!!!!).
FTR: IIUC, the algorithm fails as soon as for M_7.


127 = 1 \pmod 9

but

(7+1)/2 = 4.

Some more evaluation (in Go):

Code:
package main

import (
	"fmt"

	"github.com/cznic/mathutil"
	"github.com/cznic/mathutil/mersenne"
)

func main() {
	fails := 0
	n := uint32(2)
	for n <= mersenne.Knowns[48] {
		n, _ = mathutil.NextPrime(n)
		if (mathutil.ModPowUint32(2, n, (n+2))-1)%((n+1)/2) == 0 {
			if _, ok := mersenne.Known[n]; ok {
				fmt.Printf("M_%d really is prime\n", n)
			} else {
				fails++
			}
		}
	}
	fmt.Printf("False positives: %d\n", fails)
}
Running it:

Code:
~/src/tmp/main> go build && time ./main
M_3 really is prime
M_5 really is prime
M_17 really is prime
M_107 really is prime
M_521 really is prime
False positives: 338664

real	0m4.744s
user	0m4.735s
sys	0m0.004s
~/src/tmp/main>
jnml is offline   Reply With Quote