mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2019-02-26, 04:36   #1
bbb120
 
bbb120's Avatar
 
Feb 2019
China

3A16 Posts
Default what does sigma mean in ECM?

I recently take great interest in ECM factorization ,
https://members.loria.fr/PZimmermann...ds/ecmnet.html
what sigma can be used for ?
bbb120 is offline   Reply With Quote
Old 2019-02-26, 11:25   #2
DukeBG
 
Mar 2018

3×43 Posts
Default

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 parametizations. Basically, also just different ways to get curves.

Last fiddled with by DukeBG on 2019-02-26 at 11:26
DukeBG is offline   Reply With Quote
Old 2019-02-27, 01:07   #3
bbb120
 
bbb120's Avatar
 
Feb 2019
China

2·29 Posts
Default

https://members.loria.fr/PZimmermann...s/ecm/go.magma
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 is offline   Reply With Quote
Old 2019-03-08, 02:12   #4
bbb120
 
bbb120's Avatar
 
Feb 2019
China

728 Posts
Default

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);
http://magma.maths.usyd.edu.au/calc/
magma calculator online

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

Last fiddled with by bbb120 on 2019-03-08 at 02:14
bbb120 is offline   Reply With Quote
Old 2019-03-08, 02:17   #5
bbb120
 
bbb120's Avatar
 
Feb 2019
China

2·29 Posts
Default

https://members.loria.fr/PZimmermann...op10-2018.html
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);
[ <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> ]
bbb120 is offline   Reply With Quote
Old 2020-10-15, 17:16   #6
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

110100101012 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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 parametizations. Basically, also just different ways to get curves.
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.
storm5510 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Iteration of (sigma(n)+phi(n))/2 sean Factoring 2 2017-09-18 15:39
Given sigma(n)-n, find the smallest possible n mart_r Aliquot Sequences 6 2013-07-23 20:50
Spooky sigma values lavalamp Software 2 2010-08-24 15:22

All times are UTC. The time now is 00:44.

Fri Nov 27 00:44:10 UTC 2020 up 77 days, 21:55, 3 users, load averages: 2.03, 1.61, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.