mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2021-04-21, 15:04   #12
axn
 
axn's Avatar
 
Jun 2003

120358 Posts
Default

Serge, one question. Does LLR use standard PRP test, 3^(N-1) == 1, or does it do 3^10^p == 3^10?
axn is offline   Reply With Quote
Old 2021-04-21, 15:25   #13
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17×563 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Good one!

Maybe it will be clear when the PRP Top entry becomes visible, but what types of PRP tests has this one "passed", as of now?

/JeppeSN
We finished 3-PRP, 7-PRP, 11-PRP, 13-PRP (and their SPRP chasers are still running, the Lucas+Frobenius test phases -- they are ~10x slower even on 32 threads).
Batalov is offline   Reply With Quote
Old 2021-04-21, 15:28   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

53×73 Posts
Default

Quote:
Originally Posted by Batalov View Post
We finished 3-PRP, 7-PRP, 11-PRP, 13-PRP (and their SPRP chasers are still running, the Lucas test phase).
I am currently testing it for Lucas over x^2-4*x+1
paulunderwood is offline   Reply With Quote
Old 2021-04-21, 15:33   #15
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

957110 Posts
Default

Quote:
Originally Posted by axn View Post
Serge, one question. Does LLR use standard PRP test, 3^(N-1) == 1, or does it do 3^10^p == 3^10?
I'll have to doublecheck in the source, but as far as I remember the code does the honest modular exponentiation of b^(N-1) using (in this case) mod (10^p-1) and then converts to giants and does a slow/careful mod ((10^p-1)/9) and expects unit.
For N not being near a power of 2, there is no expected savings of doing exponentiation to N-1, to N or to N+1 (for Mersennes, for example). N-1 is just a binary string of both "1"s and "0"s, no difference from N or even 9N.
Batalov is offline   Reply With Quote
Old 2021-04-21, 16:01   #16
axn
 
axn's Avatar
 
Jun 2003

19·271 Posts
Default

Quote:
Originally Posted by Batalov View Post
For N not being near a power of 2, there is no expected savings of doing exponentiation to N-1, to N or to N+1 (for Mersennes, for example). N-1 is just a binary string of both "1"s and "0"s, no difference from N or even 9N.
But 9N+1 = 10^p = 5^p*2^p has a lot more zeros than 1s. Honestly, I don't know what is the impact of simple squaring vs squaring*3. Once upon a time, I recall there being low single digit % difference in performance between LLR and PRP on Riesel numbers (all 1s), but I could be mistaken.
axn is offline   Reply With Quote
Old 2021-04-21, 16:07   #17
Cybertronic
 
Cybertronic's Avatar
 
Jan 2007
Germany

38110 Posts
Default

Congratulation , this is so cool !
Cybertronic is online now   Reply With Quote
Old 2021-04-21, 16:18   #18
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17×563 Posts
Thumbs up

Quote:
Originally Posted by axn View Post
But 9N+1 = 10^p = 5^p*2^p has a lot more zeros than 1s. Honestly, I don't know what is the impact of simple squaring vs squaring*3. Once upon a time, I recall there being low single digit % difference in performance between LLR and PRP on Riesel numbers (all 1s), but I could be mistaken.
True, but we might hit some other 9th root of unity. (we can then rule the false positive out, of course, with subsequent traditional tests; no false negatives should result).
Worth trying; interesting. llr is not doing it now, but we can hack a patch, and test the speed gain (if it exists).
Batalov is offline   Reply With Quote
Old 2021-04-21, 16:36   #19
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

Quote:
Originally Posted by Batalov View Post
It is R5794777, and perhaps unsurprisingly it has 5794777 decimal digits (all "1"s).
Yaay! Congrats Serge and Ryan!

LaurV is offline   Reply With Quote
Old 2021-04-21, 17:19   #20
axn
 
axn's Avatar
 
Jun 2003

19×271 Posts
Default

Quote:
Originally Posted by Batalov View Post
True, but we might hit some other 9th root of unity. (we can then rule the false positive out, of course, with subsequent traditional tests; no false negatives should result).
Worth trying; interesting. llr is not doing it now, but we can hack a patch, and test the speed gain (if it exists).
Worth pointing out: after computing 3^5^p, the remaining p squarings can be protected with GEC.

PS:- In theory, even the 3^5^p could be protected by GEC, but it will cost 50% extra -- worth it only if used as an alternative for double checks
axn is offline   Reply With Quote
Old 2021-04-21, 20:05   #21
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

27268 Posts
Default

Quote:
Originally Posted by axn View Post
Worth pointing out: after computing 3^5^p, the remaining p squarings can be protected with GEC.

PS:- In theory, even the 3^5^p could be protected by GEC, but it will cost 50% extra -- worth it only if used as an alternative for double checks
Much less extra cost, say you want a^(b^n) mod N using error checking, then choose e>0 and set a larger new base: B=b^e, for simplicity assume that e divides n, then

a^(b^n)=a^(B^(n/e))

and you can do the error checking using this new base, if we count only the squarings then the extra cost of using B>2 is
ceil(log2(B))/log2(B)-1 in 1 part.
[for B=2 this is zero].

One small drawback here is that when you would want to choose very large e so large B to lower the overhead then you can't error check that very frequently.
R. Gerbicz is offline   Reply With Quote
Old 2021-04-21, 20:51   #22
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

3·31 Posts
Smile

Quote:
Originally Posted by Batalov View Post
The last two known repunits were found back in 2007. Welcome, the year 2021.

With Ryan Propper, we decided to give a boost to the project which changed a few homes over the years. (We don't know the latest live site. skoberne site is defunct. Perhaps, Kurt's subpage.)

So, we might go up to p<10,000,000 and so far found one. We are using MT llr and gr-mfaktc to 64 bits for presieve.
It is submitted to PRPtop (but has not showed up yet), to Mathworld and to UTM (in category of thesaurus of primes). Wikipedia and OEIS 004023 will be updated when sourced with other pages.

It is R5794777, and perhaps unsurprisingly it has 5794777 decimal digits (all "1"s).

It also happens to be the largest currently known PRP.

Congratulations on finding the next repunit prime, well done.
I can give some infos on the current repunit search that our team is doing:


I extended the original database from skoberne (with complete new structure), but it is not publicly available. So every few weeks I send a new excerpt to Kurt, so his website Kurt's subpage is officially the new live site, but so far only up to n=6000000. The database itself contains all prime exponents up to 10000000, including known factors, Res64 and/or Res2048 values plus the current bit-depth of sieving. If somebody is interested I can send him a complete dump, or extract the needed information, just send me a PM.

As of today we have tested all of the exponents up to 4880957, with the exception of very few numbers around 4300459 (still waiting for the results of one user).

So how was the new number found, by random selection or systematic search? If you are still in favor of a systematic search we could combine our efforts. Currently I am doing a manual reservation of exponents via email, nothing like the professional search for Mersenne primes.

I would also suggest that you try out running the PRP test with prime95/mprime, it should be faster than llr. E.g. running the test for the found prp has the worktodo entry
PRP=1,10,5794777,-1,99,0,3,1,"9"
I am currently running the test with mprime on an 8 Core AMD, will post the results here once finished.


Cheers,
Danilo


PS.: @Batalov, I didn't see your comment on LLR vs mprime, only later. I should compare again, last time I tested mprime was like 10% faster. Also I am using it to get the Res2048 value, does LLR has the similar option to get the long residue?

Last fiddled with by MrRepunit on 2021-04-21 at 21:13 Reason: llr vs mprime was already discussed
MrRepunit is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalized Repunit primes Bob Underwood Math 12 2020-10-11 20:01
Some CADO-NFS Work At Around 175-180 Decimal Digits EdH CADO-NFS 127 2020-10-07 01:47
Integers congruent to last two decimal digits mod 23 enzocreti enzocreti 1 2020-03-03 18:38
Twin Primes with 128 Decimal Digits tuckerkao Miscellaneous Math 2 2020-02-16 06:23
records for primes 3.14159 Information & Answers 8 2018-12-09 00:08

All times are UTC. The time now is 18:43.


Sat Oct 23 18:43:36 UTC 2021 up 92 days, 13:12, 0 users, load averages: 0.80, 1.00, 1.16

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