"New" primality test/check

[gophne]

Originally Posted by jnml

Please clarify, I would love to understand what you're saying, but I don't.

Hi njml

I use very basic SAGEMATH code, as listed in post #50. Since the algorithm is very simple (straight math calculations), the results for M7, M13, M19, M31 returns positive when I run it in SAGEMATH code.

[gophne]

Originally Posted by science_man_88

http://www.mersenneforum.org/forumdisplay.php?f=140

Hi science_man_88

Which thread should I look at on the page that comes up?

[science_man_88]

Originally Posted by gophne

Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).

That's where algorithmic complexity computation comes in.

[gophne]

Originally Posted by jnml

Before digging further we should agree on notation. I used this one:



meaning is and = th Mersenne Prime as listed at https://en.wikipedia.org/wiki/Mersen...ersenne_primes.

Using this notation, your method correctly detects eg. , and , but fails to detect for e.g. , and .

I don't know sagemath, nonetheless, it might be useful to show the sagemath code as an alternative to the proper description in math-notation.

Hi jnml

Perhaps somebody else can run the code in SAGEMATH...the code is fairly straight forward since the algorithm is also simple. I will try to put it more "formally" looking at SAGE code posted by other users.

I will try to grap screen an example, but sinnce I am running SAGEMATH in "VMWare Workstation software, I can't seem to do that.

[jnml]

Originally Posted by gophne

Perhaps somebody else can run the code in SAGEMATH...the code is fairly straight forward since the algorithm is also simple. I will try to put it more "formally" looking at SAGE code posted by other users.

I will try to grap screen an example, but sinnce I am running SAGEMATH in "VMWare Workstation software, I can't seem to do that.

Okay, attempting to understand post #50, I really previously inferred a completely different method.

Source

package main

import (
	"fmt"
	"math/big"

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

var (
	_1 = big.NewInt(1)
	_2 = big.NewInt(2)
)

func main() {
	var tests, ok, falsePos, falseNeg int
	var negs []uint32
	var last uint32
	n := uint32(2)
	for n <= mersenne.Knowns[21] {
		last = n
		n, _ = mathutil.NextPrime(n)
		_, prime := mersenne.Known[n]

		// http://www.mersenneforum.org/showpost.php?p=475141&postcount=50
		//
		// #1......a=2^7-1..................Divisor under test~127....n-2
		// #2......b=(2^7-1)-2.............n~125
		// #3......c=1/2*(b+1).............Target Congruant~63
		// #4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
		// #5.......e=d mod a..............Congruant~63
		// #6.......c==e.......................True~127(divisor) is Prime

		a := mersenne.New(n)
		var b, c big.Int
		b.Sub(b.Set(a), _2)
		c.Div(c.Add(c.Set(&b), _1), _2)
		x := mathutil.ModPowBigInt(_2, &b, a)
		x.Sub(x, _1)
		conj := x.Cmp(&c) == 0

		tests++
		switch {
		case prime == conj:
			ok++
		case prime:
			falseNeg++
			negs = append(negs, n)
		default:
			falsePos++
		}
	}
	fmt.Printf("False negatives: %8d\n", falseNeg)
	fmt.Printf("False positives: %8d\n", falsePos)
	fmt.Printf("Correct results: %8d\n", ok)
	fmt.Printf("Prime exponents: %8d (tests performed)\n", tests)
	fmt.Printf("Last exponent:   %8d\n", last)
	fmt.Println("False negatives:")
	for _, v := range negs {
		fmt.Printf("\tM_%d\n", v)
	}
}

Run

~/src/tmp/main> go build && time ./main 
False negatives:        0
False positives:     1205
Correct results:       21
Prime exponents:     1226 (tests performed)
Last exponent:       9941
False negatives:

real	1m10.533s
user	1m11.096s
sys	0m0.428s
~/src/tmp/main>

• Only exponents < 10000 were tested this time as the single test is not anymore that fast as it was in the misunderstood case.
  
• No more false negatives!
  
• However much more false positiives.
  
• Seems to run a bit than LL tests in PARI (see http://www.mersenneforum.org/showpos...6&postcount=40)

[science_man_88]

Originally Posted by jnml

• Seems to run a bit than LL tests in PARI (see http://www.mersenneforum.org/showpos...6&postcount=40)

http://www.mersenneforum.org/showthread.php?t=20803 may also give useful comparisons

[Batalov]

Originally Posted by jnml

[*]However much more false positiives.

I'd say. Much more. The test simply returns true every time, huh?

[jnml]

Originally Posted by Batalov

I'd say. Much more. The test simply returns true every time, huh?

Oops

[gophne]

Hi njml and batalov

I get the following running the Algorithm in SAGEMATH

False Positives identified by the algorithm;

0-100..............0 ~100 value, number of odd numbers tested would be half
0-1,000............3
0-10,000...........22
0-100,000..........78
0-1,000,000........245

pi(x)~78,498 primes less than 1,000,000 (primes.utm.edu) and therefore potentially 421,502 odd numbers that could be potentially "false positives". The actual false positives up to 1,000,000 according to the algorithm (run in SAGE) is therefore approx. 0.058%

No false negatives encountered up to 1,000,000.

[Batalov]

Originally Posted by gophne

The algorithm is this:

For <...> odd n, (2^n-1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and non-congruant for all composites <...>

Thats it!

So you are saying that your test is (2^n-1) = (n+1)/2 (mod n+2).
This is the same as:
2^(n+1)-2 = n+1 (mod n+2) . . . . . . (equivalent to mulitply both sides by 2 because n is odd)
2^(n+1) = n+3 (mod n+2) . . . . . . . . rearrange, subtract n+2...
2^(n+1) = 1 (mod n+2)
which is the 2-PRP test for n+2, not for n.

Why would this test work for n? It "sort of" works for n+2, for sure. But what does it have to do with the primality of n??

[science_man_88]

Originally Posted by gophne

Hi science_man_88

Which thread should I look at on the page that comes up?

Well theory on mersenne primes is probably craziest.