mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Probability & Probabilistic Number Theory

Reply
 
Thread Tools
Old 2017-11-25, 22:36   #12
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

If anyone was seriously interested in finding a PRP larger that the largest known prime, then consider this.
There are no numbers that can be tested faster than Mersenne's (within a fraction of a % of a %, that is your "less iterations to run for the cofactor" which is negligible if you think for a minute).

To be even remotely competitive with GIMPS in terms of size and plausibility, the candidates have to have three properties:
(a) as fast to test as a Mersenne number.
(b) as probable to find as a Mersenne number (that means sieved just as deep, that means factors are restricted) - this is a must. If your project can sieve to 36 bits and GIMPS to 72, then you already lost.
(c) finally, the project has a compute throughput as large as GIMPS -- but for far less glory.

Conditions (a+b) will mean that candidates have to be Mersenne cofactors, Wagstaff's, GFN cofactors or some cyclotomic cofactors (or straight with power not 3-smooth).
Gaussian-Mersennes and Eisenstein-Mersennes (and their cofactors) are not contenders (they fail condition (a), though they do pass condition (b)) - failing condition (a) by a factor of 2 is as bad as failing condition (b) by a factor of 2 - in both cases in order to simply keeping up with GIMPS you have to have 2x more power. But then - why? You could just as well work with GIMPS even if you consider getting half of credit with GIMPS getting the other half.
Batalov is offline   Reply With Quote
Old 2017-11-25, 23:37   #13
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·271 Posts
Default

Thank you very much for the detailed analysis Batalov, much appreciated.
On a somewhat related benchmark

Quote:
The largest known Carmichael number of this form was found by H. Dubner in 1996 and has 1025 digits.

https://archive.lib.msu.edu/crcmath/...ath/c/c060.htm

Last fiddled with by a1call on 2017-11-25 at 23:38
a1call is offline   Reply With Quote
Old 2017-11-26, 14:35   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

66328 Posts
Default

Quote:
Originally Posted by a1call View Post
Thank you very much for the detailed analysis Batalov, much appreciated.
On a somewhat related benchmark
Quote:
The largest known Carmichael number of this form was found by H. Dubner in 1996 and has 1025 digits.

https://archive.lib.msu.edu/crcmath/...ath/c/c060.htm
Actually, this seems to be more than a bit garbled. The following 1996 post to the NMBRTHRY Listserv from Harvey Dubner himself, tells a different story. He found a couple of Carmichael numbers of the special "universal form"

U3 = PQR = (6M + 1)(12M+1)(18M + 1)

in which the prime factors P, Q, and R each have 1025 decimal digits. The post also refers to Carmichael numbers with "millions of digits."

Carmichael number record
Dr Sardonicus is offline   Reply With Quote
Old 2017-11-26, 16:48   #15
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·1,741 Posts
Default

A bit more digging turned up a 1998 post by Dubner with some larger examples of the form

(6M + 1)(12M + 1)(18M + 1):

3-component Carmichael Numbers

There was an error in a table, which was the subject of a

Correction

The smallest Carmichael number of this form, 7*13*19, is 1729, which is the smallest Carmichael number whose prime factors form a finite arithmetic progression, as well as being (as noted in the hardy-Ramanujan "taxicab number" anecdote) the smallest number that is the sum of two cubes in two different ways (10^3 + 9^3 and 1^3 + 12^3).

Also, a 1996 paper with an algorithm for producing really large Carmichael numbers:

A NEW ALGORITHM FOR CONSTRUCTING LARGE CARMICHAEL NUMBERS
Dr Sardonicus is offline   Reply With Quote
Old 2017-11-26, 19:45   #16
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·271 Posts
Default

Thank you very much for the corrections and extra research DS.
You are a very valuable member of this board.
a1call is offline   Reply With Quote
Old 2017-11-26, 19:51   #17
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7×271 Posts
Default

What is the largest PRP range that can be found using Fermat's Little Theorem (base 2) on Pari GP running on a custom pc with x GBs of memory?
Another way of asking the same question is:
What is the largest practical p for which
2^(p- 1) can be calculated?

(Thank you in advance)^2

Last fiddled with by a1call on 2017-11-26 at 19:54
a1call is offline   Reply With Quote
Old 2017-11-26, 20:01   #18
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by a1call View Post
What is the largest PRP range that can be found using Fermat's Little Theorem (base 2) on Pari GP running on a custom pc with x GBs of memory?
Please don't use gp for this; it's not built for it and it will perform poorly. There are better tools like PFGW.

I love PARI/GP but this is like pounding nails with a Swiss Army knife.
CRGreathouse is offline   Reply With Quote
Old 2017-11-26, 21:17   #19
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

Quote:
Originally Posted by a1call View Post
Another way of asking the same question is:
What is the largest practical p for which
2^(p- 1) can be calculated?
Define practical.

You have a better chance to be struck by a lightning than finding a PRP with > 10M decimal digits. Do you feel particularly lucky?

You can run PRPs on the >100,000,000-digit Mersenne cofactors (candidates that had a factor or two found). In a few CPU years you will get the result.
Take 2^332200007-1 / 272240898059289853159 and run the PRP test. It is trivial:
Code:
# worktodo.txt
PRP=1,2,332200007,-1,"272240898059289853159"
If you do feel lucky, then one candidate should be enough. When done, take the next one.
You can take even larger cofactors.
Batalov is offline   Reply With Quote
Old 2017-11-26, 22:36   #20
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7·271 Posts
Default

Point well taken. I wasn't considering the low probability of prime/PRP in the high ranges.

But then again I am more interested in understanding the different mechanics of the concept rather actually attempting to find a large PRP.

It's good to know the upper limits of what arbitrary-precision calculators can work at then consider the astronomically low possibility of finding a candidate.
a1call is offline   Reply With Quote
Old 2017-11-26, 22:41   #21
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

189710 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Please don't use gp for this; it's not built for it and it will perform poorly. There are better tools like PFGW.

I love PARI/GP but this is like pounding nails with a Swiss Army knife.
I like that reference

http://www.periodictable.com/Samples/026.55/s13.JPG


You know what they say:

You can't teach an old d d d distinguished gentleman new tricks.


PFGW, at the moment is nothing but an acronym to me.
I will have to research it.
Thank you.
a1call is offline   Reply With Quote
Old 2017-11-26, 23:33   #22
GP2
 
GP2's Avatar
 
Sep 2003

22×3×5×43 Posts
Default

Quote:
Originally Posted by Batalov View Post
Define practical.

You have a better chance to be struck by a lightning than finding a PRP with > 10M decimal digits. Do you feel particularly lucky?

You can run PRPs on the >100,000,000-digit Mersenne cofactors (candidates that had a factor or two found). In a few CPU years you will get the result.
Take 2^332200007-1 / 272240898059289853159 and run the PRP test. It is trivial:
Code:
# worktodo.txt
PRP=1,2,332200007,-1,"272240898059289853159"
If you do feel lucky, then one candidate should be enough. When done, take the next one.
You can take even larger cofactors.
Or just set WorkPreference=154 in prime.txt, and then mprime/Prime95 will automatically assign you 100-million digit PRP tests.

If you're feeling less ambitious, then use 150 for first-time PRP tests or 152 for world-record PRP tests. These two choices currently amount to the same thing, at least until the next Mersenne prime is found.

It goes without saying that you should be running the latest version, 29.4b5

Last fiddled with by GP2 on 2017-11-26 at 23:34
GP2 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Largest known k? Uncwilly Data 38 2009-07-17 05:39
Largest known prime Unregistered Information & Answers 24 2008-12-13 08:13
Largest 64 bit prime? amcfarlane Math 6 2004-12-26 23:15
largest factor ,i think. heryu Miscellaneous Math 10 2004-09-08 11:15
need Pentium 4s for 5th largest prime search (largest proth) wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 21:59.

Mon Sep 28 21:59:16 UTC 2020 up 18 days, 19:10, 0 users, load averages: 1.76, 1.68, 1.64

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.