20171228, 15:16  #45  
Feb 2017
3·5·11 Posts 
Quote:
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) Last fiddled with by gophne on 20171228 at 15:17 Reason: correcting formula for target congruant 1/2*(n+1) 

20171228, 15:22  #46  
Feb 2017
165_{10} Posts 
Quote:
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? 

20171228, 15:26  #47  
Feb 2012
Prague, Czech Republ
5·37 Posts 
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:
~/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> 

20171228, 15:30  #48 
Feb 2012
Prague, Czech Republ
5·37 Posts 
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 asIunderstoodit takes about a microsecond in Go and could be maybe made about twice faster in assembly, I guess.
Last fiddled with by jnml on 20171228 at 15:31 Reason: s/the your/your/ 
20171228, 15:45  #49 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Want to see real crazy? Check out my blog area for more.
Last fiddled with by science_man_88 on 20171228 at 15:53 
20171228, 15:51  #50  
Feb 2017
3·5·11 Posts 
Quote:
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^71) #1......a=2^71..................Divisor under test~127....n2 #2......b=(2^71)2.............n~125 #3......c=1/2*(b+1).............Target Congruant~63 #4......d=2^b1...................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 

20171228, 15:52  #51 
Feb 2012
Prague, Czech Republ
5×37 Posts 

20171228, 15:54  #52  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:


20171228, 15:57  #53 
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. 
20171228, 16:04  #54  
Feb 2012
Prague, Czech Republ
271_{8} Posts 
Quote:
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 mathnotation. 

20171228, 16:05  #55  
Feb 2012
Prague, Czech Republ
5·37 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2736  20211204 00:40 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 