mersenneforum.org Question about these fascinating primes
 Register FAQ Search Today's Posts Mark Forums Read

2019-10-12, 12:29   #1
storm5510
Random Account

Aug 2009
U.S.A.

162110 Posts

Quote:
 Originally Posted by Cruelty 101*2^7345194-1 is prime! (2211126 decimal digits)
Question: What are these being ran with to get this format? It looks fascinating.

2019-12-21, 20:13   #2
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

104568 Posts

Quote:
 Originally Posted by storm5510 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.

2020-01-23, 00:39   #3
storm5510
Random Account

Aug 2009
U.S.A.

1,621 Posts

Quote:
 Originally Posted by VBCurtis 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.

 2020-01-23, 14:42 #4 storm5510 Random Account     Aug 2009 U.S.A. 31258 Posts 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.
2020-01-23, 17:21   #5
paulunderwood

Sep 2002
Database er0rr

65668 Posts

Quote:
 Originally Posted by storm5510 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.

2020-01-23, 20:46   #6
Dr Sardonicus

Feb 2017
Nowhere

23·3·149 Posts

Quote:
 Originally Posted by paulunderwood 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

2020-01-23, 21:12   #7
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

Quote:
 Originally Posted by Dr Sardonicus 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

2020-01-23, 22:37   #8
Dr Sardonicus

Feb 2017
Nowhere

1101111110002 Posts

Quote:
 Originally Posted by paulunderwood 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.

2020-01-24, 01:08   #9
storm5510
Random Account

Aug 2009
U.S.A.

1,621 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

2020-01-24, 05:31   #10
Happy5214

"Alexander"
Nov 2008
The Alamo City

38910 Posts

Quote:
 Originally Posted by storm5510 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

 2020-01-24, 06:43 #11 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·3·733 Posts Using 2 + floor is equivalent to using 1 + ceiling, no?

 Similar Threads Thread Thread Starter Forum Replies Last Post mart_r Prime Gap Searches 14 2020-06-30 12:42 enzocreti enzocreti 55 2019-04-27 11:10 tServo Hardware 7 2018-11-17 16:28 doctornash Other Mathematical Topics 7 2018-07-14 00:06 firejuggler Math 31 2014-01-08 18:28

All times are UTC. The time now is 00:58.

Wed Oct 28 00:58:17 UTC 2020 up 47 days, 22:09, 2 users, load averages: 1.50, 1.69, 1.87

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.