mersenneforum.org (https://www.mersenneforum.org/index.php)
-   GMP-ECM (https://www.mersenneforum.org/forumdisplay.php?f=55)
-   -   what does sigma mean in ECM? (https://www.mersenneforum.org/showthread.php?t=24113)

 bbb120 2019-02-26 04:36

what does sigma mean in ECM?

I recently take great interest in ECM factorization ,
[url]https://members.loria.fr/PZimmermann/records/ecmnet.html[/url]
what sigma can be used for ?

 DukeBG 2019-02-26 11:25

I'll keep it simple.
When factoring with ECM, you run the algorithm on the numer using multiple different curves of the same "size", each of which can yield a factor (or not). It is known how many (different) curves you need at each factor size to get a certain probability to find a factor (of that size). The sigma parameter is a number, from which the parameters (like coefficients) of the curve are derived. Testing with the same number with the same sigma, b1 and b2 would yield absolutely the same result. Running 100 curves means randomly chosing 100 sigmas.
You might also notice that sigmas start with "0:" or "1:" – those are different [I]parametizations[/I]. Basically, also just different ways to get curves.

 bbb120 2019-02-27 01:07

[url]https://members.loria.fr/PZimmermann/records/ecm/go.magma[/url]
I found it,
but why do no use A and B instead of sigma (where y^2=x^3+A*x+B)?
Is sigma much more useful than A and B?

 bbb120 2019-03-08 02:12

[CODE]FindGroupOrder := function (p, sigma)
K := GF(p);
v := K ! (4*sigma);
u := K ! (sigma^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:=40122362455616221971122353;
sigma:=2334843726764251;
FindGroupOrder(p,sigma);[/CODE]
[url]http://magma.maths.usyd.edu.au/calc/[/url]
magma calculator online

output
[ <2, 3>, <3, 1>, <5, 1>, <19, 1>, <71, 1>, <281, 1>, <331, 1>, <4271, 1>,
<8887, 1>, <70206001, 1> ]

 bbb120 2019-03-08 02:17

[url]https://members.loria.fr/PZimmermann/records/top10-2018.html[/url]
[CODE]FindGroupOrder := function (p, sigma)
K := GF(p);
v := K ! (4*sigma);
u := K ! (sigma^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:=444391024295554825813920762553875384889500352609895126972409492191251;
sigma:=2807183577;
FindGroupOrder(p,sigma);[/CODE]

[ <2, 3>, <3, 2>, <5, 1>, <7, 1>, <3347, 1>, <4363, 1>, <295751, 1>, <6746549,
1>, <22098383, 1>, <136265083, 1>, <396868981, 1>, <809136473, 1>,
<6258955966441, 1> ]

 storm5510 2020-10-15 17:16

[QUOTE=DukeBG;509492]I'll keep it simple.

When factoring with ECM, you run the algorithm on the number using multiple different curves of the same "size", each of which can yield a factor (or not). It is known how many (different) curves you need at each factor size to get a certain probability to find a factor (of that size). The sigma parameter is a number, from which the parameters (like coefficients) of the curve are derived. Testing with the same number with the same sigma, b1 and b2 would yield absolutely the same result. Running 100 curves means randomly choosing 100 sigmas.

You might also notice that sigmas start with "0:" or "1:" – those are different [I]parametizations[/I]. Basically, also just different ways to get curves.[/QUOTE]

I have wondered about the purpose of Sigma for a long time. I cannot say that I understand all of what is above. Only some of it. It appears that B1 and B2 dictate the size of the curve. In time, I can probably get the rest of it.

 RedGolpe 2021-01-26 13:44

You want the cardinality of the group generated by your elliptic curve to have as many small factors as possible. The specific form of the curves generated by the sigma parameters ensure that such cardinality is divisible by 4 (if I remember correctly, for old versions) or 12 (new versions). Sigma starting with "0:" or "1:" denote the old and new version, respectively.

 storm5510 2021-01-26 16:18

[QUOTE=DukeBG;509492]...Running 100 curves means randomly chosing 100 sigmas...[/QUOTE]

I would take the above to mean the more sigma's applied to the same candidate, the higher the chances are of finding a factor. There still needs to be increasing values of B1 and B2 during the process, otherwise a high enough magnitude may not be reached to find a factor, depending on the candidate.

 All times are UTC. The time now is 13:24.