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.

135710 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

4,243 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.

54D16 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. 23·59 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

32·7·53 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

24×11×19 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

D0B16 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

64208 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.

135710 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

25·11 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 4,243 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 06:42.

Fri Aug 14 06:42:20 UTC 2020 up 1 day, 3:17, 1 user, load averages: 1.23, 1.31, 1.28