mersenneforum.org "New" primality test/check
 Register FAQ Search Today's Posts Mark Forums Read

2017-12-28, 16:11   #56
gophne

Feb 2017

3·5·11 Posts

Quote:
 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.

2017-12-28, 16:13   #57
gophne

Feb 2017

3·5·11 Posts

Quote:
 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?

2017-12-28, 16:17   #58
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

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).
That's where algorithmic complexity computation comes in.

2017-12-28, 16:19   #59
gophne

Feb 2017

2458 Posts

Quote:
 Originally Posted by jnml 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.
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.

2017-12-28, 16:54   #60
jnml

Feb 2012
Prague, Czech Republ

5·37 Posts

Quote:
 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

Code:
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)
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

Code:
~/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)

Last fiddled with by jnml on 2017-12-28 at 16:55 Reason: s/mersenne.Knowns[22]/mersenne.Knowns[21]/

2017-12-28, 17:28   #61
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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

Last fiddled with by science_man_88 on 2017-12-28 at 17:31

2017-12-28, 18:24   #62
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts

Quote:
 Originally Posted by jnml [*]However much more false positiives.
I'd say. Much more. The test simply returns true every time, huh?

2017-12-28, 18:33   #63
jnml

Feb 2012
Prague, Czech Republ

5·37 Posts

Quote:
 Originally Posted by Batalov I'd say. Much more. The test simply returns true every time, huh?

Oops

 2017-12-28, 23:23 #64 gophne   Feb 2017 3·5·11 Posts false positives 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.
2017-12-29, 00:06   #65
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts

Quote:
 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??

2017-12-29, 00:20   #66
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2735 2021-12-03 14:57 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 ewmayer Math 11 2007-04-23 19:07 James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 22:29.

Fri Dec 3 22:29:18 UTC 2021 up 133 days, 16:58, 0 users, load averages: 0.94, 1.35, 1.45