ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 18 Dec 2017 13:57:58 +0100solving summation polynomialshttps://ask.sagemath.org/question/40125/solving-summation-polynomials/
Solving discrete logarithm problem for elliptic curves
most papers I see use Magma for solving summation polynomials, can SageMath do this?
Tue, 12 Dec 2017 18:14:31 +0100https://ask.sagemath.org/question/40125/solving-summation-polynomials/Comment by vdelecroix for <p>Solving discrete logarithm problem for elliptic curves</p>
<p>most papers I see use Magma for solving summation polynomials, can SageMath do this?</p>
https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40126#post-id-40126What do you mean precisely? Most programming languages are Turing complete (Python is one of them).Wed, 13 Dec 2017 00:15:22 +0100https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40126#post-id-40126Comment by slelievre for <p>Solving discrete logarithm problem for elliptic curves</p>
<p>most papers I see use Magma for solving summation polynomials, can SageMath do this?</p>
https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40127#post-id-40127For reference, "summation polynomials" are introduced in section 2 of the paper "Summation polynomials and the discrete logarithm problem on elliptic curves" by Igor Semaev, available at [https://eprint.iacr.org/2004/031.pdf](https://eprint.iacr.org/2004/031.pdf).
See also [a discussion of summation polynomials by Steven Galbraith on "The Elliptic Curve Cryptography blog"](https://ellipticnews.wordpress.com/2015/04/13/elliptic-curve-discrete-logarithm-problem-in-characteristic-two/) .Wed, 13 Dec 2017 01:07:21 +0100https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40127#post-id-40127Comment by Paul Doyle for <p>Solving discrete logarithm problem for elliptic curves</p>
<p>most papers I see use Magma for solving summation polynomials, can SageMath do this?</p>
https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40174#post-id-40174Sorry, of course any Turing complete language are equivalent, so my question is badly phrased. I am starting writing an MSc dissertation on the Elliptic Curve Discrete Logarithm Problem over Finite Fields 𝔽pFp, (pp large prime) which is considered to be computationally infeasible, but two recent papers have made some advances, they both present results using Magma, the main computation work is:
generating random points on an Elliptic Curve over a finite field. R=aP+bQR=aP+bQ (a, b random integers)
solving systems of summation polynomial equations (as per your reference). Sm(X1,…,Xm)=0Sm(X1,…,Xm)=0
linear algebra ( using using Gr\"obner basis algorithms )
All the papers I see use Magma, how easy it is for SageMath to do these computations?, in terms of pre-existing functions.Fri, 15 Dec 2017 11:11:59 +0100https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40174#post-id-40174Answer by Paul Doyle for <p>Solving discrete logarithm problem for elliptic curves</p>
<p>most papers I see use Magma for solving summation polynomials, can SageMath do this?</p>
https://ask.sagemath.org/question/40125/solving-summation-polynomials/?answer=40173#post-id-40173Sorry, of course any Turing complete language are equivalent, so my question is badly phrased.
I am starting writing an MSc dissertation on the Elliptic Curve Discrete Logarithm Problem over Finite Fields $\mathbb{F}_p$, ($p$ large prime) which is considered to be computationally infeasible, but two recent papers have made some advances, they both present results using Magma, the main computation work is:
1. generating random points on an Elliptic Curve over a finite field. $R = aP + bQ$ (a, b random integers)
2. solving systems of summation polynomial equations (as per your reference). $S_m(X_1,\dots,X_m) = 0$
3. linear algebra ( using using Gr\"obner basis algorithms )
All the papers I see use Magma, so question is better phrased, if I ask how easy it is for SageMath to do these computations?, in terms of pre-existing functions.
UPDATE:
I've been told by the author of one of the papers , that I should be able to do this in SageMath.Fri, 15 Dec 2017 11:11:38 +0100https://ask.sagemath.org/question/40125/solving-summation-polynomials/?answer=40173#post-id-40173Comment by Iguananaut for <p>Sorry, of course any Turing complete language are equivalent, so my question is badly phrased.
I am starting writing an MSc dissertation on the Elliptic Curve Discrete Logarithm Problem over Finite Fields $\mathbb{F}_p$, ($p$ large prime) which is considered to be computationally infeasible, but two recent papers have made some advances, they both present results using Magma, the main computation work is: </p>
<ol>
<li><p>generating random points on an Elliptic Curve over a finite field. $R = aP + bQ$ (a, b random integers)</p></li>
<li><p>solving systems of summation polynomial equations (as per your reference). $S_m(X_1,\dots,X_m) = 0$ </p></li>
<li><p>linear algebra ( using using Gr\"obner basis algorithms )</p></li>
</ol>
<p>All the papers I see use Magma, so question is better phrased, if I ask how easy it is for SageMath to do these computations?, in terms of pre-existing functions.
UPDATE:
I've been told by the author of one of the papers , that I should be able to do this in SageMath.</p>
https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40213#post-id-40213I could be wrong, but I think you are allowed to edit your own question to provide more details--if possible you should do that rather than update your question in the form of an "answer".Mon, 18 Dec 2017 13:57:58 +0100https://ask.sagemath.org/question/40125/solving-summation-polynomials/?comment=40213#post-id-40213