mersenneforum.org - "New" primality test/check

mersenneforum.org (https://www.mersenneforum.org/index.php)

- gophne (https://www.mersenneforum.org/forumdisplay.php?f=149)

- - "New" primality test/check (https://www.mersenneforum.org/showthread.php?t=22838)

[QUOTE=jnml;475127]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>
[/CODE][/QUOTE]
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)

[QUOTE=jnml;475127]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>
[/CODE][/QUOTE]
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?

[QUOTE=gophne;475136]
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)[/QUOTE]

[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)
}
}
[/CODE]

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>
[/CODE]

[QUOTE=gophne;475137]
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?[/QUOTE]

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.

[QUOTE=gophne;475137]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?[/QUOTE]

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

[QUOTE=jnml;475112]FTR: IIUC, the algorithm fails as soon as for [TEX]M_7[/TEX].

[TEX]127 = 1 \pmod 9[/TEX]

but

[TEX](7+1)/2 = 4[/TEX].

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)
}
[/CODE]
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>
[/CODE][/QUOTE]
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

[QUOTE=science_man_88;475140]Check out y blog area for more[/QUOTE]

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

[QUOTE=jnml;475142]Please clarify, I would love to understand what you're saying, but I don't.[/QUOTE]
[url]http://www.mersenneforum.org/forumdisplay.php?f=140[/url]

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.

[QUOTE=gophne;475141]
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[/QUOTE]

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

[TEX]2^7-1 = M_7 = M4[/TEX]

meaning [TEX]M_n[/TEX] is [TEX]2^n-1[/TEX] and [TEX]Mn[/TEX] = [TEX]n[/TEX]th Mersenne Prime as listed at [url]https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes[/url].

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

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.

[QUOTE=science_man_88;475143][url]http://www.mersenneforum.org/forumdisplay.php?f=140[/url][/QUOTE]

Thanks, I [I]do[/I] understand now :smile: