20191012, 12:29  #1 
Random Account
Aug 2009
U.S.A.
5^{2}·61 Posts 
Question about these fascinating primes

20191221, 20:13  #2  
"Curtis"
Feb 2005
Riverside, CA
7·617 Posts 
Quote:
Also, 231*2^23352811 is prime! 702992 digits. 

20200123, 00:39  #3 
Random Account
Aug 2009
U.S.A.
5^{2}×61 Posts 
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.

20200123, 14:42  #4 
Random Account
Aug 2009
U.S.A.
5^{2}·61 Posts 
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) Thanks. 
20200123, 17:21  #5  
Sep 2002
Database er0rr
D4C_{16} Posts 
Quote:
"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 b switch. 

20200123, 20:46  #6  
Feb 2017
Nowhere
2^{2}·3·17^{2} Posts 
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. Last fiddled with by Dr Sardonicus on 20200123 at 20:49 Reason: add qualifier 

20200123, 21:12  #7  
Sep 2002
Database er0rr
2^{2}×23×37 Posts 
Quote:
Quote:
Please tell us how one gets a factor from the conditions you mention above, Last fiddled with by paulunderwood on 20200123 at 21:14 

20200123, 22:37  #8  
Feb 2017
Nowhere
2^{2}·3·17^{2} Posts 
Quote:
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. 

20200124, 01:08  #9  
Random Account
Aug 2009
U.S.A.
5^{2}×61 Posts 
Quote:
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. 

20200124, 05:31  #10  
"Alexander"
Nov 2008
The Alamo City
3×5^{3} Posts 
Quote:
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. Last fiddled with by Happy5214 on 20200124 at 05:32 

20200124, 06:43  #11 
"Curtis"
Feb 2005
Riverside, CA
4319_{10} Posts 
Using 2 + floor is equivalent to using 1 + ceiling, no?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Patterns in primes that are primitive roots / Gaps in fullreptend primes  mart_r  Prime Gap Searches  14  20200630 12:42 
A question about primes of a particular form  enzocreti  enzocreti  55  20190427 11:10 
Fascinating Lenovo memory configuration paper  tServo  Hardware  7  20181117 16:28 
Fascinating periodic sequence pairs  doctornash  Other Mathematical Topics  7  20180714 00:06 
question about a chain of primes  firejuggler  Math  31  20140108 18:28 