mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-09-06, 07:47   #1
kurtulmehtap
 
Sep 2009

3610 Posts
Default Factorization on 2^p +1

Hi All,
We know the factors of 2^p -1 are in the form 2kp +1, What about
Factors of 2^p +1? Do they have a special form and what is the fastest way to find the factors?
Thanx
kurtulmehtap is offline   Reply With Quote
Old 2010-09-06, 12:52   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
Hi All,
We know the factors of 2^p -1 are in the form 2kp +1, What about
Factors of 2^p +1? Do they have a special form and what is the fastest way to find the factors?
Thanx
Any decent book on elementary number theory will answer the first
question.

Noone knows the answer to the second question.

You need to learn some number theory.
R.D. Silverman is offline   Reply With Quote
Old 2010-09-06, 13:29   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

though I have found 1 exception so far hence my idea is flawed. most have a first prime factor that ends in the same digit for those that end in 7,3,5, and end in 3 for ending in 9.

the first exception is 2^32+1 ends in 7 but the first prime factor Pari finds is 641.
science_man_88 is offline   Reply With Quote
Old 2010-09-06, 14:01   #4
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

24·3·61 Posts
Default

Your 'rule' for exceptions can occur for N=2^n+1 for n == 0 MOD 16.

See here for n=1...200.

The exceptions are for n=32, 48, 96, 112, 144, 160, 192.
kar_bon is offline   Reply With Quote
Old 2010-09-06, 14:06   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2×5×7×61 Posts
Default

I don't know for sure that it's true, but I think factors q of 2^p+1 must be:
q=2kp+1, and
q=1 or 3 mod 8
This is from looking at factors of 2^p+1 at the Factor DB.
Mini-Geek is offline   Reply With Quote
Old 2010-09-06, 15:14   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I don't know for sure that it's true, but I think factors q of 2^p+1 must be:
q=2kp+1, and
q=1 or 3 mod 8
This is from looking at factors of 2^p+1 at the Factor DB.
then how is 5 a factor for like 25% of them ?


Mat([5, 1]),2
[5, 1; 13, 1],6
[5, 2; 41, 1],10
[5, 1; 29, 1; 113, 1],14
[5, 1; 13, 1; 37, 1; 109, 1],18
[5, 1; 397, 1; 2113, 1],22
[5, 1; 53, 1; 157, 1; 1613, 1],26
[5, 2; 13, 1; 41, 1; 61, 1; 1321, 1],30
[5, 1; 137, 1; 953, 1; 26317, 1],34
[5, 1; 229, 1; 457, 1; 525313, 1],38
[5, 1; 13, 1; 29, 1; 113, 1; 1429, 1; 14449, 1],42
[5, 1; 277, 1; 1013, 1; 1657, 1; 30269, 1],46
[5, 3; 41, 1; 101, 1; 8101, 1; 268501, 1],50
[5, 1; 13, 1; 37, 1; 109, 1; 246241, 1; 279073, 1],54
[5, 1; 107367629, 1; 536903681, 1],58
[5, 1; 5581, 1; 8681, 1; 49477, 1; 384773, 1],62
[5, 1; 13, 1; 397, 1; 2113, 1; 312709, 1; 4327489, 1],66
[5, 2; 29, 1; 41, 1; 113, 1; 7416361, 1; 47392381, 1],70

these are all that I searched that have a factor of 5 and they fit 2 mod 4

a lot also have 3 as a first factor.
science_man_88 is offline   Reply With Quote
Old 2010-09-06, 16:32   #7
axn
 
axn's Avatar
 
Jun 2003

121248 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
then how is 5 a factor for like 25% of them ?

<snip>
these are all that I searched that have a factor of 5 and they fit 2 mod 4

a lot also have 3 as a first factor.
2^p+1 for prime p. 3 is always a factor for them. Google "Wagstaff primes"

Try this:
Code:
forprime(p=3,100,print(p " " factor((2^p+1)/3)));
axn is offline   Reply With Quote
Old 2010-09-06, 16:37   #8
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·2,417 Posts
Default

Quote:
Originally Posted by axn View Post
2^p+1 for prime p. 3 is always a factor for them. Google "Wagstaff primes"

Try this:
Code:
forprime(p=3,100,print(p " " factor((2^p+1)/3)));
not for p=2...

Luigi
ET_ is offline   Reply With Quote
Old 2010-09-06, 17:58   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I don't know for sure that it's true, but I think factors q of 2^p+1 must be:
q=2kp+1, and
q=1 or 3 mod 8
This is from looking at factors of 2^p+1 at the Factor DB.
The proof for 2^p+1, p prime is essentially the same as for 2^p-1,
except that 2^p+1, p odd, also admits an algebraic factor.
R.D. Silverman is offline   Reply With Quote
Old 2010-09-07, 09:44   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×1,601 Posts
Default

http://www.mersenneforum.org/showpos...0&postcount=92
ATH is offline   Reply With Quote
Old 2010-09-07, 13:07   #11
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

2p+1 in binary is a number with only two bits set, bit 0 and the most significant bit at bit position p. For odd p, 2p+1 is divisible by 3. Dividing out that 3, what is left in binary has a very simple pattern. Set the least significant two bits to 11 and until bit position p-2 is reached, repeat the pattern 10 moving to the left. The first few examples look like this:
Code:
9876543210 (bit positions) (bit positions p-2 highlighted)
0000000011
0000001011
0000101011
1010101011
As can easily be seen, this has a simple pattern. To be a bit more comfortable with this, you can notice that once this pattern is shifted left one position and added to the original pattern (this is multiplying by 3), all but the least significant bit are carried out (placing a bit in bit position p; as is needed for 2p+1). This is pedantic and pattern obsessive, but by looking at the pattern, it is obvious that all the values in the code block above are 3 mod 8.

addendum:
Without thinking about it much, initially I think that after the 3 is divided out, the product of the remaining factors needs to be 3 mod 8. There can be any number of factors that are 1 mod 8 but the rest of the factors must have a product that is 3 mod 8. I haven't thought about factors that are 5 mod 8 or -1 mod 8 (if any or even if these are allowed) and I haven't done the smart thing of doing actual math but I can see that if all the remaining factors that aren't 1 mod 8 are 3 mod 8 that would mean that there would need to be an odd number of factors that are 3 mod 8.

Last fiddled with by only_human on 2010-09-07 at 13:42 Reason: added addendum
only_human is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factorization of RSA-180 Robert Holmes Factoring 19 2010-11-08 18:46
Factorization of 7,254+ dleclair NFSNET Discussion 1 2006-03-21 05:11
Factorization of 11,212+ Wacky NFSNET Discussion 1 2006-03-20 23:43
Factorization of 5,307- Jeff Gilchrist NFSNET Discussion 7 2005-02-23 19:46
Factorization of M(738) McBryce Factoring 2 2003-09-19 19:32

All times are UTC. The time now is 03:45.


Wed Dec 8 03:45:51 UTC 2021 up 137 days, 22:14, 1 user, load averages: 1.31, 1.13, 1.17

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.