mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2019-10-12, 12:29   #1
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×3×227 Posts
Cool Question about these fascinating primes

Quote:
Originally Posted by Cruelty View Post
101*2^7345194-1 is prime! (2211126 decimal digits)
Question: What are these being ran with to get this format? It looks fascinating.
storm5510 is offline   Reply With Quote
Old 2019-12-21, 20:13   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

102248 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Question: What are these being ran with to get this format? It looks fascinating.
Sorry for overlooking your question for so long. We run LLR to test k*2^n-1 or k*2^n+1 formats (and quite a few others). If LLR doesn't handle it, PFGW does.

Also, 231*2^2335281-1 is prime! 702992 digits.
VBCurtis is online now   Reply With Quote
Old 2020-01-23, 00:39   #3
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2·3·227 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Sorry for overlooking your question for so long. We run LLR to test k*2^n-1 or k*2^n+1 formats (and quite a few others). If LLR doesn't handle it, PFGW does.

Also, 231*2^2335281-1 is prime! 702992 digits.
Actually, I had forgotten about this. I have been experimenting with PFGW. There is a lot to read. It is picky about its input formats.
storm5510 is offline   Reply With Quote
Old 2020-01-23, 14:42   #4
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×3×227 Posts
Default

I was learning to use the ABC2 input type for PFGW early this morning when I came up with these:

Code:
10*2^13509-1 is 3-PRP! (0.0290s+0.0015s)
10*2^21737-1 is 3-PRP! (0.0676s+0.0011s)
10*2^25623-1 is 3-PRP! (0.0805s+0.0011s)
I am not sure about the meaning of "3-" in this instance. I know how to calculate the number of digits in 2p-1. How that translates to something in this format, I do now know.


Thanks.
storm5510 is offline   Reply With Quote
Old 2020-01-23, 17:21   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

Quote:
Originally Posted by storm5510 View Post
I was learning to use the ABC2 input type for PFGW early this morning when I came up with these:

Code:
10*2^13509-1 is 3-PRP! (0.0290s+0.0015s)
10*2^21737-1 is 3-PRP! (0.0676s+0.0011s)
10*2^25623-1 is 3-PRP! (0.0805s+0.0011s)
I am not sure about the meaning of "3-" in this instance. I know how to calculate the number of digits in 2p-1. How that translates to something in this format, I do now know.


Thanks.
These are roughly 4200, 7000 and 8500 digits. You can get the exact values with pari/GP with length(decimal(10*2^13509-1)).

"3-PRP" means it passes Fermat's Little Theorem test: 3^(N-1)=1 mod N, which is necessary but not sufficient for a prime. With PFGW you can specify small bases with the -b switch.
paulunderwood is offline   Reply With Quote
Old 2020-01-23, 20:46   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

17·197 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
These are roughly 4200, 7000 and 8500 digits. You can get the exact values with pari/GP with length(decimal(10*2^13509-1)).

"3-PRP" means it passes Fermat's Little Theorem test: 3^(N-1)=1 mod N, which is necessary but not sufficient for a prime. With PFGW you can specify small bases with the -b switch.
The number of decimal digits in 10*2^13509-1 would also be 2 + floor(13509*log(2)/log(10)).

It is possible AFAIK that "PRP" means that N "passes" Rabin-Miller to base 3; in this case, in addition to

3^(N-1) == 1 (mod N), that

3^((N-1)/2) == 1 or -1 (mod N).

If N satisfied the first condition but not the second, of course, a proper factorization of N would be in hand.

Last fiddled with by Dr Sardonicus on 2020-01-23 at 20:49 Reason: add qualifier
Dr Sardonicus is offline   Reply With Quote
Old 2020-01-23, 21:12   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000010112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
The number of decimal digits in 10*2^13509-1 would also be 2 + floor(13509*log(2)/log(10)).
[/quote[

This is certainly less resources hungry than the method I gave.
[quote[

It is possible AFAIK that "PRP" means that N "passes" Rabin-Miller to base 3; in this case, in addition to

3^(N-1) == 1 (mod N), that

3^((N-1)/2) == 1 or -1 (mod N).

If N satisfied the first condition but not the second, of course, a proper factorization of N would be in hand.
PFGW does not do a M-R, only Fermat PRP. From pfgwdoc.txt:

Quote:
A.3.1 Fermat's method
Fermat's method is NOT a proof, but more like a quick indicator that a
number might be prime.
The program LLR is more sophisticated in this respect.

Please tell us how one gets a factor from the conditions you mention above,

Last fiddled with by paulunderwood on 2020-01-23 at 21:14
paulunderwood is offline   Reply With Quote
Old 2020-01-23, 22:37   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

17·197 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Please tell us how one gets a factor from the conditions you mention above,
If

3^(N-1) == 1 (mod N), and

3^((N-1)/2) == M (mod N), then

M^2 == 1 (mod N), so (assuming 1 <= M < N)

we have (M - 1)*(M + 1) == 0 (mod N).

If M == 1 (mod N) or M == -1 (mod N), one of the factors is 0 (mod N).

Otherwise, M - 1 =/= 0 (mod N), M + 1 =/= 0 (mod N), and (M+1)*(M+1) == 0 (mod N). Since gcd(M-1, M+1) | 2 then, assuming N is odd, we have

gcd(M-1, N) * gcd(M+1, N)

is a proper factorization of N.
Dr Sardonicus is offline   Reply With Quote
Old 2020-01-24, 01:08   #9
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×3×227 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
The number of decimal digits in 10*2^13509-1 would also be 2 + floor(13509*log(2)/log(10))...
I am going to spread this out a bit so I can read it better with my bad eyes. Sorry!

2 + floor(13509 * log(2) / log(10))

I carefully worked this through Windows Calculator and came up with 25,151. I am not sure about "floor" but it is familiar. So, I tried the same formula on this:

Code:
231*2^2335281-1 is prime! 702992 digits.
4,544,874. So I must not be doing something properly.
storm5510 is offline   Reply With Quote
Old 2020-01-24, 05:31   #10
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

353 Posts
Default

Quote:
Originally Posted by storm5510 View Post
I am going to spread this out a bit so I can read it better with my bad eyes. Sorry!

2 + floor(13509 * log(2) / log(10))

I carefully worked this through Windows Calculator and came up with 25,151. I am not sure about "floor" but it is familiar. So, I tried the same formula on this:

Code:
231*2^2335281-1 is prime! 702992 digits.
4,544,874. So I must not be doing something properly.
"floor" (for positive numbers) just means to truncate the part after the decimal point. It really should be the ceiling (think of 100, which has 3 digits and a base-10 log of 2).

The multiplication by (log(2) / log(10)) converts the exponent (which is the base-2 log of the 2^n part) to the base-10 log. The first 2 (I think) was supposed to be the k value (10), which really should have been 1. Replace that with the base-10 log of whatever k is (e.g. log(231) / log(10) for your last example). The -1 at the end can basically be ignored.

Last fiddled with by Happy5214 on 2020-01-24 at 05:32
Happy5214 is offline   Reply With Quote
Old 2020-01-24, 06:43   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10000100101002 Posts
Default

Using 2 + floor is equivalent to using 1 + ceiling, no?
VBCurtis is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Patterns in primes that are primitive roots / Gaps in full-reptend primes mart_r Prime Gap Searches 14 2020-06-30 12:42
A question about primes of a particular form enzocreti enzocreti 55 2019-04-27 11:10
Fascinating Lenovo memory configuration paper tServo Hardware 7 2018-11-17 16:28
Fascinating periodic sequence pairs doctornash Other Mathematical Topics 7 2018-07-14 00:06
question about a chain of primes firejuggler Math 31 2014-01-08 18:28

All times are UTC. The time now is 02:52.

Sat Aug 15 02:52:52 UTC 2020 up 1 day, 23:28, 0 users, load averages: 2.25, 2.20, 2.30

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.