mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > News

Reply
 
Thread Tools
Old 2018-12-19, 03:16   #78
Madpoo
Serpentine Vermin Jar
 
Madpoo's Avatar
 
Jul 2014

2×23×71 Posts
Default

Quote:
Originally Posted by kriesel View Post
I hope it's either statistical fluctuation, or an actual pattern with mathematical justification TBD, not a consequence of similar effect undiscovered bugs lurking in the primality test codes. Some of the codes have ancestry in common. If there was an issue in common, present in a bit of "DNA in common", despite the best efforts of the authors and extreme care in using differing programs on differing hardware in multiple confirmations by multiple individuals, how could we know?
If it helps put you at ease, the current iterations of programs can be run against the known primes that have an exponent == 3 mod 4, and I think those tests have been done lately and confirmed. But if in doubt, run your own test to make sure.

EDIT: By "done lately and confirmed" I mean there are people who do sometimes run new tests of previously discovered primes - the server doesn't accept them, but people do the tests, I guess just to see what happens, or whatever.

Last fiddled with by Madpoo on 2018-12-19 at 03:19
Madpoo is offline   Reply With Quote
Old 2018-12-19, 05:32   #79
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×5×11×37 Posts
Default

Quote:
Originally Posted by Madpoo View Post
If it helps put you at ease, the current iterations of programs can be run against the known primes that have an exponent == 3 mod 4, and I think those tests have been done lately and confirmed. But if in doubt, run your own test to make sure.

EDIT: By "done lately and confirmed" I mean there are people who do sometimes run new tests of previously discovered primes - the server doesn't accept them, but people do the tests, I guess just to see what happens, or whatever.
Perhaps people rerun them to test their setup for reliability, or to see what sort of alert sound it might make. (No sound if it's a known one, in my experience.)

In PRP3, for the series of all known Mersenne exponents, I'm half way through M49 now, having started from M2, running the exponents big enough for gpuOwL V5.0-9c13870, and the lower exponents were run on prime95 v29.4b8.
After the gpuowl run completes (and perhaps with some delay if I've guessed M51 right), run times will go up at https://www.mersenneforum.org/showpo...6&postcount=10

Haven't seen anything out of the ordinary yet. That's encouraging but not definitive.

If they all pass, it does not necessarily mean the existing codes are without flaw.
If one fails, it does not necessarily mean the existing codes are flawed, it could be a transient hardware issue.There's a sliver of a chance of an error occurring outside the loop of iterations that are guarded for accuracy by the Gerbicz check.
No disrespect to any of the authors (or users, or hardware designers for that matter; some tasks are just very hard). I've fixed code that failed nonreproducibly at low rates. Ppb or lower frequency bugs can be hard to determine exist, much less identify and resolve. Current assignments can be of order 1018 core clocks to complete.
kriesel is online now   Reply With Quote
Old 2018-12-19, 08:18   #80
GP2
 
GP2's Avatar
 
Sep 2003

257910 Posts
Default

Quote:
Originally Posted by Madpoo View Post
I ran a quick count of the distinct exponents with any known factors and whether that exponent is 1 or 3 mod 4:

Mod Count
1 14,559,812 (49.301%)
3 14,972,752 (50.699%)

I wouldn't say it's a runaway for the 3 mod 4 exponents being factored. In fact it seems like a pretty basic variation around 50/50 based on an incomplete set.
But exponents of p=3 mod 4 do have slightly more factors than exponents of p=1 mod 4, as was noted as early as 1967 by Ehrman (and cited by Wagstaff in 1983).

So I would expect that the counts above will never be exactly 50/50 even theoretically. If you slightly alter the λ of a Poisson distribution then you slightly alter your counts at k=0.

We could look at the factors themselves, rather than distinct exponents with or without factors. Based on the same dataset I used before (frozen on 2018-12-01), I get:

Code:
                         all f    f <= 65 bits
p=1 mod 4, f=1 mod 8    9846883     9304449
p=3 mod 4, f=1 mod 8    9833742     9310151

p=1 mod 4, f=7 mod 8   10655959    10119410
p=3 mod 4, f=7 mod 8   11565454    11045807
So
  1. There are more factors with f=7 (mod 8) than f=1 (mod 8)
  2. The fact that exponents with p=3 (mod 4) are more likely to have factors than exponents with p=1 (mod 4) is due to the factors that are 7 (mod 8).
  3. As your post also reflected, factors of size 65 bits or less are a pretty big subset of the set of all known factors

If p=3 mod 4 and 2p+1 is prime, then it's a factor of the Mersenne number with exponent p, and f=2p+1=7 mod 8. And if p=1 mod 4 then the smallest possible factor is 6p+1, and again in this case there will be f=6p+1=7 mod 8.

Last fiddled with by GP2 on 2018-12-19 at 08:29
GP2 is offline   Reply With Quote
Old 2018-12-19, 09:42   #81
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

2×19×29 Posts
Default

Quote:
Originally Posted by kriesel View Post
I hope it's either statistical fluctuation, or an actual pattern with mathematical justification TBD, not a consequence of similar effect undiscovered bugs lurking in the primality test codes. Some of the codes have ancestry in common. If there was an issue in common, present in a bit of "DNA in common", despite the best efforts of the authors and extreme care in using differing programs on differing hardware in multiple confirmations by multiple individuals, how could we know?
I think we are confident with very high probability that the currently known mersenne primes (51 of them) are indeed prime.

So the "systematic error" could be only in the form of undiscovered primes (below the current wavefront).

If that would be the case, then the density of MPs would be even farther away from what's theoretically predicted.
preda is online now   Reply With Quote
Old 2018-12-19, 16:33   #82
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

32·61 Posts
Default

Quote:
Originally Posted by GP2 View Post
  1. There are more factors with f=7 (mod 8) than f=1 (mod 8)
  2. The fact that exponents with p=3 (mod 4) are more likely to have factors than exponents with p=1 (mod 4) is due to the factors that are 7 (mod 8).
  3. As your post also reflected, factors of size 65 bits or less are a pretty big subset of the set of all known factors

If p=3 mod 4 and 2p+1 is prime, then it's a factor of the Mersenne number with exponent p, and f=2p+1=7 mod 8. And if p=1 mod 4 then the smallest possible factor is 6p+1, and again in this case there will be f=6p+1=7 mod 8.

Not sure how good of a comparison they are, but generalized repunits may provide enough data for some empirical analysis.
Some time ago I searched for primes p such that 2kp+1 give less primes than average for small k, thus making it more probable that (b^p-1)/(b-1) is prime. The output was not that significant, as far as I remember, but it was just a thought.
mart_r is offline   Reply With Quote
Old 2018-12-19, 18:12   #83
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Quote:
Originally Posted by mart_r View Post
Not sure how good of a comparison they are, but generalized repunits may provide enough data for some empirical analysis.
Some time ago I searched for primes p such that 2kp+1 give less primes than average for small k, thus making it more probable that (b^p-1)/(b-1) is prime. The output was not that significant, as far as I remember, but it was just a thought.
Paul Bourdelais is looking for generalized repunit primes, but I think he's only reached the 1M or 2M exponent ranges by now.

And apart from Wagstaff (b=−2), I've been doing ECM lately to find more factors for generalized repunits for bases 3, 5, 7, 11, 12 and −3, −5, −7, −10, −11, −12. I've contributed the factors to FactorDB and found some new PRP cofactors, But it's mostly very unexplored territory. For instance, for base b=3 I'm finding lots of small factors unknown by FactorDB at a wavefront of a mere p=63k or so, and at even lower p for the other bases.

So right now there just aren't that many known primes or semiprimes yet for these repunits, and the statistics are too low to be meaningful.
GP2 is offline   Reply With Quote
Old 2018-12-21, 20:26   #84
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

As mentioned earlier, filtering by non-tiny p is in practice equivalent to filtering by the asymmetricity of the factors that make up the semiprime.

We can only find relatively small factors, so beyond the Cunningham project range where nearly everything is fully factored, every Mersenne semprime or Wagstaff semiprime that we are capable of discovering is necessarily composed of two highly asymmetric factors.

These were the counts when we filtered Mersenne semiprimes by size of the exponent p:

Quote:
Originally Posted by GP2 View Post
Code:
Mersenne semiprimes

             filter by
           p greater than:
           10^3 10^4 10^5
mod 4
     p=1    16   10    7
     p=3    30   20   14
mod 8
     p=1     8    5    3
     p=3    12    7    5
     p=5     8    5    4
     p=7    18   13    9
But if we consider only Mersenne semiprimes (of any size) where the bit length of the (smaller) factor is less than 5% of the bit length of the Mersenne number, then we get nearly the same counts as when we filter for exponent p < 10^3 :

Code:
Mersenne semiprimes

        filter by asymmetric bit length:
           len(small factor) < 0.05 *
           len(Mersenne number)
mod 4
     p=1    15
     p=3    29
mod 8
     p=1     8
     p=3    11
     p=5     7
     p=7    18
Similarly, these were the counts when we filtered Wagstaff semiprimes by size of the exponent p:

Quote:
Originally Posted by GP2 View Post
Code:
Wagstaff semiprimes

             filter by
           p greater than:
           10^3 10^4 10^5
mod 4
     p=1    24   13    5
     p=3    13    6    2
mod 8
     p=1    14    9    3
     p=3     6    3    2
     p=5    10    4    2
     p=7     7    3    0
And again, if we consider only Wagstaff semiprimes (of any size) where the bit length of the (smaller) factor is less than 5% of the bit length of the Wagstaff number, then we get nearly the same counts as when we filter for exponent p < 10^3 :

Code:
Wagstaff semiprimes

        filter by asymmetric bit length:
           len(small factor) < 0.05 *
           len(Mersenne number)
mod 4
     p=1    21
     p=3    11
mod 8
     p=1    12
     p=3     5
     p=5     9
     p=7     6

Last fiddled with by GP2 on 2018-12-21 at 20:35
GP2 is offline   Reply With Quote
Old 2018-12-29, 16:21   #85
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

All factors of Mersenne numbers are 1 or 7 (mod 8). But all factors in general are 1 or 5 (mod 6), except for 2 and 3.

Combining the two gives: All factors of Mersenne numbers are 1 or 7 or 17 or 23 (mod 24).

The various congruence classes are not equally likely (factor data frozen as of December 1):

Code:
[(1, 170925), (7, 190532), (17, 185312), (23, 207834)]      0M < p < 10M
[(1, 135127), (7, 150156), (17, 146802), (23, 165115)]     10M < p < 20M
[(1,  83674), (7,  95232), (17,  92200), (23, 104402)]    990M < p < 1000M
There is a marked difference between p=1 (mod 4) and p=3 (mod 4):

Code:
    p=1 (mod 4)
[(1,  85562), (7, 102644), (17,  92628), (23,  88934)]      0M < p < 10M
[(1,  67370), (7,  81196), (17,  73487), (23,  69787)]     10M < p < 20M
[(1,  41802), (7,  51688), (17,  46104), (23,  44159)]    990M < p < 1000M

    p=3 (mod 4)
[(1,  85363), (7,  87888), (17,  92684), (23, 118900)]      0M < p < 10M
[(1,  67757), (7,  68960), (17,  73315), (23,  95328)]     10M < p < 20M
[(1,  41872), (7,  43544), (17,  46096), (23,  60243)]    990M < p < 1000M
It's interesting, for example, that for exponents p=3 (mod 4), factors that are f=23 (mod 24) are found about one-third more frequently than the other kinds.

Empirically, all Mersenne numbers with odd exponent are 7 mod 24 (that is, the values of the Mersenne numbers themselves, not the values of the exponents).

Therefore a Mersenne semiprime must consist of either a (1, 7) mod 24 pair of factors or a (17, 23) mod 24 pair of factors. So the frequency asymmetries of 1,7,17,23 mod 24 factors maybe can start to explain why p=1 (mod 4) and p=3 (mod 4) seem to produce semiprimes with different likelihood?

Last fiddled with by GP2 on 2018-12-29 at 16:56
GP2 is offline   Reply With Quote
Old 2018-12-29, 16:25   #86
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Likewise, all factors of Wagstaff numbers are 1 or 3 (mod 8) and consequently 1, 11, 17, 19 (mod 24).

For all known factors (as of a couple of days ago), we also have asymmetries:

Code:
    all
[(1, 520596), (11, 807965), (17, 638798), (19, 672074)]

    p=1 (mod 4)
[(1, 257566), (11, 514932), (17, 316467), (19, 279297)]

    p=3 (mod 4)
[(1, 263030), (11, 293033), (17, 322331), (19, 392777)]
Empirically, all 2^n+1 with odd exponent are 9 mod 24, and Wagstaff numbers (2^n+1)/3 with odd exponent are all 11 or 19 mod 24, except for n=3 which gives (2^n+1)/3 = 3.

Last fiddled with by GP2 on 2018-12-29 at 16:46
GP2 is offline   Reply With Quote
Old 2018-12-29, 17:03   #87
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by GP2 View Post
All factors of Mersenne numbers are 1 or 7 (mod 8). But all factors in general are 1 or 5 (mod 6), except for 2 and 3.

Combining the two gives: All factors of Mersenne numbers are 1 or 7 or 17 or 23 (mod 24).

The various congruence classes are not equally likely (factor data frozen as of December 1):

Code:
[(1, 170925), (7, 190532), (17, 185312), (23, 207834)]      0M < p < 10M
[(1, 135127), (7, 150156), (17, 146802), (23, 165115)]     10M < p < 20M
[(1,  83674), (7,  95232), (17,  92200), (23, 104402)]    990M < p < 1000M
There is a marked difference between p=1 (mod 4) and p=3 (mod 4):

Code:
    p=1 (mod 4)
[(1,  85562), (7, 102644), (17,  92628), (23,  88934)]      0M < p < 10M
[(1,  67370), (7,  81196), (17,  73487), (23,  69787)]     10M < p < 20M
[(1,  41802), (7,  51688), (17,  46104), (23,  44159)]    990M < p < 1000M

    p=3 (mod 4)
[(1,  85363), (7,  87888), (17,  92684), (23, 118900)]      0M < p < 10M
[(1,  67757), (7,  68960), (17,  73315), (23,  95328)]     10M < p < 20M
[(1,  41872), (7,  43544), (17,  46096), (23,  60243)]    990M < p < 1000M
It's interesting, for example, that for exponents p=3 (mod 4), factors that are f=23 (mod 24) are found about one-third more frequently than the other kinds.

Empirically, all Mersenne numbers with odd exponent are 7 mod 24 (that is, the values of the Mersenne numbers themselves, not the values of the exponents).

Therefore a Mersenne semiprime must consist of either a (1, 7) mod 24 pair of factors or a (17, 23) mod 24 pair of factors. So the frequency asymmetries of 1,7,17,23 mod 24 factors maybe can start to explain why p=1 (mod 4) and p=3 (mod 4) seem to produce semiprimes with different likelihood?
no matter the mersenne with prime exponent, an odd number of prime factors need be 3 mod 4, 1 mod 4 can have any number at last check. so 7 mod 8 is slightly biased potentially from that. not just sophie germain primes.
science_man_88 is offline   Reply With Quote
Old 2018-12-29, 18:39   #88
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

7816 Posts
Thumbs up

I do not know what "empirically" means in the preceding posts, but for any odd \(p\) we have \[2^p\equiv(-1)^p = -1 \pmod 3\] and also for any \(p\ge 3\) we have \[2^p=2^3\cdot 2^{p-3}\equiv 0\cdot 2^{p-3}=0 \pmod 8\] so if we combine, whenever \(p\) is both odd and at least three, then \(2^p\equiv 8 \pmod {24}\). Therefore \(2^p-1\equiv 7 \pmod {24}\) and \(2^p+1\equiv 9 \pmod {24}\).

/JeppeSN

Last fiddled with by JeppeSN on 2018-12-29 at 18:41
JeppeSN is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
500€ Reward for a proof for the Wagstaff primality test conjecture Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23
Torture and Benchmarking test of Prome95.Doubts in implementation paramveer Information & Answers 32 2012-01-15 06:05
Wagstaff Conjecture davieddy Miscellaneous Math 209 2011-01-23 23:50
Algorithmic breakthroughs davieddy PrimeNet 17 2010-07-21 00:07
Conspiracy theories jasong Soap Box 11 2010-07-05 12:23

All times are UTC. The time now is 05:16.

Fri Jul 10 05:16:39 UTC 2020 up 107 days, 2:49, 0 users, load averages: 1.26, 1.27, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.