mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-04-10, 09:22   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default 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 3504206+2.

N+1 and N-1 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 3^{n}-2, N+1 would therefore be 3^{n}-1

As we know, a^{2k}-1\equiv(a^k+1)(a^k-1) and so if n is even then 3^{n}-2\equiv(3^{n/2}+1)(3^{n/2}-1) 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:

3^{2^n}-1\equiv(3^{2^0}-1)(3^{2^1}+1)(3^{2^2}+1)(3^{2^3}+1)[...](3^{2^{n-2}}+1)(3^{2^{n-1}}+1)

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 3^{k*2{n}}-1 would make a search for 3^{k*2{n}}-2 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 prime-searching project which looks for PRPs of the form b^{k*2{n}}-2 and then distributes factoring work of the PRP+1?
lukerichards is offline   Reply With Quote
Old 2019-04-10, 11:02   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110010011002 Posts
Default

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]
For each k these numbers' number of digits grow very quickly -- so you won't have many to test. Then there is the problem of finding actual PRPs for this double exponent -- a similar problem to the rarity of Fermat prime numbers.

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]
paulunderwood is offline   Reply With Quote
Old 2019-04-10, 11:08   #3
axn
 
axn's Avatar
 
Jun 2003

10011010110112 Posts
Default

You're looking at two coinciding rare events

1) b^N-2 is prp
2) b^N-1 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 2019-04-10 at 11:09
axn is online now   Reply With Quote
Old 2019-04-10, 11:52   #4
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

I might be going mad but I can't find the edit button on the first post. Maybe you can't edit the lead post in a thread? Anyway, there's a mistake. Maybe a mod could edit it and delete this post?

Quote:
Originally Posted by lukerichards View Post
3^{2^n}-1\equiv(3^{2^0}-1)(3^{2^1}+1)(3^{2^2}+1)(3^{2^3}+1)[...](3^{2^{n-2}}+1)(3^{2^{n-1}}+1)
Should read:

Quote:
Originally Posted by lukerichards View Post
3^{2^n}-1\equiv(3^{2^0}-1)(3^{2^0}+1)(3^{2^1}+1)(3^{2^2}+1)(3^{2^3}+1)[...](3^{2^{n-2}}+1)(3^{2^{n-1}}+1)
lukerichards is offline   Reply With Quote
Old 2019-04-10, 11:56   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
For each k these numbers' number of digits grow very quickly -- so you won't have many to test.
Understood - but that at least makes the problem relatively finite (limited by computing power and time), which at least gives bounds for reasonable investigation.

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.
lukerichards is offline   Reply With Quote
Old 2019-04-10, 13:23   #6
axn
 
axn's Avatar
 
Jun 2003

115338 Posts
Default

014224 has the known list of 3^n-2 primes.
051783 has the known list of 3^n+2 primes.

These are rather small sets. You can see how many such numbers have the qualities that you look for.

PS:- Why is the OEIS tag trying to add an "A" ?
axn is online now   Reply With Quote
Old 2019-04-10, 14:00   #7
DukeBG
 
Mar 2018

3·43 Posts
Default

Quote:
Originally Posted by axn View Post
014224 has the known list of 3^n-2 primes.
051783 has the known list of 3^n+2 primes.

These are rather small sets. You can see how many such numbers have the qualities that you look for.
If you look closely at the second page, you'll probably recognize the name Luke W. Richards..
DukeBG is offline   Reply With Quote
Old 2019-04-10, 14:37   #8
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by DukeBG View Post
If you look closely at the second page, you'll probably recognize the name Luke W. Richards..
Indeed, I've tested (or sieved) all n up to 1,300,000 for 3n+2 while someone else has tested n up to 1,000,000 for 3n-2.

I also have a database of about 1,000,000 primes, p, and the first n for which they divide 3n-2, coupled with their multiplicative orders of p modulo 3, which saves time on a lot of PRP tests.
lukerichards is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some code for factoring numbers up to 2^63 arbooker Factoring 209 2019-10-14 14:43
Factoring Mersenne numbers paulunderwood Miscellaneous Math 18 2017-08-27 14:56
Factoring Big Numbers In c# ShridharRasal Factoring 10 2008-03-20 17:17
Need help factoring Cunningham numbers jasong Factoring 27 2006-03-21 02:47
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 07:58.

Thu May 6 07:58:50 UTC 2021 up 28 days, 2:39, 0 users, load averages: 1.55, 1.72, 1.78

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.