20190410, 09:22  #1 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 
Factoring 3^(k*2^n) +/ 1 numbers
Random musings of last night and this morning.
As many on the forum are well aware, I discovered a PRP this time last year which, due to my inexperience and lack of awareness around the subject, is practically unprovable due to the difficulty in factoring N+/1. It was 3^{504206}+2. N+1 and N1 both have a number of algebraic factors which are either too small to be useful or too large to be factorable. Moving onto new concepts, ideas and projects, the following has been rattling around in my brain for a while: Assume a search for primes in , N+1 would therefore be As we know, and so if n is even then giving two factors. This is fine, but largely useless if n is large as the factors are huge and still require factorising. However, if the exponent is a power of 2, this can be done repeatedly: Giving n (usually composite) factors, increasing in value exponentially. Obviously none of this is groundbreaking, I'm just filling in the background information to my musings. My question  the bit I think instinctively is 'no' but I can't work out for sure  is whether these algebraic factors of very specific would make a search for primes at all viable, or whether the factoring of the factors would be still an absurdly gargantuan task. All of the identified factors would be of very specific forms. Furthermore, leading on from that: is there any feasibility in a primesearching project which looks for PRPs of the form and then distributes factoring work of the PRP+1? 
20190410, 11:02  #2 
Sep 2002
Database er0rr
111001001100_{2} Posts 
Code:
? k=1;for(n=1,32,print([n,ceil(2^n*log(3^(k))/log(10))])) [1, 1] [2, 2] [3, 4] [4, 8] [5, 16] [6, 31] [7, 62] [8, 123] [9, 245] [10, 489] [11, 978] [12, 1955] [13, 3909] [14, 7818] [15, 15635] [16, 31269] [17, 62538] [18, 125075] [19, 250149] [20, 500298] [21, 1000596] [22, 2001192] [23, 4002384] [24, 8004767] [25, 16009533] [26, 32019066] [27, 64038131] [28, 128076262] [29, 256152524] [30, 512305047] [31, 1024610093] [32, 2049220186] Code:
? forstep(k=1,14,2,for(n=1,13,if(ispseudoprime(3^(k*2^n)2),print([n,k])))) [1, 1] [2, 1] [1, 3] [1, 11] 
20190410, 11:08  #3 
Jun 2003
1001101011011_{2} Posts 
You're looking at two coinciding rare events
1) b^N2 is prp 2) b^N1 is sufficiently (about 28%? at minimum) factored. You may find that no such (b,N) exists within currently testable ranges. EDIT: There will be plenty of small (b,N), but probably none that is large enough (say, to enter T5K). Last fiddled with by axn on 20190410 at 11:09 
20190410, 11:52  #4 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 

20190410, 11:56  #5  
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}·3^{2} Posts 
Quote:
Also worth noting that there are lots of Ks that could be used. I think any prime k should give a unique exponent. Some kind of ratio between k and n would rule out candidates where n is not large enough to give sufficient algebraic factors. 

20190410, 14:00  #7 
Mar 2018
3·43 Posts 
If you look closely at the second page, you'll probably recognize the name Luke W. Richards..

20190410, 14:37  #8  
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}·3^{2} Posts 
Quote:
I also have a database of about 1,000,000 primes, p, and the first n for which they divide 3^{n}2, coupled with their multiplicative orders of p modulo 3, which saves time on a lot of PRP tests. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some code for factoring numbers up to 2^63  arbooker  Factoring  209  20191014 14:43 
Factoring Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170827 14:56 
Factoring Big Numbers In c#  ShridharRasal  Factoring  10  20080320 17:17 
Need help factoring Cunningham numbers  jasong  Factoring  27  20060321 02:47 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 