Extremely non-smooth Factor of M61^120-1

[kosta]

Sometime ago, in another thread I had asked for help factoring numbers of the form M^k-1 where M is some Mersenne prime, for example the ninth, 2^61-1

I has asked for various k, and several people helped, which altogether led to the complete factorization of M61^60-1 and then recently M61^120-1

The latter had a hard 281-digit composite factor and it was finally cracked by yoyo@home, and a 58 digit factor was found after 28000 curves at 260E6.

Now for the bizarre part:

the factor is
F = 2524656400165152086793813231096167969340948451658898368801
and it is non-smooth in the extreme:
F-1 = (2^5)(5^2)(3155820500206440108492266538870209961676185564573622961)

Leaving aside silly numerology, that is 2^5 vs 5^2 , I want to know if (with hindsight) it would have been expected to be found earlier if B2 was set higher? Looking at the optimal parameter tables, it looks like F was found just about where it would be expected based on its total size.

Actually, if indeed larger B2 helps to find non-smooth factors, then perhaps the question is this - the optimal parameters were obtained using a scan over all prime factors in some fixed range. But any given number is not obliged to be average. So, in my mind it is not clear if it follows that for a GIVEN number, the parameters from the table lead to the shortest expected cpu time. I can give you counterexamples, on generic grounds, where the first optimization would not lead to shortest expected time, but I dont like generic arguments and in any case ECM is special.

Nevertheless, I should state my conjecture : I claim that if it is true that larger values of B2 lead to finding non-smoooth factors earlier, then the actual optimal strategy (in the sense of getting the shortest expected time to find a factor of unknown length and smoothness) may be to run a multitude of curves with some carefully chosen distribution of B2 (and B1).

It would be nice if the mathematicians would enlighten this possibly confused physicist.

[Mr. P-1]

Originally Posted by kosta

I want to know if (with hindsight) it would have been expected to be found earlier if B2 was set higher?

My understanding is that ECM doesn't care about the smoothness of q-1 in particular. It will find a factor q if q+b is smooth to the specified bounds, where b is a random integer, |b| < sqrt(N). Running lots of curves allows you to try many different b.

[Mini-Geek]

Originally Posted by kosta

the factor is
F = 2524656400165152086793813231096167969340948451658898368801
and it is non-smooth in the extreme:
F-1 = (2^5)(5^2)(3155820500206440108492266538870209961676185564573622961)

Interesting, but irrelevant for ECM. This only means that the factor would be a VERY poor choice for discovery via P-1. If you know the sigma value used to find this factor, you will find that its group order is smooth enough to fit into the bounds used. A simplistic understanding of ECM and group orders, by analogy to P-1 factoring, is this:
in P-1, it depends on the smoothness of P-1
in ECM, it depends on the smoothness of the group order of the prime given the randomly-chosen sigma

Originally Posted by kosta

Leaving aside silly numerology, that is 2^5 vs 5^2 , I want to know if (with hindsight) it would have been expected to be found earlier if B2 was set higher? Looking at the optimal parameter tables, it looks like F was found just about where it would be expected based on its total size.

Actually, if indeed larger B2 helps to find non-smooth factors ...

A larger B2 will help to find any factor (regardless of the smoothness) in fewer curves, but not necessarily faster (i.e. a shorter time). The B2 values in use are chosen for shortest time to discover a factor. There's no real benefit to fixing B1 and choosing a variety of B2s as you describe.

[ATH]

I do not know much about how ECM works, but I do know that the group order depends on the random sigma value used for each curve, and on the unknown factor p. I don't *think* it depends on the smoothness of p-1 at all, but please correct me if that is wrong.

You can use the Magma Calculator to find the group order: http://magma.maths.usyd.edu.au/calc/

Paste this into the calculator and change the p in the bottom to the factor and s to the random sigma value:

FindGroupOrder2 := function (p, s)
   K := GF(p);
   v := K ! (4*s);
   u := K ! (s^2-5);
   x := u^3;
   b := 4*x*v;
   a := (v-u)^3*(3*u+v);
   A := a/b-2;
   x := x/v^3;
   b := x^3 + A*x^2 + x;
   E := EllipticCurve([0,b*A,0,b^2,0]);
   return FactoredOrder(E);
end function;

p := 2524656400165152086793813231096167969340948451658898368801;
s := 70000;
FindGroupOrder2(p, s);

For s := 70000; I get:
[ <2, 2>, <3, 2>, <7, 1>, <271, 1>, <201667, 1>, <942857, 1>, <1020667, 1>,
<3789012629, 1>, <4981628159, 1>, <10091839780402927, 1> ]

You have to look at the first value in the last two < >, < >, so for sigma 70000 B1 had to be greater than (or equal to?) 4981628159 and B2 had to be greater than (or equal to?) 10091839780402927.

for s := 7465465;
[ <2, 7>, <3, 5>, <5, 1>, <757, 1>, <214447087825456243000327977206731120922301\
37678627, 1> ]

B1 had to be only 758 but B2 had to be huge (above 21444708782545624300032797720673112092230137678627).

[kosta]

thanks for the replies, so, I was wrong about larger B2 helping some numbers vs others, with ECM it seems B2 helps everyone equally, unlike p-1.

The number was factored with generous help from yoyo@home, I am trying to see if they reported the sigma and the B2 limit which finally cracked it. Not at factordb, so far I dont see it on rechenkraft.net either, only the username of the one who succeeded.

Anyway, if anyone is in the mood to help out, try your hand on any factors of M61^(k=1260) - 1 , here http://factordb.com/index.php?id=1100000000593467382

They all had some hundreds of curves at 1E6 run, so probably no more factors below 30 digits.

K

[kosta]

Looking at another recent factor i got,
http://factordb.com/index.php?id=1100000000594414821
and following the suggestion from ATH, above, to look up the group order for the lucky sigma and its factorization , indeed shows the group order is rather smooth.

But then I have another puzzle, why are about half of the digits of the group order identical to the number ? I.e.

p=58672363083616544558212366138621
o=58672363083616547731782941254944

[Mini-Geek]

Originally Posted by kosta

But then I have another puzzle, why are about half of the digits of the group order identical to the number ? I.e.

p=58672363083616544558212366138621
o=58672363083616547731782941254944

This is a good way to understand it:

Originally Posted by Mr. P-1

My understanding is that ECM doesn't care about the smoothness of q-1 in particular. It will find a factor q if q+b is smooth to the specified bounds, where b is a random integer, |b| < sqrt(N). Running lots of curves allows you to try many different b.

I don't know the exact relation of sigma to b - it must be some calculations that I haven't looked up, and/or are above my head. But this isn't too hard to understand: since |b| < sqrt(N), adding b to N will keep around half the digits the same (because sqrt(N) has about half the digits of N). Thus the group order will have roughly the first half of the digits the same. In this case, b=3173570575116323.

[Mr. P-1]

Originally Posted by Mini-Geek

This is a good way to understand it:

I don't know the exact relation of sigma to b - it must be some calculations that I haven't looked up, and/or are above my head.

ATH gave the formula in his post above. Don't understand it? Neither do I.

But this isn't too hard to understand: since |b| < sqrt(N), adding b to N will keep around half the digits the same (because sqrt(N) has about half the digits of N). Thus the group order will have roughly the first half of the digits the same. In this case, b=3173570575116323.

This is correct. There's one other implication to this that you might not have appreciated, and this is that the magnitude of the group order - the number of digits - is about the same as the factor. In particular, it is independent of b. This means that the likelihood that the group order is smooth is independent of b. So, for any particular choice of bounds B1 and B2, the probability of finding a factor will be the same, whether you're doing P-1, P+1, or ecm.

This assumes, of course, that you don't know anything about the factorisation of group order, which is certain to be the case when b is random. Running P-1, other than being a much faster algorithm, is exactly equivalent to running ecm with b fixed at -1. For some numbers, among them Fermat and Mersenne numbers and their cofactors, we do something about the factorisation of q-1, namely that it is divisable by 2ⁿ⁺² and 2q respectively. You can interpret this in two ways, one is that P-1 is much more likely to find a factor of these numbers. The other is that P-1 has the same chance of finding a factor 2n+2 or log₂(q)+1* bits larger than one that ECM might find.

*Or one bit less, if ECM always chooses odd b. I don't know whether it does or not.

[Mr. P-1]

Originally Posted by Mr. P-1

It will find a factor q if q+b is smooth to the specified bounds, where b is a random integer, |b| < sqrt(N).

As is probably obvious, my use of the word "random" was loose. The group order, hence b, is deterministically calculable from sigma and q.

[prgamma10]

Originally Posted by Mr. P-1

*Or one bit less, if ECM always chooses odd b. I don't know whether it does or not.

The curves are chosen such that their group order are always divisible by 12.

[kosta]

thanks, again to everyone, I now understand much better how ECM performs, as compared to p-1.

Anyway, if anyone here is willing to run ecm to help obtain guarantees on primitive polynomials which i need, try to look for factors of M61^1260-1 here: http://factordb.com/index.php?id=1100000000593467382
, starting with B1=3E6