"New" primality test/check - Page 5

gophne · 2017-12-28, 15:16

Quote:

Originally Posted by jnml

Moar stats

Code:

~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297

real	0m4.821s
user	0m4.814s
sys	0m0.008s
~/src/tmp/main>

Hi jnml

Can you give me an example of a false negative please that you have found -the target congruant for the algorithm always being 1/2*(n+1)

gophne · 2017-12-28, 15:22

Quote:

Originally Posted by jnml

Moar stats

Code:

~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297

real	0m4.821s
user	0m4.814s
sys	0m0.008s
~/src/tmp/main>

Hi jnml

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?

jnml · 2017-12-28, 15:26

Quote:

Originally Posted by gophne

Can you give me an example of a false negative please that you have found -the target congruant for the algorithm always being 1/2*(n+1)

Code:

package main

import (
	"fmt"

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

func main() {
	var tests, ok, falsePos, falseNeg int
	var negs []uint32
	n := uint32(2)
	for n <= mersenne.Knowns[48] {
		n, _ = mathutil.NextPrime(n)
		_, prime := mersenne.Known[n]
		conj := (mathutil.ModPowUint32(2, n, n+2)-1)%((n+1)/2) == 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", n)
	fmt.Println("False negatives:")
	for _, v := range negs {
		fmt.Printf("\tM_%d\n", v)
	}
}

Run

Code:

~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297
False negatives:
	M_7
	M_13
	M_19
	M_31
	M_61
	M_89
	M_127
	M_607
	M_1279
	M_2203
	M_2281
	M_3217
	M_4253
	M_4423
	M_9689
	M_9941
	M_11213
	M_19937
	M_21701
	M_23209
	M_44497
	M_86243
	M_110503
	M_132049
	M_216091
	M_756839
	M_859433
	M_1257787
	M_1398269
	M_2976221
	M_3021377
	M_6972593
	M_13466917
	M_20996011
	M_24036583
	M_25964951
	M_30402457
	M_32582657
	M_37156667
	M_42643801
	M_43112609
	M_57885161
	M_74207281

real	0m5.063s
user	0m5.059s
sys	0m0.000s
~/src/tmp/main>

jnml · 2017-12-28, 15:30

Quote:

Originally Posted by gophne

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?

I don't understand the question, sorry. Perhaps please try to reformulate your method/algorithm in a more universally comprehensible math notation. Chances are I completely misunderstood your description. Anyway, the test for a single exponent using your method as-I-understood-it takes about a microsecond in Go and could be maybe made about twice faster in assembly, I guess.

science_man_88 · 2017-12-28, 15:45

Quote:

Originally Posted by gophne

Hi jnml

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?

Want to see real crazy? Check out my blog area for more.

gophne · 2017-12-28, 15:51

Quote:

Originally Posted by jnml

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>

Hi jnml

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

e.g. M3 (2^7-1)

#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

jnml · 2017-12-28, 15:52

Quote:

Originally Posted by science_man_88

Check out y blog area for more

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

science_man_88 · 2017-12-28, 15:54

Quote:

Originally Posted by jnml

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

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

gophne · 2017-12-28, 15:57

Hi njml

I get positive results for M7,M13,M19,M31 using sagemath code (see example post #50). I could not test higher because of unknown run time.

jnml · 2017-12-28, 16:04

Quote:

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).

e.g. M3 (2^7-1)

#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

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

$2^7-1 = M_7 = M4$

meaning $M_n$ is $2^n-1$ and $Mn$ = $n$ th Mersenne Prime as listed at https://en.wikipedia.org/wiki/Mersen...ersenne_primes.

Using this notation, your method correctly detects eg. $M_3$ , $M_5$ and $M_{17}$ , but fails to detect for e.g. $M_7$ , $M_{13}$ and $M_{19}$ .

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.

jnml · 2017-12-28, 16:05

Quote:

Originally Posted by science_man_88

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

Thanks, I do understand now

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
gpuOwL: an OpenCL program for Mersenne primality testing	preda	GpuOwl	2922	2023-03-28 01:52
GQQ: a "deterministic" "primality" test in O(ln n)^2	Chair Zhuang	Miscellaneous Math	21	2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
"New primality proving test from Alex Petrov"	ewmayer	Math	11	2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor="	James Heinrich	Software	2	2005-03-19 21:58

2017-12-28, 15:57	#53
gophne Feb 2017 3×5×11 Posts	Hi njml I get positive results for M7,M13,M19,M31 using sagemath code (see example post #50). I could not test higher because of unknown run time.