mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Riesel Prime Search (https://www.mersenneforum.org/forumdisplay.php?f=59)
-   -   Question about these fascinating primes (https://www.mersenneforum.org/showthread.php?t=25145)

storm5510 2019-10-12 12:29

Question about these fascinating primes
 
[QUOTE=Cruelty;527372][B]101*2^7345194-1[/B] is prime! (2211126 decimal digits)[/QUOTE]

[U]Question[/U]: What are these being ran with to get this format? It looks fascinating. :smile:

VBCurtis 2019-12-21 20:13

[QUOTE=storm5510;527803][U]Question[/U]: What are these being ran with to get this format? It looks fascinating. :smile:[/QUOTE]

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 2020-01-23 00:39

[QUOTE=VBCurtis;533338]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.[/QUOTE]

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 2020-01-23 14:42

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)
[/CODE] I am not sure about the meaning of "3-" in this instance. I know how to calculate the number of digits in 2[SUP]p[/SUP]-1. How that translates to something in this format, I do now know.


Thanks. :smile:

paulunderwood 2020-01-23 17:21

[QUOTE=storm5510;535791]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)
[/CODE] I am not sure about the meaning of "3-" in this instance. I know how to calculate the number of digits in 2[SUP]p[/SUP]-1. How that translates to something in this format, I do now know.


Thanks. :smile:[/QUOTE]

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

"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 [c]-b[/c] switch.

Dr Sardonicus 2020-01-23 20:46

[QUOTE=paulunderwood;535805]These are roughly 4200, 7000 and 8500 digits. You can get the exact values with pari/GP with [c]length(decimal(10*2^13509-1))[/c].

"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 [c]-b[/c] switch.[/QUOTE]
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 2020-01-23 21:12

[QUOTE=Dr Sardonicus;535812]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.[/QUOTE]

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.
[/QUOTE]

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 2020-01-23 22:37

[QUOTE=paulunderwood;535815]Please tell us how one gets a factor from the conditions you mention above,[/QUOTE]
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 2020-01-24 01:08

[QUOTE=Dr Sardonicus;535812]The number of decimal digits in 10*2^13509-1 would also be 2 + floor(13509*log(2)/log(10))...[/QUOTE]

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.[/CODE] 4,544,874. So I must not be doing something properly.

Happy5214 2020-01-24 05:31

[QUOTE=storm5510;535835]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.[/CODE] 4,544,874. So I must not be doing something properly.[/QUOTE]

"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 2020-01-24 06:43

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


All times are UTC. The time now is 05:47.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.