mathematica 发表于 2019-2-26 10:58:51

椭圆曲线分解（ECM）中的sigma是什么意思？


https://members.loria.fr/PZimmermann/records/ecmnet.html

https://members.loria.fr/PZimmermann/records/top50.html

mathematica 发表于 2019-2-26 11:34:25

https://members.loria.fr/PZimmermann/records/ecm/params.html
这儿有椭圆曲线参数的选择！
https://members.loria.fr/PZimmermann/records/ecm/go.magma
这儿的sigma不知道什么意思，似乎计算群的阶数

mathematica 发表于 2019-2-26 11:49:26

// courtesy of Allan Steel
// first save this in a file (say go.magma)
// then start magma and type:
//    load "go.magma";
// then type:
//    FindGroupOrder(p, sigma);
// where p is the found factor (must be prime)
// and sigma is the curve parameter (Suyama's parametrization)
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();
   return FactoredOrder(E);
end function;

mathematica 发表于 2019-2-27 09:56:41

mathematica 发表于 2019-2-26 11:49


根据上面的代码，然后搜索“Suyama's parametrization”，我得到了自己想要的答案！

mathematica 发表于 2019-3-8 10:23:30

mathematica 发表于 2019-2-26 11:49


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();
   return FactoredOrder(E);
end function;
p:=444391024295554825813920762553875384889500352609895126972409492191251;
sigma:=2807183577;
FindGroupOrder(p,sigma);

http://magma.maths.usyd.edu.au/calc/
在线计算器，输入上面的代码，然后得到结果
[ <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> ]

mathematica 发表于 2019-3-11 14:44:52

本帖最后由 mathematica 于 2019-3-11 14:51 编辑

mathematica 发表于 2019-3-8 10:23
http://magma.maths.usyd.edu.au/calc/
在线计算器，输入上面的代码，然后得到结果
[ , , , , , ,...

ECM分解2^257-1
得到一个因子
ECM found a factor in curve #9, stage #2
Sigma=5369942429900985, B1=1000, B2=100000.
M257 has a factor: 535006138814359 (ECM curve 9, B1=1000, B2=100000)
得到结果
[ <2, 3>, <3, 2>, <5, 2>, <7, 1>, <29, 1>, <31, 1>, <823, 1>, <57389, 1> ]
2^3*3^2*5^2*7*29*31*823*57389
=535006094527800
这个数出卖了535006138814359这个因子

ECM found a factor in curve #56, stage #2
Sigma=3994976758012964, B1=800, B2=80000.
M257 has a factor: 535006138814359 (ECM curve 56, B1=800, B2=80000)
535006121869800因式分解
{{2, 3}, {3, 2}, {5, 2}, {7, 1}, {31, 1}, {37, 1}, {61, 1}, {151, 1}, {4019, 1}}
这个数出来了535006138814359这个因子

nyy 发表于 2023-4-19 10:09:55

ecmgroup(p, s)={
my(v,u,x,b,a,A,E);
s=Mod(s,p);
v=4*s;
u=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=ellinit();
ellcard(E)
}


If you're comfortable with PARI/GP scripting:

https://www.mersenneforum.org/showthread.php?t=28476

nyy 发表于 2023-4-19 10:12:36

http://factordb.com/groupcalc.php
这儿也有

nyy 发表于 2023-4-19 10:16:23

check.pari

/* for gmp-ecm version 7.x: for parameter sigma = 0:s */
/* also for gmp-ecm version 6.x: for sigma = s */
FindGroupOrder(p,s)={
my(K,v,u,x,b,a,A,E);
K = Mod(1,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 = ellinit(,K);
return(ellcard(E));
}

FindGroupOrderA(p,A)={
my(K, d, a, b, E);
K = Mod(1,p);
d = K*((A+2)/4);
a = K*(4*d-2);
b = K*(16*d+2);
E = ellinit(,K);
return(ellcard(E));
}

/* for parameter sigma = 1:s */
FindGroupOrderParam1(p,s)={
return(FindGroupOrderA(p, 4*s^2/2^64-2));
}

/* for parameter sigma = 2:s */
FindGroupOrderParam2(p,s)={
my(K,E,P,x,y,x3,A);
K = Mod(1,p);
E = ellinit(,K);
= ellmul(E, [-3,3], s);
x3 = (3*x+y+6)/(2*(y-3));
A = -(3*x3^4+6*x3^2-1)/(4*x3^3);
return(FindGroupOrderA(p, A));
}

/* for parameter sigma = 3:s */
FindGroupOrderParam3(p,s)={
   return(FindGroupOrderA(p, 4*s/2^32-2));
}

FindGroupOrderParam(p, sigma, param) = {
if (param == 0, return(FindGroupOrder(p, sigma)));
if (param == 1, return(FindGroupOrderParam1(p, sigma)));
if (param == 2, return(FindGroupOrderParam2(p, sigma)));
if (param == 3, return(FindGroupOrderParam3(p, sigma)));
print("Invalid parametrization: ", param);
}

/*
# check if a prime p is found with bounds B1 and B2,
# for parameter 'param' and sigma in
# check_found (31622776601683800097, 11000, 1873422, 0, 1000)
# check_found (31622776601683800097, 11000, 1873422, 1, 1000)
# check_found (31622776601683800097, 11000, 1873422, 2, 1000)
# check_found (31622776601683800097, 11000, 1873422, 3, 1000)
*/
check_found(p, B1, B2, param, sigma_max) = {
my(e2=0,e3=0,tries=0,found=0,sigma,f);
for(sigma=0,sigma_max-1,
    iferr(f = factor(FindGroupOrderParam(p, sigma, param)),
          E, next(), 1);
    f = factor(FindGroupOrderParam(p, sigma, param));
    tries += 1;
    if (f != 2,
      print(" * Error 1,1 != 2");
      print("factors = ",f);
      return();
    );
    e2 += f;
    if (f == 3,
      e3 += f;
    );
    ms=matsize(f);
    if (f <= B1 && f <= B2,
      found += 1;
    );
);
printf("tries=%d, found=%d, %0.8f %0.8f %0.8f \n",tries,found,1.0*e2/tries,1.0*e3/tries,2.0^(e2/tries)*3.0^(e3/tries));
}

/* check all parametrizations 0, 1, 2, 3 */
check_found_all(p, B1, B2, sigma_max) = {
for (param=0,3,
    check_found(p,B1,B2,param,sigma_max);
);
}

/*
sample run:

check_found_all(31622776601683800097, 11000, 1873422, 1000)
*/


https://gitlab.inria.fr/zimmerma/ecm/-/commit/c2e3a25c0995b4ab346f068b9c322146cd65d002#97d65751f36f4156474134e9852bc269433541c5

Add group order calculation and checking code for Pari/GP, similar to check.sage.
页: [1]
查看完整版本: 椭圆曲线分解（ECM）中的sigma是什么意思？