Question about these fascinating primes

[storm5510]

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.

[VBCurtis]

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.

[storm5510]

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.

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]

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

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 2^p-1. How that translates to something in this format, I do now know.


Thanks.

[paulunderwood]

Originally Posted by storm5510

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

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 2^p-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.

[Dr Sardonicus]

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.

[paulunderwood]

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:

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,

[Dr Sardonicus]

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.

[storm5510]

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:

231*2^2335281-1 is prime! 702992 digits.

4,544,874. So I must not be doing something properly.

[Happy5214]

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:

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.

[VBCurtis]

Using 2 + floor is equivalent to using 1 + ceiling, no?