Methods of attacking a large factorization

[CRGreathouse]

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.

[alpertron]

Originally Posted by CRGreathouse

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.

[CRGreathouse]

Originally Posted by alpertron

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?

[alpertron]

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?

[CRGreathouse]

Originally Posted by alpertron

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.

Originally Posted by alpertron

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.

[jyb]

Originally Posted by CRGreathouse

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.

Originally Posted by alpertron

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.

[CRGreathouse]

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.

[jyb]

Originally Posted by CRGreathouse

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.

[alpertron]

Originally Posted by jyb

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 2⁴ⁿ⁺²+1. The original number does not have this form.

[alpertron]

Originally Posted by alpertron

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

[PBMcL]

Originally Posted by jyb

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.