Question about these fascinating primes
[QUOTE=Cruelty;527372][B]101*2^73451941[/B] is prime! (2211126 decimal digits)[/QUOTE]
[U]Question[/U]: What are these being ran with to get this format? It looks fascinating. :smile: 
[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^n1 or k*2^n+1 formats (and quite a few others). If LLR doesn't handle it, PFGW does. Also, 231*2^23352811 is prime! 702992 digits. 
[QUOTE=VBCurtis;533338]Sorry for overlooking your question for so long. We run LLR to test k*2^n1 or k*2^n+1 formats (and quite a few others). If LLR doesn't handle it, PFGW does.
Also, 231*2^23352811 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. 
I was learning to use the ABC2 input type for PFGW early this morning when I came up with these:
[CODE]10*2^135091 is 3PRP! (0.0290s+0.0015s) 10*2^217371 is 3PRP! (0.0676s+0.0011s) 10*2^256231 is 3PRP! (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=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^135091 is 3PRP! (0.0290s+0.0015s) 10*2^217371 is 3PRP! (0.0676s+0.0011s) 10*2^256231 is 3PRP! (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^135091))[/c]. "3PRP" means it passes Fermat's Little Theorem test: 3^(N1)=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=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^135091))[/c].
"3PRP" means it passes Fermat's Little Theorem test: 3^(N1)=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^135091 would also be 2 + floor(13509*log(2)/log(10)). It is possible AFAIK that "PRP" means that N "passes" RabinMiller to base 3; in this case, in addition to 3^(N1) == 1 (mod N), that 3^((N1)/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=Dr Sardonicus;535812]The number of decimal digits in 10*2^135091 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" RabinMiller to base 3; in this case, in addition to 3^(N1) == 1 (mod N), that 3^((N1)/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 MR, 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, 
[QUOTE=paulunderwood;535815]Please tell us how one gets a factor from the conditions you mention above,[/QUOTE]
If 3^(N1) == 1 (mod N), and 3^((N1)/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(M1, M+1)  2 then, assuming N is odd, we have gcd(M1, N) * gcd(M+1, N) is a proper factorization of N. 
[QUOTE=Dr Sardonicus;535812]The number of decimal digits in 10*2^135091 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^23352811 is prime! 702992 digits.[/CODE] 4,544,874. So I must not be doing something properly. 
[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^23352811 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 base10 log of 2). The multiplication by (log(2) / log(10)) converts the exponent (which is the base2 log of the 2^n part) to the base10 log. The first 2 (I think) was supposed to be the k value (10), which really should have been 1. Replace that with the base10 log of whatever k is (e.g. log(231) / log(10) for your last example). The 1 at the end can basically be ignored. 
Using 2 + floor is equivalent to using 1 + ceiling, no?

All times are UTC. The time now is 06:42. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.