mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-01-28, 19:43   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135248 Posts
Default Methods of attacking a large factorization

I'm interested in finding a (partial) factorization of 2^(1093^2) - 1. I added the known factors of 2^1093 - 1, then did trial division to 10^10 finding another prime. I added the work to
http://factordb.com/index.php?query=2^(1093^2)-1
(there was no existing entry).

Can anyone help? I have not been initiated into the mysteries of Aurifeuille, so there may be an easy crack here I'm not aware of.
CRGreathouse is offline   Reply With Quote
Old 2014-01-28, 20:55   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×11×61 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I'm interested in finding a (partial) factorization of 2^(1093^2) - 1. I added the known factors of 2^1093 - 1, then did trial division to 10^10 finding another prime. I added the work to
http://factordb.com/index.php?query=2^(1093^2)-1
(there was no existing entry).

Can anyone help? I have not been initiated into the mysteries of Aurifeuille, so there may be an easy crack here I'm not aware of.
AFAIK in order to apply Aurifeuille factorizations, the exponent must be square free.
alpertron is offline   Reply With Quote
Old 2014-01-28, 21:10   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175416 Posts
Default

Quote:
Originally Posted by alpertron View Post
AFAIK in order to apply Aurifeuille factorizations, the exponent must be square free.
OK. I wasn't too optimistic in any case, looking at existing factorizations of the form 2^(p^2) - 1. I don't suppose there are other tricks that might apply?
CRGreathouse is offline   Reply With Quote
Old 2014-01-28, 21:15   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

53E16 Posts
Default

I do not know at this moment. In the meantime, I'm running the P-1 factorization method on Prime95 using B1=10M, B2=500M. It will be ready in a few hours. If I'm lucky maybe I can find another factor of your number.

By the way, why do you need factors of this particular number?
alpertron is offline   Reply With Quote
Old 2014-01-28, 21:19   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,493 Posts
Default

Quote:
Originally Posted by alpertron View Post
By the way, why do you need factors of this particular number?
There was a discussion recently about the properties of numbers of the form 2^(p^2) - 1 where p is a Weifereich prime. I wasn't a participant -- it was an email exchange between one of my correspondents and Carl Pomerance -- but it seemed interesting enough to look into.

Quote:
Originally Posted by alpertron View Post
In the meantime, I'm running the P-1 factorization method on Prime95 using B1=10M, B2=500M. It will be ready in a few hours. If I'm lucky maybe I can find another factor of your number.
Thanks! I haven't tried rho/SQUFOF or ECM yet, so there is a decent chance.

Last fiddled with by CRGreathouse on 2014-01-28 at 21:21
CRGreathouse is offline   Reply With Quote
Old 2014-01-28, 21:56   #6
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

1,667 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I'm interested in finding a (partial) factorization of 2^(1093^2) - 1. I added the known factors of 2^1093 - 1, then did trial division to 10^10 finding another prime. I added the work to
http://factordb.com/index.php?query=2^(1093^2)-1
(there was no existing entry).

Can anyone help? I have not been initiated into the mysteries of Aurifeuille, so there may be an easy crack here I'm not aware of.
Quote:
Originally Posted by alpertron View Post
AFAIK in order to apply Aurifeuille factorizations, the exponent must be square free.
The only algebraic factors I'm aware of are the ones you've already added, that is, the factors of 2^1093 - 1.

There is no Aurifeullian factorization available, though not for the reason alpertron gives. The exponent need not be square-free; e.g. 2^18 + 1 has an Aurifeullian split. It's the base whose square-freeness is interesting, though a base with squares is not prohibited; it's just that it borrows its algebraic structure from the square-free part of the base (e.g. 12^33+1 has the same structure as 3^33+1).

Your number doesn't have an Aurifeullian split because for a base of 2, those splits are "on the + side". I.e. there are such splits for 2^n + 1, for certain values of n, but not for 2^n - 1. In general, Aurifeullian splits will be available for b^n + 1 if the square-free part of b is 2 or 3 mod 4. If the square-free part of b is 1 mod 4, then such splits are available for b^n - 1. And of course in either case n must be an odd multiple of the square-free part of b.
jyb is offline   Reply With Quote
Old 2014-01-28, 22:19   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,493 Posts
Default

Oh, duh, the factors must be of the form 2k*1093^2, so that makes trial division easy. 19353313801 is easy to pull out this way.
CRGreathouse is offline   Reply With Quote
Old 2014-01-28, 22:37   #8
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

110100000112 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Oh, duh, the factors must be of the form 2k*1093^2, so that makes trial division easy. 19353313801 is easy to pull out this way.
Assuming you meant that they must be of the form 2k*1093^2 + 1, can you explain why that should be true? If p is such a factor, then the order of 2 mod p need not be 1093^2, it can be 1093. So the only such restriction I can get is that p = 2*k*1093 + 1.
jyb is offline   Reply With Quote
Old 2014-01-28, 22:51   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24768 Posts
Default

Quote:
Originally Posted by jyb View Post
Your number doesn't have an Aurifeullian split because for a base of 2, those splits are "on the + side". I.e. there are such splits for 2^n + 1, for certain values of n, but not for 2^n - 1. In general, Aurifeullian splits will be available for b^n + 1 if the square-free part of b is 2 or 3 mod 4. If the square-free part of b is 1 mod 4, then such splits are available for b^n - 1. And of course in either case n must be an odd multiple of the square-free part of b.
Yes, you are right. When the base is 2, the Aurifeullian factorization can only be done on 24n+2+1. The original number does not have this form.
alpertron is offline   Reply With Quote
Old 2014-01-29, 03:14   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001111102 Posts
Default

Quote:
Originally Posted by alpertron View Post
In the meantime, I'm running the P-1 factorization method on Prime95 using B1=10M, B2=500M. It will be ready in a few hours.
With B1=20M, Prime95 found the factor 2479320524445467655675641833, but unfortunately it is a product of already known prime factors: 43721 x 111487 x 26282279 x 19353313801
alpertron is offline   Reply With Quote
Old 2014-01-29, 03:19   #11
PBMcL
 
PBMcL's Avatar
 
Jan 2005

2·31 Posts
Default

Quote:
Originally Posted by jyb View Post
Assuming you meant that they must be of the form 2k*1093^2 + 1, can you explain why that should be true? If p is such a factor, then the order of 2 mod p need not be 1093^2, it can be 1093. So the only such restriction I can get is that p = 2*k*1093 + 1.
Suppose q is a prime factor of 2^(p^2)-1 where p is an odd prime and d is the order of 2 mod q. Since d must divide p^2, then the only possibilities are d=p or d=p^2. When d=p, q divides 2^p-1, which is the known algebraic factor of 2^(p^2)-1. Compute the cofactor C = (2^(p^2)-1)/(2^p-1) and then compute a = gcd(C, 2^p-1). If a>1, compute C'=C/a and repeat until any and all of the repeated prime factors of 2^p-1 have been removed from the cofactor. Then the order of any q dividing the remaining cofactor must be p^2, and q must be of the form q = 2*k*(p^2) + 1. This is just a special case of a much more general theorem.
PBMcL is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cyclotomic Polynomial Factoring methods mickfrancis Factoring 2 2015-01-11 18:31
Attacking the 2+ and 2LM tables xilman Cunningham Tables 28 2013-02-01 21:02
An equivalent problem for factorization of large numbers HellGauss Math 5 2012-04-12 14:01
Methods to determine integer multiples dsouza123 Math 6 2006-11-18 16:10
Guidelines for ECM Before Other Methods wblipp GMP-ECM 1 2005-04-19 15:58

All times are UTC. The time now is 06:52.

Fri Feb 26 06:52:02 UTC 2021 up 85 days, 3:03, 0 users, load averages: 2.02, 1.69, 1.58

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.