mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Data (https://www.mersenneforum.org/forumdisplay.php?f=21)
-   -   Mersenne number factored (disbelievers are biting elbows) (https://www.mersenneforum.org/showthread.php?t=19407)

alpertron 2014-08-06 13:07

Well, I said that this is an approximation. Before these calculations, I had no idea of how many PRPs we would find.

alpertron 2014-08-06 17:30

[QUOTE=Gordon;379856]So how many Mersenne Primes was that you found again ???

Please reply with the prime exponent you found and we'll throw you a :party:[/QUOTE]
Well, this is not correct. In order to find these Mersenne primes, you need several people: the inventor of the algorithm, one or more persons that polish it making more amenable to computers, the one who code it in an optimized way, and the person who runs the computer that finally finds the results.

So you are just one little line in the "cast of characters" (that spans several screens) of the discovery of M2976221.

Silverman is in the second category of people mentioned above, but I think he is not related to anything related to Mersenne number primality.

Batalov 2014-08-06 17:34

[STRIKE]The posts that were less than useful to this thread are now moved to the [URL="http://mersenneforum.org/showthread.php?goto=newpost&t=12945"]eponymous thread[/URL].[/STRIKE]

The posts that were less than useful to this thread are now moved to the [URL="http://mersenneforum.org/showthread.php?goto=newpost&t=12945"]thread for posts that are less than useful[/URL].

R.D. Silverman 2014-08-06 17:58

[QUOTE=alpertron;379857]
Silverman is in the second category of people mentioned above, but I think he is not related to anything related to Mersenne number primality.[/QUOTE]

Wrong again. Check with David Slowinski.

A long time prior to GIMPS (early 80's), I provided David with a
moderately large list of exponents that did not need to be factored because I
had found small divisors.

Batalov 2014-08-06 18:05

[QUOTE=axn;379483]I don't see how the last 64 bits help.

Lets say F divides Mp. By Fermat, 3^(Mp/F) = 3 (mod (Mp/F)). Raising both sides to F, we get 3^Mp = 3^F (mod Mp/F). Now if we have the full residue 3^Mp (mod Mp), we can easily calculate 3^Mp (mod Mp/F). But last 64-bits? Are you saying 3^Mp = 3^F (mod Mp/F) ==> 3^Mp = 3^F (mod Mp). I just tried it with M2311 (77567729423209*4514379640917651135021865565129IPRP-652). LHS holds, but RHS doesn't.[/QUOTE]
I now had some spare time to check if the low bits help and indeed they don't* and I didn't find a trick to make them useful (I was thinking that we could bit-rotate the residue, but we can only do that mod M[SUB]p[/SUB], not mod M[SUB]p[/SUB]/F).

The top 512bits, as P.L.M. wrote, work, but one needs a modification to the program, to save those 512-bit residues in a file and later fetch and use them. EWMayer wrote [URL="http://mersenneforum.org/showpost.php?p=342776&postcount=15"]some code like that[/URL]. If I were to implement this, I could write a patch to prime95 (I've written and used small other ad hoc hacks; it is doable).

____
*I [STRIKE]remembered[/STRIKE] was misled into thinking about this possibility by my anecdotal experience with tiny factors, like 5 for some [TEX]2^p \pm 2^{{p+1}\over{2}}+1[/TEX] and 7 for some [TEX]3^p \pm 3^{{p+1}\over{2}}+1[/TEX]. They show up as prpbase^4 and prpbase^6 in the RES64, but this is a pure coincidence: e.g.
[FONT="Fixedsys"]2^1223+2^612+1 is composite: RES64: [0000000000000051] (0.0041s+0.0008s)[/FONT] (where 51[SUB]16[/SUB] = 81 = 3^4)
They are, of course, special for that form.
This small curio does not extend itself to even slightly larger factors, let alone 80-90+ bit factors that are relevant for the OP PRP project.

alpertron 2014-08-06 18:06

[QUOTE=R.D. Silverman;379861]Wrong again. Check with David Slowinski.

A long time prior to GIMPS (early 80's), I provided David with a
moderately large list of exponents that did not need to be factored because I
had found small divisors.[/QUOTE]

OK, my fault. I didn't know that. But this is not related to the second category I mentioned before, but more with KWh spent on calculations.

Gordon 2014-08-06 20:19

[QUOTE=Batalov;379859]The posts that were less than useful to this thread are now moved to the [URL="http://mersenneforum.org/showthread.php?goto=newpost&t=12945"]eponymous thread[/URL].[/QUOTE]

[URL="http://dictionary.reference.com/browse/eponymous?s=t"][URL="http://dictionary.reference.com/browse/eponymous?s=t"]eponymous[/URL][/URL] - nice word, completely wrongly used.

Nice to see the forum police out and about.

Gordon 2014-08-06 20:25

[QUOTE=Batalov;379859]The posts that were less than useful to this thread are now moved to the [URL="http://mersenneforum.org/showthread.php?goto=newpost&t=12945"]eponymous thread[/URL].[/QUOTE]

Which was actually everything from about post 155 onwards, if you want to set yourself as the forum police then at least be consistent :bow:

henryzz 2014-08-06 21:42

[QUOTE=alpertron;379831]Using the formulas above I computed the expected numbers of PRP to be found in different ranges. Notice that most Mersenne numbers are not factored up to these bounds because the factorization stopped when the first prime factor was found.

[CODE]
Range Known PRPs 25 digits 30 digits 35 digits
------------------------------------------------------------
1K-2K 45 14 17 20
2K-5K 26 17 20 24
5K-10K 16 12 14 16
10K-20K 10 11 13 15
20K-50K 8 13 16 18
50K-100K 7 9 11 13
100K-200K 5 9 10 12
200K-500K 5 11 13 15
500K-1M 3 8 9 11
1M-2M 3 7 9 10
2M-3M 0 4 5 6
3M-4M 0 3 3 4
4M-5M 0 2 3 3
5M-10M 0 7 8 9
[/CODE][/QUOTE]
I am not convinced by some of those numbers. 10k-20k has had complete 40 digit ecm run but is low. 20k-50k has had 35 digit and some 40 digit but is lower than your estimate for 25 digit. I realize ecm doesn't find 100% of factors upto the ecm limit but those numbers seem a little odd.

Batalov 2014-08-06 22:35

[QUOTE=Gordon;379872]Which was actually everything from about post 155 onwards, if you want to set yourself as the forum police then at least be consistent :bow:[/QUOTE]
[I]Genial[/I]!! :big grin:

Thank you for you vital grammatical correction. I've adjusted the above message, perhaps more to your liking. It must be grammatically correct now, because it is grammatically correct. (From the Department of Redundancy Department.)

Now, here's why messages from about post 155 onwards are not moved. Some (not all of them) were useless. Humor, wordplay, flirtations are fine - especially, in a thread that started to devolve into a philosophical/philological debate veering into Clintonesque defenses based on a convenient redefinition of the meaning of the word "is" (or "sex", or "probable", or whatever).

But that thread is for messages that are [B]less[/B] than useful: mud fight, name-calling, non-sequiturs, bragging, and such. Into the "less than useful" thread such messages go, regardless of the size of the brain of whoever throws :poop: in the fan.

Also, in my humble opinion, [SPOILER]Rules of MENSA:
1st RULE: You do not talk about MENSA. 2nd RULE: You DO NOT talk about MENSA. 3rd RULE: If someone says “stop” or goes limp, taps out of a fight, pay attention, they are most likely in MENSA and way more intelligent than you! (c)[/SPOILER]

kladner 2014-08-07 00:21

:goodposting::batalov:

alpertron 2014-08-07 11:34

[QUOTE=henryzz;379883]I am not convinced by some of those numbers. 10k-20k has had complete 40 digit ecm run but is low. 20k-50k has had 35 digit and some 40 digit but is lower than your estimate for 25 digit. I realize ecm doesn't find 100% of factors upto the ecm limit but those numbers seem a little odd.[/QUOTE]
The problem in your reasoning is that the 40-digit level is only complete in the cases that no factors were found. According to [URL="http://www.mersenne.org/report_ecm/default.php?txt=0&ecm_lo=10000&ecm_hi=20000&ecmnof_lo=10000&ecmnof_hi=20000"]the official report[/URL], the 35-digit level is complete up to 11.5K, and the 30-digit level is (almost) complete up to 16K. The other numbers are in the range 25 to 30 digits. So I think the estimate for 10K to 20K is OK for me. Notice that completing the n-digit level means that about 30% of the prime factors with that number of digits were not found because of the statistical nature of ECM.

In the range 20K to 50K only the 25-digit level was completed according to [URL="http://www.mersenne.org/report_ecm/default.php?txt=0&ecm_lo=20000&ecm_hi=50000&ecmnof_lo=20000&ecmnof_hi=50000"]this report[/URL].

henryzz 2014-08-07 16:38

[QUOTE=alpertron;379921]The problem in your reasoning is that the 40-digit level is only complete in the cases that no factors were found. According to [URL="http://www.mersenne.org/report_ecm/default.php?txt=0&ecm_lo=10000&ecm_hi=20000&ecmnof_lo=10000&ecmnof_hi=20000"]the official report[/URL], the 35-digit level is complete up to 11.5K, and the 30-digit level is (almost) complete up to 16K. The other numbers are in the range 25 to 30 digits. So I think the estimate for 10K to 20K is OK for me. Notice that completing the n-digit level means that about 30% of the prime factors with that number of digits were not found because of the statistical nature of ECM.

In the range 20K to 50K only the 25-digit level was completed according to [URL="http://www.mersenne.org/report_ecm/default.php?txt=0&ecm_lo=20000&ecm_hi=50000&ecmnof_lo=20000&ecmnof_hi=50000"]this report[/URL].[/QUOTE]
Good point. Sorry for the mistake.

Gordon 2014-08-08 22:43

[QUOTE=Batalov;379888][I]Genial[/I]!! :big grin:[/QUOTE]

I must bow to your far superior knowledge of the nuances of the English language

[QUOTE=Batalov;379888]Now, here's why messages from about post 155 onwards are not moved. Some (not all of them) were useless. Humor, wordplay, flirtations are fine - especially, in a thread that started to devolve into a philosophical/philological debate veering into Clintonesque defenses based on a convenient redefinition of the meaning of the word "is" (or "sex", or "probable", or whatever). [/QUOTE]

But by your reasoning anything that adds nothing to the discussion must be considered less than useful, so you fail again.

You see when you decide to set yourself up as the arbiter of what does and doesn't add value, don't be surprised that when you act inconsistently based on your prejudices that the thread holding up the Sword of Damocles is cut.

Or you could simply in future decide not to act like the thinkpol.

Batalov 2014-08-09 00:02

You are kidding yourself if you think that moderation is a police work. It is mostly waste disposal. If you always wanted to apply but were too shy to ask about it, don't be, write to Mike. Waste has to be disposed of. Spam and lunacy, too. Nonsense can stay.

The sewer thread for the waste was not always called what it is called now. It used to bear names of those prolific individuals who made most contributions. Its current name is a bit too kind (you can thank Mike). It is for posts with negative usefulness, if you insist on a better definition. "Less than useful" - not quite the same, I agree.

Some posts are deleted altogether, if this is news to you (e.g. commercial spam). Require the proverbial "CODE OF CONDUCT" if you absolutely demand to know what particular flavor of 1984 is implemented on this forum.

axn 2014-08-30 12:11

[CODE]M2327417/23915387348002001 is a probable prime![/CODE]

I'm waiting on some additional PRP checks with PFGW before submitting to PRP Top site.

alpertron 2014-08-30 13:11

[QUOTE=axn;381734][CODE]M2327417/23915387348002001 is a probable prime![/CODE]

I'm waiting on some additional PRP checks with PFGW before submitting to PRP Top site.[/QUOTE]

Congratulations!!! That's a lot bigger than the previous record holder of divisors of Mersenne numbers.

MatWur-S530113 2014-08-30 18:41

Congratulations from me, too. As Dario said this is now the largest Mersenne-cofactor known as a prp. It should be soon Nr. 1 on Henris & Renauld Lifchitz's page at [URL]http://www.primenumbers.net/prptop/searchform.php?form=%282^n-1%29%2F%3F&action=Search[/URL]
. Of course only if you reportet it there ;)


[URL="http://www.primenumbers.net/prptop/searchform.php?form=%282^n-1%29%2F%3F&action=Search"][/URL]

paulunderwood 2014-08-30 18:42

[QUOTE=axn;381734][CODE]M2327417/23915387348002001 is a probable prime![/CODE]

I'm waiting on some additional PRP checks with PFGW before submitting to PRP Top site.[/QUOTE]

Congrats :toot:

axn 2014-08-31 04:53

[QUOTE=MatWur-S530113;381755]Of course only if you reportet it there ;)[/QUOTE]
It cleared PRP tests with base=5 & 7 as well, so I have submitted it. Should show up in a couple of days, I guess.:smile:

alpertron 2014-09-05 18:10

[QUOTE=axn;381786]It cleared PRP tests with base=5 & 7 as well, so I have submitted it. Should show up in a couple of days, I guess.:smile:[/QUOTE]

I found another hit:

M270,059 = 540119 * 6481417 * 7124976157756725967 * PRP-81265

paulunderwood 2014-09-05 18:28

[QUOTE=alpertron;382224]I found another hit:

M270,059 = 540119 * 6481417 * 7124976157756725967 * PRP-81265[/QUOTE]

Congrats :smile:

MatWur-S530113 2014-09-05 18:31

Congratulation Dario!
The next one we don't need to factor anymore :max:.
If James is reading here: Is it possible to mark those prp-factors which are already proven as primes on the prp-page? That M11=23*prp2 looks somehow .... strange ^^
And on the page for the smoothest P-1-factors the case k=1 should be ignored. k=1 happens only iff the exponent of the M-number is a Sophie-Germaine-prime congruent 3 mod 4, thus this column is the same as a list of the SG-primes = 3 mod 4.

Matthias

axn 2014-09-07 13:37

They're (both) here... [url]http://www.primenumbers.net/prptop/searchform.php?form=%282^x-1%29%2F%3F&action=Search[/url]

alpertron 2014-09-20 01:53

Another probable prime:

M19121 = 917809 * 415147656569 * 1531543915081 * 27784129616513881634842031 * PRP-5701

This probable prime is in the range of a primality test.

houding 2014-09-20 05:50

On this page

[URL="http://www.mersenne.ca/prp.php?show=3&min_exponent=1&max_exponent=10%2C000%2C000"]http://www.mersenne.ca/prp.php?show=3&min_exponent=1&max_exponent=10%2C000%2C000[/URL]

1093 is also up for PRP testing.

I ran it and this is the message I got:

"M1093/known_factors is a probable prime! We4: 088A088A,00000000"

Not sure if this exponent has been PRP'd and reported before

I hope that someone else is not working on it - sorry if I spoiled your moment

Batalov 2014-09-20 06:28

[QUOTE=houding;383518]On this page

[URL]http://www.mersenne.ca/prp.php?show=3&min_exponent=1&max_exponent=10%2C000%2C000[/URL]

1093 is also up for PRP testing.[/QUOTE]
It is not up for PRP testing.

Of course, everyone can run yet another PRP test on a known [I]prime[/I], but it doesn't make it a meaningful exercise.

It is wasteful for those who are unfamiliar with the Cunningham project to go below "[URL="http://homes.cerias.purdue.edu/~ssw/cun/"]min_exponent=1300[/URL]" (or, with its extensions, below 2400).
Dario is correct that the PRP-5701 is trivially proven prime. For comparison, Wu has just [URL="http://primes.utm.edu/primes/page.php?id=118512"]recently proven[/URL] a Wagstaff prime as large as 25,000 decimal digits. An ECPP proof for any number up to, say, 10000 decimal digits is a rather trivial exercise in 2014.

houding 2014-09-20 07:19

My apologies.

I guess (maybe I should not guess:smile:) that there is more to than just putting a PRP line from that page in P95 and running it, and then getting an answer yes it is PRP or not, and then telling someone about it. My favorite RDS will probably agree :grin:

I have some homework to do if i want to know that is all about.

Adolf

Mini-Geek 2014-09-20 14:27

[QUOTE=alpertron;383494]Another probable prime:

M19121 = 917809 * 415147656569 * 1531543915081 * 27784129616513881634842031 * PRP-5701

This probable prime is in the range of a primality test.[/QUOTE]

I'm running a primality test on that now using Primo. I will report the result, or that I've abandoned it, at some point. :smile: So far, I'm at 18565/18938 bits.

alpertron 2014-09-20 18:34

I ran the P-1 factorization method with B1=200K, B2=5M on the range 900000-990000 and B1=2M, B2=50M on the range 990000-1000000, for the Mersenne numbers that already have known factors (in previous months I'd ran P-1 with B1=10M, B2=500M on all Mersenne numbers without known factors).

After finding more than 600 new prime factors, I ran PRP on the cofactors, but no new PRP appeared.

I started P-1 with B1=300K, B2=10M on the composite Mersenne numbers with exponents in the range 800000-900000.

Mini-Geek 2014-09-21 12:28

[QUOTE=Mini-Geek;383537]I'm running a primality test on that now using Primo. I will report the result, or that I've abandoned it, at some point. :smile: So far, I'm at 18565/18938 bits.[/QUOTE]

Done, submitted to [url]http://www.factordb.com/index.php?id=1100000000710088779[/url]

alpertron 2014-10-05 18:00

Stop the presses!!!

After finding more than 1700 new prime factors of Mersenne numbers in the range 700K - 1M using P-1 algorithm, I finally discovered a PRP:

M750,151 = 429934042631 * 7590093831289 * 397764574647511 * 8361437834787151 * 17383638888678527263 * PRP-225744

VBCurtis 2014-10-05 19:09

Nice find! I suppose Primo won't prove it prime for a while yet... :)

Batalov 2014-10-05 19:15

[B]Earth[/B], also known as [B]Sol 3[/B], was a giant supercomputer designed to prove the primality of this number. Designed by Deep Thought and built by the Magratheans, it was commonly mistaken for a planet, especially by the ape descendants who lived on it. It was situated far out in the uncharted backwaters of the unfashionable end of the Western Spiral Arm of the Galaxy.

Unfortunately, the Earth was destroyed by the Vogons five minutes before the program was to be completed.

VBCurtis 2014-10-05 19:18

[QUOTE=Batalov;384424][B]Earth[/B], also known as [B]Sol 3[/B], was a giant supercomputer designed to prove the primality of this number. Designed by Deep Thought and built by the Magratheans, it was commonly mistaken for a planet, especially by the ape descendants who lived on it. It was situated far out in the uncharted backwaters of the unfashionable end of the Western Spiral Arm of the Galaxy.

Unfortunately, the Earth was destroyed by the Vogons five minutes before the program was to be completed.[/QUOTE]

:tu: :tu:

Thanks for this.

axn 2014-10-12 09:57

There is something to be said for dumb luck.
[CODE]M3464473/604874508299177 is a probable prime! We4: E866B6FC,00000000
[/CODE]
Still need to do some (slow) independent check with PFGW. Ugh!

EDIT:- Anybody know how to make P95 use a different base to do the PRP test?

alpertron 2014-10-12 13:07

That's the first Mega-PRP cofactor of a Mersenne number known. Congratulations.

MatWur-S530113 2014-10-12 15:34

Congratulation, too. :smile:

Prime95 2014-10-12 15:42

[QUOTE=axn;385016]
EDIT:- Anybody know how to make P95 use a different base to do the PRP test?[/QUOTE]

Congrats. Try adding PRPBase=n to prime.txt.

paulunderwood 2014-10-12 15:45

[QUOTE=axn;385016]There is something to be said for dumb luck.
[CODE]M3464473/604874508299177 is a probable prime! We4: E866B6FC,00000000
[/CODE]
Still need to do some (slow) independent check with PFGW. Ugh!

EDIT:- Anybody know how to make P95 use a different base to do the PRP test?[/QUOTE]

Congrats. :toot:

If I were you, I would run:

[code]
./pfgw64 -tc -q"(2^3464473-1)/604874508299177"
[/code]

to get a fermat+lucas PRP test done. :smile:

axn 2014-10-13 12:07

[QUOTE=Prime95;385027]Try adding PRPBase=n to prime.txt.[/QUOTE]
Thanks. That worked (well, it isn't obvious that it worked, so I tried it first on a composite number).

[QUOTE=paulunderwood;385028]If I were you, I would run:

[code]
./pfgw64 -tc -q"(2^3464473-1)/604874508299177"
[/code]

to get a fermat+lucas PRP test done. :smile:[/QUOTE]

I have already submitted the PRP to the Top list after passing b=5,7 tests, but I will run this as well. The problem is that PFGW doesn't have suspend/resume for these tests, so I'll have to be careful not to shutdown my laptop or interrupt the test in anyway while it runs. Probably will take the better part of a day (or more) to run it, since PFGW uses the generic FFT for them. :sad:

alpertron 2014-12-11 16:29

I've just found:

M488,441 = 61543567 x 30051203516986199 x PRP-147012

c10ck3r 2014-12-12 03:54

[QUOTE=alpertron;389763]I've just found:

M488,441 = 61543567 x 30051203516986199 x PRP-147012[/QUOTE]
Anyone up for making: a) a website or b) a codebox on the first post to show what Mersenne numbers have been "fully factored" (PRPs anyways)?

Batalov 2014-12-12 03:58

There is already a [URL="http://www.primenumbers.net/prptop/searchform.php?form=%282%5En-1%29%2F%3F&action=Search"]website[/URL].

LaurV 2014-12-12 03:58

@Dario:
:tu:

(edit 2: @Batalov: also on [URL="http://www.mersenne.ca/prp.php"]James'[/URL])

TheMawn 2014-12-12 04:31

I'm a bit unfamiliar with Probable Primes. How Probable is Probable? Is there a [I]realistic[/I] chance that any of the PRP's for the "fully factored" Mersennes are actually composite?

retina 2014-12-12 04:40

[QUOTE=TheMawn;389828]Is there a [I]realistic[/I] chance that any of the PRP's for the "fully factored" Mersennes are actually composite?[/QUOTE]There is a more realistic chance you will be hit by lightning whilst simultaneously being hit by a meteor whilst simultaneously experiencing an earthquake of magnitude 9.9 on Friday the 13th at 06:06:06 in the morning.

wombatman 2014-12-12 04:41

1 Attachment(s)
:smile:

LaurV 2014-12-12 05:41

[QUOTE=TheMawn;389828]I'm a bit unfamiliar with Probable Primes. How Probable is Probable? Is there a [I]realistic[/I] chance that any of the PRP's for the "fully factored" Mersennes are actually composite?[/QUOTE]
Actually the chances are not so remote. It is true that for a number of that size to be strong pseudoprime to some bases,[URL="http://primes.utm.edu/notes/prp_prob.html"] the chances are extraordinarily low,[/URL] even lower than Retina said, but Mersenne factors don't behave like general numbers of their sizes. It is quite common for a composite mersenne factor to be 2-PSP, for example all 3 composite combinations of 233, 1103 and 2089 (prime factors of M29) are pseudoprimes base 2. This seems to happen more often for p=1 (mod 4), but it happens often enough for p=3 (mod 4), for example 514447 is a 2-PSP (is the product of 359 and 1433, prime factors of M179). Interesting enough, you can find small multiple-base-PSP very easy for small composite factors of mersenne numbers, for example 10974881 is both 2-PRP and 3-PRP, but it not a prime (it is a PSP product of 1913 and 5737, prime factors of M239).

And so on. There can be easily found small mersenne factors which are PRP to many bases, but still composite. So, there IS a remote chance that those big PRPs are still PSP. I guess we will not know very soon.

Anyhow, the result is nice, and worth of congratulations.

axn 2014-12-12 15:44

[QUOTE=LaurV;389837]Actually the chances are not so remote. It is true that for a number of that size to be strong pseudoprime to some bases,[URL="http://primes.utm.edu/notes/prp_prob.html"] the chances are extraordinarily low,[/URL] even lower than Retina said, but Mersenne factors don't behave like general numbers of their sizes. It is quite common for a composite mersenne factor to be 2-PSP, for example all 3 composite combinations of 233, 1103 and 2089 (prime factors of M29) are pseudoprimes base 2. This seems to happen more often for p=1 (mod 4), but it happens often enough for p=3 (mod 4), for example 514447 is a 2-PSP (is the product of 359 and 1433, prime factors of M179). Interesting enough, you can find small multiple-base-PSP very easy for small composite factors of mersenne numbers, for example 10974881 is both 2-PRP and 3-PRP, but it not a prime (it is a PSP product of 1813 and 5737, prime factors of M239). [/QUOTE]

Base 2 should not be used for Mersenne cofactors. They [B]all[/B] pass it.

Let p be a prime and f = 2[SUP]s[/SUP]kp+1 be a composite factor of 2^p-1 (where k is odd).

We know that 2^p == 1 (mod f). Raising both sides by k, we get

2^(pk) == 1 (mod f)
i.e. 2^((f-1)/2[SUP]s[/SUP]) == 1 (mod f)

IOW, f passes Base-2 strong PRP test.

chris2be8 2014-12-12 17:01

What PRP tests have been done on M488,441?

Chris

alpertron 2014-12-12 17:10

The default from Prime95. There is a setting in the program to change the base. If someone wants to do it, go ahead.

paulunderwood 2014-12-12 18:44

[CODE] ./pfgw64 -tc -q"(2^488441-1)/(61543567*30051203516986199)"
PFGW Version 3.7.7.64BIT.20130722.x86_Dev [GWNUM 27.11]

Primality testing (2^488441-1)/(61543567*30051203516986199) [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 5
Running N+1 test using discriminant 13, base 1+sqrt(13)
(2^488441-1)/(61543567*30051203516986199) is Fermat and Lucas PRP! (2068.5123s+0.0169s)
[/CODE]

paulunderwood 2014-12-12 20:28

I ran my own algorithm written in GMP:

[CODE]Likely prime with a=0

real 86m52.781s
user 84m37.781s
sys 1m32.782s
[/CODE]

Which means jacobiSymbol(-1,n)==-1 and (x+2)^(n+1)==5 (mod n, x^2+1).

This implies a 5-PRP test and the test: x^(n+1)==1 (mod n, x^2-(6/5)*x+1) :smile:

alpertron 2015-01-02 17:22

Another big cofactor of Mersenne number which is probable prime:

(2^440399-1)/(16210820281161978209*31518475633*880799)

Batalov 2015-04-14 08:39

Another fully factored small Mersenne:[URL="http://www.mersenne.ca/exponent.php?exponentdetails=10433"] M10433[/URL] (and [URL="http://factordb.com/index.php?query=M10433"]at FactorDB[/URL])
M10433 = 146063 · 7345550506166399 · 17578384916225511229570561 · [COLOR=Blue]407523153578238773059225963827711400649[/COLOR][SUB]<39>[/SUB] · [COLOR=Blue]P3056[/COLOR]

Batalov 2015-04-21 17:06

One more:
[URL="http://factordb.com/index.php?query=2%5E35339-1"]M35339[/URL] = 5776625742089 · 291148630508887 · 7028028455954046211351 · [COLOR="Blue"]4153830438466899077960892137[SUB]<28>[/SUB] · P10562[/COLOR]

alpertron 2015-04-21 18:04

[QUOTE=Batalov;400573]One more:
[URL="http://factordb.com/index.php?query=2%5E35339-1"]M35339[/URL] = 5776625742089 · 291148630508887 · 7028028455954046211351 · [COLOR="Blue"]4153830438466899077960892137[SUB]<28>[/SUB] · P10562[/COLOR][/QUOTE]
Excellent findings!!! It is not clear to me why the report at [url]http://www.mersenne.org/report_exponent/?exp_lo=35339&exp_hi=&full=1[/url] does not show the finder of the 28-digit prime factor.

Batalov 2015-04-21 18:35

I tried different options for submitting a factor, and all of them don't list the finder (me :-)
I am now simply submitting a single line
[QUOTE]M35339 has a factor: 4153830438466899077960892137[/QUOTE]
into manual results form - either on mersenne.ca or mersenne.org (while logged in!).

I tried pasting the whole ECM output - the result is the same (or worse - not parsed out).

It doesn't matter to me. It is a valid contender for the [URL="http://primes.utm.edu/top20/page.php?id=49"]Mersenne cofactor[/URL] top20; this does matter. The cofactor is proven before submitting, of course.

Madpoo 2015-04-21 22:01

[QUOTE=Batalov;400581]I tried different options for submitting a factor, and all of them don't list the finder (me :-)
I am now simply submitting a single line

into manual results form - either on mersenne.ca or mersenne.org (while logged in!).

I tried pasting the whole ECM output - the result is the same (or worse - not parsed out).

It doesn't matter to me. It is a valid contender for the [URL="http://primes.utm.edu/top20/page.php?id=49"]Mersenne cofactor[/URL] top20; this does matter. The cofactor is proven before submitting, of course.[/QUOTE]

I can see in the server logs where you posted that result at 2015-04-21 @ 17:08:12 UTC. George or James can probably give better guidance on why it might accept the factor but not log the result text as submitted. It may have been formed in such a way it couldn't parse all of it, or something... and now that it's a known factor it won't accept any other submissions for it, I think. But never fear, it can be manually done I'm sure.

Batalov 2015-04-22 02:13

I think for small and very old factors, this is fine (for them to be anonymous).
In Ye Goode Olde Days, factors were immaterial - only primes were the goal of the project, so they bore no name.
In fact, that's fine even for larger factors (including mine); I mean fine for me.

However, because large crowds started making a sport out of factoring alone and they need some encouragement ("look, here is _[I]my[/I]_ factor"; "hey, my factor is bigger than yours!") and they need their name attached to a factor. Which is a fair price for the amount of (GPU) work (and electricity) they put into this effort. They [I]will[/I] want to find a bigger factor and they [I]will[/I] run their computers some more. If all they will be getting out of the project would be the heated house and a constant hum from the computer, they may fall off pretty fast.

LaurV 2015-04-22 02:22

[QUOTE=Batalov;400619]
However, because large crowds started making a sport out of factoring alone and they need some encouragement ("look, here is _[I]my[/I]_ factor"; "hey, my factor is bigger than yours!") and they need their name attached to a factor. Which is a fair price for the amount of (GPU) work (and electricity) they put into this effort. They [I]will[/I] want to find a bigger factor and they [I]will[/I] run their computers some more. If all they will be getting out of the project would be the heated house and a constant hum from the computer, they may fall off pretty fast.[/QUOTE]
+1 (me, me, me, sexy me-me....) :razz:

retina 2015-04-22 02:32

[QUOTE=Batalov;400619]I think for small and very old factors, this is fine (for them to be anonymous).
In Ye Goode Olde Days, factors were immaterial - only primes were the goal of the project, ...[/QUOTE]Why you want to downgrade those poor little factors when they are precisely the thing that everyone is searching for; PRIMES! It's not the size of the primes that matters, it's what you do with them.

[size=1]It's my prime and I'll stroke it as fast and as often as I want. And besides, I was only cleaning it. Honest.[/size]

kladner 2015-04-22 02:50

:rofl: :goodposting:

Batalov 2015-04-26 03:28

[QUOTE=Batalov;400573]One more:
[URL="http://factordb.com/index.php?query=2%5E35339-1"]M35339[/URL] = 5776625742089 · 291148630508887 · 7028028455954046211351 · [COLOR="Blue"]4153830438466899077960892137[SUB]<28>[/SUB] · P10562[/COLOR][/QUOTE]
And one more:
[URL="http://factordb.com/index.php?query=2%5E41681-1"]M41681[/URL] = 1052945423 · 16647332713153 · [COLOR="Blue"]2853686272534246492102086015457[SUB][/SUB] · [URL="http://primes.utm.edu/primes/page.php?id=119809"]P12495[/URL][/COLOR][/QUOTE]

alpertron 2015-06-25 20:44

This time I found a big PRP:

(2^1790743-1)/(146840927*158358984977*3835546416767873* 20752172271489035681) is a 539014-digit PRP. See [url]http://www.mersenne.ca/exponent/1790743[/url]

axn 2015-06-26 03:26

[QUOTE=alpertron;404786]This time I found a big PRP:

(2^1790743-1)/(146840927*158358984977*3835546416767873* 20752172271489035681) is a 539014-digit PRP. See [url]http://www.mersenne.ca/exponent/1790743[/url][/QUOTE]

:w00t: Congrats!

alpertron 2015-06-26 19:18

[QUOTE=axn;404804]:w00t: Congrats![/QUOTE]

Thanks, it appears that the cofactor of M1790743 is now 35th in the ranking of the top PRP list:

[url]http://www.primenumbers.net/prptop/prptop.php?page=1#haut[/url]

alpertron 2015-07-09 14:39

The 300th (probably) completely Mersenne number factored known is M675977

The cofactor (2[sup]675977[/sup]-1)/(1686378749257*7171117283326998925471) has 203456 digits.

You can see it at: [url]http://www.mersenne.ca/exponent/675977[/url]

List of PRP Mersenne cofactors: [url]http://www.mersenne.ca/prp.php?show=1&min_exponent=1&max_exponent=10%2C000%2C000[/url]

GP2 2016-11-15 00:58

The 306th known probably-fully-factored Mersenne exponent is [URL="http://www.mersenne.ca/exponent/151013"]M151013[/URL]

It is a semiprime, whose smaller factor 61157791169561859593299975690769 was discovered October 28.

This is too large for primality certification. All probable-prime cofactors for exponents 63703 and below have been proven prime (274 out of the 306), while all the larger ones are only (highly) probably prime.

The list of known Mersenne primes and fully-factored or probably-fully-factored exponents can be found at [url]http://www.mersenne.ca/prp.php[/url]



The 305th was [URL="http://www.mersenne.ca/exponent/5233"]M5233[/URL], with 5 factors plus a cofactor. The 304th was [URL="http://www.mersenne.ca/exponent/822971"]M822971[/URL], with 3 factors + cofactor.

The 303rd was [URL="http://www.mersenne.ca/exponent/5240707"]M5240707[/URL], the current record holder. It is a semiprime, whose smaller factor 75392810903 was discovered a long time ago by trial-factoring, but was not PRP tested until late July of this year.

axn 2016-11-15 03:03

[QUOTE=GP2;447216]All probable-prime cofactors for exponents 63703 and below have been proven prime (274 out of the 306), while all the larger ones are only (highly) probably prime.[/QUOTE]

The record for ECPP proof is about 31k digits ([url]http://primes.utm.edu/top20/page.php?id=27[/url]). That means the next four PRPs [C](M82939 - PRP-24938, M86137 - PRP-25896, M86371 - PRP-25984, M87691 - PRP-26371)[/C] are "provable" (with some serious time commitment.)

GP2 2016-12-05 18:16

The 307th fully-factored-or-probably-fully-factored Mersenne number is [URL="http://www.mersenne.ca/exponent/25243"]M25243[/URL].

It has four factors plus a PRP cofactor. The fourth factor 449245236879223161338352589831 was found using P−1 stage 1 with B1=500000000.

This is within range of primality testing by Primo, if someone wants to tackle it.

paulunderwood 2016-12-05 18:22

[QUOTE=GP2;448486]The 307th fully-factored-or-probably-fully-factored Mersenne number is [URL="http://www.mersenne.ca/exponent/25243"]M25243[/URL].

It has four factors plus a PRP cofactor. The fourth factor 449245236879223161338352589831 was found using P−1 stage 1 with B1=500000000.

This is within range of primality testing by Primo, if someone wants to tackle it.[/QUOTE]

It will be a UTM submission: [URL="http://primes.utm.edu/top20/page.php?id=49"]top20[/URL] :smile:

Edit, I'll prove it prime with Primo -- is there someone I should co-credit?

ATH 2016-12-05 18:48

Do we want PRP status of co-factors logged in primenet as well?

I'm not sure how mersenne.ca is updated? is it getting info from primenet via scripts running on primenet?

Does mersenne.ca contain other information missing from primenet besides the PRP information? Like extra factors for exponents besides the first one, that are not in primenet?

GP2 2016-12-05 23:04

[QUOTE=ATH;448494]Do we want PRP status of co-factors logged in primenet as well?

I'm not sure how mersenne.ca is updated? is it getting info from primenet via scripts running on primenet?

Does mersenne.ca contain other information missing from primenet besides the PRP information? Like extra factors for exponents besides the first one, that are not in primenet?[/QUOTE]

Primenet does not store any information about which exponents are fully-factored or probably-fully-factored. It should, or at least we should make sure that fully-factored exponents are eliminated from consideration for any further factoring by ECM or other method.

mprime/Prime95 can do PRP testing, but it does not send the results to Primenet, nor can these results be manually submitted to Primenet. These results have to be manually submitted to Mersenne.ca, at [url]http://www.mersenne.ca/index.php?submitresults=1[/url]

Mersenne.ca is the central repository for PRP information on Mersenne exponents, with the full list at [url]http://www.mersenne.ca/prp.php[/url]

All of the PRP exponents up to and including M63,703 have had their cofactors certified prime with Primo or some other means. All the higher exponents are only probably-fully-factored, albeit with very high confidence.

Ranges for PRP testing can be reserved at [url]http://www.mersenne.ca/prp.php?assigned_distribution=1[/url] by clicking on the blue links and then clicking on the button in the resulting page. However, that page does not really document clearly that results need to be submitted at [url]http://www.mersenne.ca/index.php?submitresults=1[/url]

Mersenne.ca pulls updates daily from Primenet. Both of these sites should have identical information about residues and factors, including second and higher factors. A few months ago, a few dozen inconsistencies were discovered between the two databases, but those were reconciled and presumably there is no longer an issue.

One difference is that Mersenne.ca has factors data for exponents up to 4.29 billion, whereas Primenet only stores factors data for exponents up to 1.00 billion.

paulunderwood 2016-12-07 14:49

[QUOTE=paulunderwood;448489]It will be a UTM submission: [URL="http://primes.utm.edu/top20/page.php?id=49"]top20[/URL] :smile:

Edit, I'll prove it prime with Primo -- is there someone I should co-credit?[/QUOTE]

[URL="http://primes.utm.edu/primes/page.php?id=122574"]Submission[/URL] to The Prime Pages.

I submitted the certificate to FactorDB. Can some please provide me with a link to it so I can include the link in TPP database :smile:

Batalov 2016-12-07 15:45

[QUOTE=paulunderwood;448489]
... is there someone I should co-credit?[/QUOTE]
GP2?

GP2 2016-12-07 18:46

[QUOTE=Batalov;448667]GP2?[/QUOTE]

No need...

paulunderwood 2016-12-07 20:31

I have added a link at TPP to the cofactor certificate at FactorDB. Now [url]http://www.mersenne.ca/exponent/25243[/url] can be updated from "probable prime" to "prime"

GP2 2016-12-11 09:02

The 308th known probably-fully-factored Mersenne exponent is [URL="http://www.mersenne.ca/exponent/25933"]M25933[/URL].

It has three factors plus the PRP cofactor, and its latest 40-digit factor 5589137403017310421606050379256829183569 was found using P-1 with B1=500000000, B2=19081568754210, using mprime for stage 1 and gmp-ecm for stage 2.

Like the last time, this needs a Primo certificate.

Jayder 2016-12-11 10:24

[QUOTE=GP2;448932]The 308th known probably-fully-factored Mersenne exponent is [URL="http://www.mersenne.ca/exponent/25933"]M25933[/URL].

It has three factors plus the PRP cofactor, and its latest 40-digit factor 5589137403017310421606050379256829183569 was found using P-1 with B1=500000000, B2=19081568754210, using mprime for stage 1 and gmp-ecm for stage 2.

Like the last time, this needs a Primo certificate.[/QUOTE]
Good going. If it's alright, I'd like to do the certificate for this one. It will be done within the day.

GP2 2016-12-11 11:34

[QUOTE=Jayder;448936]Good going. If it's alright, I'd like to do the certificate for this one. It will be done within the day.[/QUOTE]

Well, I guess you called dibs.

GP2 2016-12-13 00:48

And the hits just keep on coming:

[URL="http://www.mersenne.ca/exponent/4834891"]M4834891[/URL]/1701881633/70659688575577 is a probable prime

This is the 309th fully-or-probably-fully factored Mersenne exponent, and the second largest after M5240707.

This is an unexpected flurry of new PRP results.

The factors were discovered long ago, but now the wavefront of PRP testing has reached the 4.8M range...

paulunderwood 2016-12-13 02:51

[QUOTE=GP2;449044]
[URL="http://www.mersenne.ca/exponent/4834891"]M4834891[/URL]/1701881633/70659688575577 is a probable prime
.[/QUOTE]

FWIW:

[CODE]time ../../coding/gwnum/lucasPRP M4834891-cofactor 1 2 4834891 -1
Lucas testing on x^2 - 3*x + 1 ...
Is Lucas PRP!

real 64m3.983s
user 228m46.452s
sys 4m39.080s[/CODE]

[URL="http://www.mersenneforum.org/showpost.php?p=435694&postcount=14"]Reference program[/URL] :geek:

Jayder 2016-12-13 04:49

[QUOTE=GP2;448932]The 308th known probably-fully-factored Mersenne exponent is [URL="http://www.mersenne.ca/exponent/25933"]M25933[/URL].

It has three factors plus the PRP cofactor, and its latest 40-digit factor 5589137403017310421606050379256829183569 was found using P-1 with B1=500000000, B2=19081568754210, using mprime for stage 1 and gmp-ecm for stage 2.

Like the last time, this needs a Primo certificate.[/QUOTE]
Forgot to post this yesterday: [url]http://factordb.com/index.php?id=1100000000886495500[/url]

Is it suggested that I submit this to the Prime Pages? I will have to make an account and figure it out if so.

paulunderwood 2016-12-13 05:23

[QUOTE=Jayder;449055]Forgot to post this yesterday: [url]http://factordb.com/index.php?id=1100000000886495500[/url]

Is it suggested that I submit this to the Prime Pages? I will have to make an account and figure it out if so.[/QUOTE]

Yes. It is a top20 proven Mersenne cofactor :smile:

GP2 2016-12-21 22:29

[URL="http://factordb.com/index.php?query=2%5E53381-1"]factordb is showing that M53381 is fully-factored[/URL]

As of this writing, it has [URL="http://www.mersenne.ca/exponent/53381"]not been tested yet at mersenne.ca[/URL]

It has three factors plus the PRP cofactor. I found the third factor a couple of days ago using ECM. This is the 310th known fully-factored or probably-fully-factored Mersenne exponent.

This one will be a bit challenging to certify primality. Who wants to try it?

paulunderwood 2016-12-22 02:09

[QUOTE=GP2;449724][URL="http://factordb.com/index.php?query=2%5E53381-1"]factordb is showing that M53381 is fully-factored[/URL]

As of this writing, it has [URL="http://www.mersenne.ca/exponent/53381"]not been tested yet at mersenne.ca[/URL]

It has three factors plus the PRP cofactor. I found the third factor a couple of days ago using ECM. This is the 310th known fully-factored or probably-fully-factored Mersenne exponent.

This one will be a bit challenging to certify primality. Who wants to try it?[/QUOTE]

I'll pick it up. It will take about four weeks on a 6 core 1090T. Until then... :smile:

axn 2016-12-22 03:28

[QUOTE=GP2;449724]As of this writing, it has [URL="http://www.mersenne.ca/exponent/53381"]not been tested yet at mersenne.ca[/URL][/QUOTE]

It is now.

GP2 2017-03-03 04:25

Mersenne.ca is showing that M[URL="http://www.mersenne.ca/exponent/84211"]84211[/URL]/1347377/31358793176711980763958121/3314641676042347824169591561 is a probable prime.

It is the 311th known fully-factored or probably-fully-factored Mersenne exponent. The third factor was discovered a few days ago, the results.txt actually reported "Cofactor is a probable prime!" but I didn't notice it at the time.

It is a bit too large for primality certification to be feasible in a reasonable amount of time. Note that certification of the next-lower M82939 has not been attempted yet, as far as I know. The largest certified fully-factored exponent is M63703.

There are now five known probably-fully-factored Mersenne exponents in the 80k range (82939, 84211, 86137, 86371, 87691), not to mention the prime M86243, but none in the 70k range.

paulunderwood 2017-03-03 06:02

[QUOTE=GP2;454160]Mersenne.ca is showing that M[URL="http://www.mersenne.ca/exponent/84211"]84211[/URL]/1347377/31358793176711980763958121/3314641676042347824169591561 is a probable prime.

It is the 311th known fully-factored or probably-fully-factored Mersenne exponent. The third factor was discovered a few days ago, the results.txt actually reported "Cofactor is a probable prime!" but I didn't notice it at the time.

It is a bit too large for primality certification to be feasible in a reasonable amount of time. Note that certification of the next-lower M82939 has not been attempted yet, as far as I know. The largest certified fully-factored exponent is M63703.

There are now five known probably-fully-factored Mersenne exponents in the 80k range (82939, 84211, 86137, 86371, 87691), not to mention the prime M86243, but none in the 70k range.[/QUOTE]

On a many core/socket system, these can be proved in a "reasonable amount of time", because a proof with ECPP (using Primo) is [URL="https://en.wikipedia.org/wiki/Embarrassingly_parallel"]embarrassingly parallel[/URL].

GP2 2017-03-03 07:35

[QUOTE=paulunderwood;454164]On a many core/socket system, these can be proved in a "reasonable amount of time", because a proof with ECPP (using Primo) is [URL="https://en.wikipedia.org/wiki/Embarrassingly_parallel"]embarrassingly parallel[/URL].[/QUOTE]

Well, feel free to tackle it after M53381... :smile: although M82939 might have priority.

Odd that no PRPs were found in the 70k range or the upper half of 60k. I did find factors there but no PRPs resulted.

paulunderwood 2017-03-08 18:49

[QUOTE=GP2;454165]Well, feel free to tackle it after M53381... :smile: although M82939 might have priority.

Odd that no PRPs were found in the 70k range or the upper half of 60k. I did find factors there but no PRPs resulted.[/QUOTE]

I decline your offer of testing those hefty numbers :wink:

I have completed the certificate of the M53381 cofactor and have submitted it to both [URL="http://primes.utm.edu/primes/page.php?id=123121"]UTM's The Prime Pages[/URL] and factordb. Please update your records :smile:

VictordeHolland 2017-03-08 22:01

[QUOTE=paulunderwood;454500]I decline your offer of testing those hefty numbers :wink:

I have completed the certificate of the M53381 cofactor and have submitted it to both [URL="http://primes.utm.edu/primes/page.php?id=123121"]UTM's The Prime Pages[/URL] and factordb. Please update your records :smile:[/QUOTE]
Seems like its already updated, rank 4 on the Mersenne cofactor list, congrats!

[quote][INDENT][URL="http://primes.utm.edu/top20/page.php?id=27"]Elliptic Curve Primality Proof[/URL] (archivable [URL="http://primes.utm.edu/top20/home.php#archivable"]*[/URL]) Prime on list: [B]no[/B], rank [B]41[/B]
Subcategory: "ECPP"

[URL="http://primes.utm.edu/top20/page.php?id=49"]Mersenne cofactor[/URL] (archivable [URL="http://primes.utm.edu/top20/home.php#archivable"]*[/URL]) Prime on list: [B]yes[/B], rank [B]4[/B]
Subcategory: "Mersenne cofactor"

[/INDENT][/quote]

GP2 2017-03-10 00:30

The 312th fully-factored or probably-fully-factored Mersenne exponent is [URL="http://www.mersenne.ca/exponent/175631"]M175631[/URL]

It has two smaller factors plus a PRP cofactor. The second factor was found by user TJAOI on March 3. I'm not sure who ran the PRP test.

GP2 2017-03-10 01:18

Someone has been running hundreds of ECM curves on [URL="https://www.mersenne.org/report_exponent/?exp_lo=53381&exp_hi=&full=1&ecmhist=1"]M53381[/URL] in the past few days, even though it has been known to be probably-fully-factored since December, and certified fully-factored a few days ago... hmmm...

Probably-fully-factored and fully-factored exponents ought to be removed from the ECM report listings. Some already have been but some haven't. Right now, [URL="https://www.mersenne.org/report_ecm/?txt=0&ecm_lo=1&ecm_hi=1&ecmnof_lo=53300&ecmnof_hi=53400"]53381 still appears there[/URL].

Batalov 2017-03-10 03:35

[QUOTE=GP2;454567]Someone has been running hundreds of ECM curves on [URL="https://www.mersenne.org/report_exponent/?exp_lo=53381&exp_hi=&full=1&ecmhist=1"]M53381[/URL] in the past few days ...[/QUOTE]
The proverbial disbelievers, right? :rolleyes:


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

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