mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > gophne

Reply
 
Thread Tools
Old 2017-12-28, 16:11   #56
gophne
 
Feb 2017

3×5×11 Posts
Default

Quote:
Originally Posted by jnml View Post
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 is offline   Reply With Quote
Old 2017-12-28, 16:13   #57
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Hi science_man_88

Which thread should I look at on the page that comes up?
gophne is offline   Reply With Quote
Old 2017-12-28, 16:17   #58
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by gophne View Post

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.
science_man_88 is offline   Reply With Quote
Old 2017-12-28, 16:19   #59
gophne
 
Feb 2017

16510 Posts
Default

Quote:
Originally Posted by jnml View Post
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 = nth 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.
gophne is offline   Reply With Quote
Old 2017-12-28, 16:54   #60
jnml
 
Feb 2012
Prague, Czech Republ

22·32·5 Posts
Default

Quote:
Originally Posted by gophne View Post
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)
		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

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]/
jnml is offline   Reply With Quote
Old 2017-12-28, 17:28   #61
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by jnml View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-12-28, 18:24   #62
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,787 Posts
Default

Quote:
Originally Posted by jnml View Post
[*]However much more false positiives.
I'd say. Much more. The test simply returns true every time, huh?
Batalov is offline   Reply With Quote
Old 2017-12-28, 18:33   #63
jnml
 
Feb 2012
Prague, Czech Republ

2648 Posts
Default

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

Oops
jnml is offline   Reply With Quote
Old 2017-12-28, 23:23   #64
gophne
 
Feb 2017

3·5·11 Posts
Default 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.
gophne is offline   Reply With Quote
Old 2017-12-29, 00:06   #65
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,787 Posts
Default

Quote:
Originally Posted by gophne View Post
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??
Batalov is offline   Reply With Quote
Old 2017-12-29, 00:20   #66
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by gophne View Post
Hi science_man_88

Which thread should I look at on the page that comes up?
Well theory on mersenne primes is probably craziest.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2733 2021-10-13 10:39
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

All times are UTC. The time now is 13:25.


Wed Oct 27 13:25:39 UTC 2021 up 96 days, 7:54, 0 users, load averages: 10.82, 11.08, 6.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.