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

mathematica

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

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

mathematica

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

mathematica

1. // courtesy of Allan Steel
   
2. // first save this in a file (say go.magma)
   
3. // then start magma and type:
   
4. //    load "go.magma";
   
5. // then type:
   
6. //    FindGroupOrder(p, sigma);
   
7. // where p is the found factor (must be prime)
   
8. // and sigma is the curve parameter (Suyama's parametrization)
   
9. FindGroupOrder := function (p, sigma)
   
10.    K := GF(p);
    
11.    v := K ! (4*sigma);
    
12.    u := K ! (sigma^2-5);
    
13.    x := u^3;
    
14.    b := 4*x*v;
    
15.    a := (v-u)^3*(3*u+v);
    
16.    A := a/b-2;
    
17.    x := x/v^3;
    
18.    b := x^3 + A*x^2 + x;
    
19.    E := EllipticCurve([0,b*A,0,b^2,0]);
    
20.    return FactoredOrder(E);
    
21. end function;

复制代码

mathematica

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

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

mathematica

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

1. FindGroupOrder := function (p, sigma)
   
2.    K := GF(p);
   
3.    v := K ! (4*sigma);
   
4.    u := K ! (sigma^2-5);
   
5.    x := u^3;
   
6.    b := 4*x*v;
   
7.    a := (v-u)^3*(3*u+v);
   
8.    A := a/b-2;
   
9.    x := x/v^3;
   
10.    b := x^3 + A*x^2 + x;
    
11.    E := EllipticCurve([0,b*A,0,b^2,0]);
    
12.    return FactoredOrder(E);
    
13. end function;
    
14. p:=444391024295554825813920762553875384889500352609895126972409492191251;
    
15. sigma:=2807183577;
    
16. 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

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

1. ecmgroup(p, s)={
   
2. my(v,u,x,b,a,A,E);
   
3. s=Mod(s,p);
   
4. v=4*s;
   
5. u=s^2-5;
   
6. x=u^3;
   
7. b=4*x*v;
   
8. a=(v-u)^3*(3*u+v);
   
9. A=a/b-2;
   
10. x=x/v^3;
    
11. b=x^3+A*x^2+x;
    
12. E=ellinit([0,b*A,0,b^2,0]);
    
13. ellcard(E)
    
14. }

复制代码

If you're comfortable with PARI/GP scripting:

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

nyy

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

nyy

check.pari

1. /* for gmp-ecm version 7.x: for parameter sigma = 0:s */
   
2. /* also for gmp-ecm version 6.x: for sigma = s */
   
3. FindGroupOrder(p,s)={
   
4.   my(K,v,u,x,b,a,A,E);
   
5.   K = Mod(1,p);
   
6.   v = K*(4*s);
   
7.   u = K*(s^2-5);
   
8.   x = u^3;
   
9.   b = 4*x*v;
   
10.   a = (v-u)^3*(3*u+v);
    
11.   A = a/b-2;
    
12.   x = x/v^3;
    
13.   b = x^3 + A*x^2 + x;
    
14.   E = ellinit([0,b*A,0,b^2,0],K);
    
15.   return(ellcard(E));
    
16. }
    
17. 
    
18. FindGroupOrderA(p,A)={
    
19.   my(K, d, a, b, E);
    
20.   K = Mod(1,p);
    
21.   d = K*((A+2)/4);
    
22.   a = K*(4*d-2);
    
23.   b = K*(16*d+2);
    
24.   E = ellinit([0,a/b,0,1/b^2,0],K);
    
25.   return(ellcard(E));
    
26. }
    
27. 
    
28. /* for parameter sigma = 1:s */
    
29. FindGroupOrderParam1(p,s)={
    
30.   return(FindGroupOrderA(p, 4*s^2/2^64-2));
    
31. }
    
32. 
    
33. /* for parameter sigma = 2:s */
    
34. FindGroupOrderParam2(p,s)={
    
35.   my(K,E,P,x,y,x3,A);
    
36.   K = Mod(1,p);
    
37.   E = ellinit([0,36],K);
    
38.   [x,y] = ellmul(E, [-3,3], s);
    
39.   x3 = (3*x+y+6)/(2*(y-3));
    
40.   A = -(3*x3^4+6*x3^2-1)/(4*x3^3);
    
41.   return(FindGroupOrderA(p, A));
    
42. }
    
43. 
    
44. /* for parameter sigma = 3:s */
    
45. FindGroupOrderParam3(p,s)={
    
46.    return(FindGroupOrderA(p, 4*s/2^32-2));
    
47. }
    
48. 
    
49. FindGroupOrderParam(p, sigma, param) = {
    
50.   if (param == 0, return(FindGroupOrder(p, sigma)));
    
51.   if (param == 1, return(FindGroupOrderParam1(p, sigma)));
    
52.   if (param == 2, return(FindGroupOrderParam2(p, sigma)));
    
53.   if (param == 3, return(FindGroupOrderParam3(p, sigma)));
    
54.   print("Invalid parametrization: ", param);
    
55. }
    
56. 
    
57. /*
    
58. # check if a prime p is found with bounds B1 and B2,
    
59. # for parameter 'param' and sigma in [sigma_min,sigma_max-1]
    
60. # check_found (31622776601683800097, 11000, 1873422, 0, 1000)
    
61. # check_found (31622776601683800097, 11000, 1873422, 1, 1000)
    
62. # check_found (31622776601683800097, 11000, 1873422, 2, 1000)
    
63. # check_found (31622776601683800097, 11000, 1873422, 3, 1000)
    
64. */
    
65. check_found(p, B1, B2, param, sigma_max) = {
    
66.   my(e2=0,e3=0,tries=0,found=0,sigma,f);
    
67.   for(sigma=0,sigma_max-1,
    
68.     iferr(f = factor(FindGroupOrderParam(p, sigma, param)),
    
69.           E, next(), 1);
    
70.     f = factor(FindGroupOrderParam(p, sigma, param));
    
71.     tries += 1;
    
72.     if (f[1,1] != 2,
    
73.       print(" * Error 1,1 != 2");
    
74.       print("factors = ",f);
    
75.       return();
    
76.     );
    
77.     e2 += f[1,2];
    
78.     if (f[2,1] == 3,
    
79.       e3 += f[2,2];
    
80.     );
    
81.     ms=matsize(f)[1];
    
82.     if (f[ms-1,1] <= B1 && f[ms,1] <= B2,
    
83.       found += 1;
    
84.     );
    
85.   );
    
86.   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));
    
87. }
    
88. 
    
89. /* check all parametrizations 0, 1, 2, 3 */
    
90. check_found_all(p, B1, B2, sigma_max) = {
    
91.   for (param=0,3,
    
92.     check_found(p,B1,B2,param,sigma_max);
    
93.   );
    
94. }
    
95. 
    
96. /*
    
97. sample run:
    
98. 
    
99. check_found_all(31622776601683800097, 11000, 1873422, 1000)
    
100. */
     

复制代码

https://gitlab.inria.fr/zimmerma ... 4e9852bc269433541c5

Add group order calculation and checking code for Pari/GP, similar to check.sage.