mersenneforum.org "New" primality test/check
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2017-12-28, 15:16   #45
gophne

Feb 2017

16510 Posts

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)

Last fiddled with by gophne on 2017-12-28 at 15:17 Reason: correcting formula for target congruant 1/2*(n+1)

2017-12-28, 15:22   #46
gophne

Feb 2017

3·5·11 Posts

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?

2017-12-28, 15:26   #47
jnml

Feb 2012
Prague, Czech Republ

5·37 Posts

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>

2017-12-28, 15:30   #48
jnml

Feb 2012
Prague, Czech Republ

5·37 Posts

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.

Last fiddled with by jnml on 2017-12-28 at 15:31 Reason: s/the your/your/

2017-12-28, 15:45   #49
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

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.

Last fiddled with by science_man_88 on 2017-12-28 at 15:53

2017-12-28, 15:51   #50
gophne

Feb 2017

3×5×11 Posts

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

2017-12-28, 15:52   #51
jnml

Feb 2012
Prague, Czech Republ

5·37 Posts

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.

2017-12-28, 15:54   #52
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

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

 2017-12-28, 15:57 #53 gophne   Feb 2017 2458 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.
2017-12-28, 16:04   #54
jnml

Feb 2012
Prague, Czech Republ

5·37 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). 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.

2017-12-28, 16:05   #55
jnml

Feb 2012
Prague, Czech Republ

5×37 Posts

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 preda GpuOwl 2760 2022-05-15 00:00 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 06:44.

Fri May 27 06:44:39 UTC 2022 up 43 days, 4:45, 0 users, load averages: 1.61, 1.11, 1.04

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔