找回密码
 欢迎注册
查看: 43869|回复: 9

[提问] 椭圆曲线分解(ECM)中的sigma是什么意思?

[复制链接]
发表于 2019-2-26 10:58:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×

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

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

QQ截图20190226105820.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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不知道什么意思,似乎计算群的阶数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-26 11:49:26 | 显示全部楼层
  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;
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-27 09:56:41 | 显示全部楼层

根据上面的代码,然后搜索“Suyama's parametrization”,我得到了自己想要的答案!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-8 10:23:30 | 显示全部楼层
  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> ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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这个因子

点评

光滑数出卖了这些素数  发表于 2019-3-11 14:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 10:09:55 | 显示全部楼层
  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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 10:12:36 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-4-19 10:16:23 | 显示全部楼层
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. FindGroupOrderA(p,A)={
  18.   my(K, d, a, b, E);
  19.   K = Mod(1,p);
  20.   d = K*((A+2)/4);
  21.   a = K*(4*d-2);
  22.   b = K*(16*d+2);
  23.   E = ellinit([0,a/b,0,1/b^2,0],K);
  24.   return(ellcard(E));
  25. }

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

  30. /* for parameter sigma = 2:s */
  31. FindGroupOrderParam2(p,s)={
  32.   my(K,E,P,x,y,x3,A);
  33.   K = Mod(1,p);
  34.   E = ellinit([0,36],K);
  35.   [x,y] = ellmul(E, [-3,3], s);
  36.   x3 = (3*x+y+6)/(2*(y-3));
  37.   A = -(3*x3^4+6*x3^2-1)/(4*x3^3);
  38.   return(FindGroupOrderA(p, A));
  39. }

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

  44. FindGroupOrderParam(p, sigma, param) = {
  45.   if (param == 0, return(FindGroupOrder(p, sigma)));
  46.   if (param == 1, return(FindGroupOrderParam1(p, sigma)));
  47.   if (param == 2, return(FindGroupOrderParam2(p, sigma)));
  48.   if (param == 3, return(FindGroupOrderParam3(p, sigma)));
  49.   print("Invalid parametrization: ", param);
  50. }

  51. /*
  52. # check if a prime p is found with bounds B1 and B2,
  53. # for parameter 'param' and sigma in [sigma_min,sigma_max-1]
  54. # check_found (31622776601683800097, 11000, 1873422, 0, 1000)
  55. # check_found (31622776601683800097, 11000, 1873422, 1, 1000)
  56. # check_found (31622776601683800097, 11000, 1873422, 2, 1000)
  57. # check_found (31622776601683800097, 11000, 1873422, 3, 1000)
  58. */
  59. check_found(p, B1, B2, param, sigma_max) = {
  60.   my(e2=0,e3=0,tries=0,found=0,sigma,f);
  61.   for(sigma=0,sigma_max-1,
  62.     iferr(f = factor(FindGroupOrderParam(p, sigma, param)),
  63.           E, next(), 1);
  64.     f = factor(FindGroupOrderParam(p, sigma, param));
  65.     tries += 1;
  66.     if (f[1,1] != 2,
  67.       print(" * Error 1,1 != 2");
  68.       print("factors = ",f);
  69.       return();
  70.     );
  71.     e2 += f[1,2];
  72.     if (f[2,1] == 3,
  73.       e3 += f[2,2];
  74.     );
  75.     ms=matsize(f)[1];
  76.     if (f[ms-1,1] <= B1 && f[ms,1] <= B2,
  77.       found += 1;
  78.     );
  79.   );
  80.   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));
  81. }

  82. /* check all parametrizations 0, 1, 2, 3 */
  83. check_found_all(p, B1, B2, sigma_max) = {
  84.   for (param=0,3,
  85.     check_found(p,B1,B2,param,sigma_max);
  86.   );
  87. }

  88. /*
  89. sample run:

  90. check_found_all(31622776601683800097, 11000, 1873422, 1000)
  91. */
复制代码


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

Add group order calculation and checking code for Pari/GP, similar to check.sage.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-22 01:39 , Processed in 0.028492 second(s), 21 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表