solving maths elliptic equation

Hello everyone,

I need to solve an equation in matlab as such:

y2=x3+aX+b Given

4a3+27b2≠0

Thanks in advance, regards, Anupam

[Walter Roberson]

That does not appear to be an elliptic to me.

[John D'Errico]

To me, it seems closer to cryptic than elliptic. Perhaps a rubric, or a cube from Rubic? Maybe even aseptic or dyspeptic. But in the end? Just a cubic. Now I must go, no longer a goldbrick.

[Image Analyst]

Which of the 7 variables (y2, x3, X, a, a3, b, and b2) do you have values for, and which do you not have values for and need to solve for? What's elliptic? Everything looks linear to me, unless you didn't put in proper symbols for multiplication and exponentiation (* and ^), but I guess at first I should assume you know what you're doing/saying.

[Walter Roberson]

It appears to me that the graph has to do with conic sections. Conic sections are not always ellipses.

Answer 1

[John D'Errico]

Hint:

help roots
help solve

Answer 2

[Anupam]

am sorry for the formatting mistake, actually its like this

y^2=x^3+ax+b=0 given 4a^3+27b^2≠0

I need to solve it to generate a pair of private and public key for further use for a cryptographic algorithm

[Walter Roberson]

Is it perhaps over integers instead of over reals ? Because in reals it is

y = +/- sqrt(x^3+a*x+b)

and the constraint doesn't matter to that.

Answer 3

[Roger Stafford]

As John has already pointed out, this is a "cubic" equation in the unknown x, not an "elliptic" equation. As he has also pointed out, it can be solved numerically using matlab's 'roots' function.

If you are interested in an explicit formula in terms of general values for a and b, you should read up on the theory of cubic equations. It was first discovered by Scipione Del Ferro some time in the fifteen hundreds. The following web sites, as well as many text books, explain that theory:

 http://en.wikipedia.org/wiki/Cubic_function
 http://mathworld.wolfram.com/CubicFormula.html

You can search Google for other presentations of the theory.

The condition that you mention, 4*a^3+27*b^2 ~= 0, excludes the case where all three roots are real but two or all three are multiple roots. Can you possibly tell us how such a condition relates to the generation of keys for cryptographic purposes?

Answer 4

[Anupam]

Let me clarify, I am doing my final year project at the local university and I have to design an Elliptic Curve Digital Signature Algorithm(ECDSA). My field to use this type of algorithm is for a wireless sensor network. My supervisor instructed me to do this way as we need to respect the size of each data in the network, power consumption of the wireless sensors and also delay.

The initial phase of the algorithm is to solve the above equation for the pair of keys, then further on it will be used during the encryption process.

I do not have that proper knowledge on this crytographic technique, it seems complex but it would be good to learn new things. I am not so familiar to matlab also as I have done a small coursework using it but I would be grateful and thankful to everyone helping me to learn matlab.

Thanks again, I think I made myself clear and given the aim of my code implementation

[Walter Roberson]

Sorry, for legal reasons, we cannot discuss Elliptic Curve Encryption on Mathworks' servers.

Answer 5

[Roger Stafford]

In my opinion, where you stated "x^3+ax+b=0" you misled us into thinking you wished to solve that cubic equation, and the "y^2" part remained a mystery. Now I understand that you are indeed dealing with elliptic curves of the type y^2 = x^3+a*x+b, but you still have not made it clear what you mean by the statement "solve the above equation for the pair of keys". What exactly do you mean by that? There is an infinite continuum of points (x,y) that lie on such a curve.

I have been looking at the web site

 http://en.wikipedia.org/wiki/Elliptic_curve

which speaks of an operation in which two points, P and Q, on such a curve uniquely determine a third distinct point R which must also lie on the curve and at the same time must lie on the straight line through P and Q. Is that actually the problem you are posing here? If so, you should make that clear. We shouldn't have to make guesses as to what you are asking!

Note: The web site

 http://mathworld.wolfram.com/EllipticCurve.html

has a solution for this problem with equations (10) and (11).