20140128, 19:43  #1 
Aug 2006
13524_{8} Posts 
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. 
20140128, 20:55  #2  
Aug 2002
Buenos Aires, Argentina
2×11×61 Posts 
Quote:


20140128, 21:10  #3 
Aug 2006
1754_{16} Posts 

20140128, 21:15  #4 
Aug 2002
Buenos Aires, Argentina
53E_{16} Posts 
I do not know at this moment. In the meantime, I'm running the P1 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? 
20140128, 21:19  #5  
Aug 2006
2^{2}×1,493 Posts 
Quote:
Thanks! I haven't tried rho/SQUFOF or ECM yet, so there is a decent chance. Last fiddled with by CRGreathouse on 20140128 at 21:21 

20140128, 21:56  #6  
Aug 2005
Seattle, WA
1,667 Posts 
Quote:
Quote:
There is no Aurifeullian factorization available, though not for the reason alpertron gives. The exponent need not be squarefree; e.g. 2^18 + 1 has an Aurifeullian split. It's the base whose squarefreeness is interesting, though a base with squares is not prohibited; it's just that it borrows its algebraic structure from the squarefree 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 squarefree part of b is 2 or 3 mod 4. If the squarefree 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 squarefree part of b. 

20140128, 22:19  #7 
Aug 2006
2^{2}·1,493 Posts 
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.

20140128, 22:37  #8 
Aug 2005
Seattle, WA
11010000011_{2} Posts 
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.

20140128, 22:51  #9  
Aug 2002
Buenos Aires, Argentina
2476_{8} Posts 
Quote:


20140129, 03:14  #10 
Aug 2002
Buenos Aires, Argentina
10100111110_{2} Posts 
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

20140129, 03:19  #11 
Jan 2005
2·31 Posts 
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^p1, which is the known algebraic factor of 2^(p^2)1. Compute the cofactor C = (2^(p^2)1)/(2^p1) and then compute a = gcd(C, 2^p1). If a>1, compute C'=C/a and repeat until any and all of the repeated prime factors of 2^p1 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cyclotomic Polynomial Factoring methods  mickfrancis  Factoring  2  20150111 18:31 
Attacking the 2+ and 2LM tables  xilman  Cunningham Tables  28  20130201 21:02 
An equivalent problem for factorization of large numbers  HellGauss  Math  5  20120412 14:01 
Methods to determine integer multiples  dsouza123  Math  6  20061118 16:10 
Guidelines for ECM Before Other Methods  wblipp  GMPECM  1  20050419 15:58 