Draw Elliptic Curves with SQL

The advantage of the approach based on elliptic curves in comparison with the problem of factoring the number used in RSA, or the problem of integer logarithmization used in the Diffie-Hellman algorithm and in DSS, is that in this case equivalent protection is provided with a smaller key length.

In the general case, the equation of an elliptic curve E in the field of real numbers R has the form:

- y ^ 2 + a1 * x * y + a3 * y = x ^ 3 + a2 * x ^ 2 + a4 * x + a6
')
or in the case of a finite residue ring Z | n:

- y ^ 2 + a1 * x * y + a3 * y = x ^ 3 + a2 * x ^ 2 + a4 * x + a6 mod N

We set ourselves the task of visualizing an elliptic curve.

Elliptic curve E in the field of real numbers R

If the elliptic curve E is considered in the field of real numbers R, then the construction of the graph can be described using only the knowledge of algebra and geometry of the upper classes

arguments n a1 a2 a3 a4 a6 xmin xmax

1. Select the range [xmin - xmax] of the argument x
2. We mark on the selected range of the argument x the necessary number of values ​​x1, ..., xN
3. Each of the values ​​of x1, ..., xN is substituted into the equation y ^ 2 + a1 * x * y + a3 * y = x ^ 3 + a2 * x ^ 2 + a4 * x + a6 and we get the usual quadratic equation of the argument y
4. Find the roots of the quadratic equation of the argument y
5. If the quadratic equation of the argument y has solutions, then we add two points to the graph
6. We connect with lines all the “upper” points on the graph and all the “lower” points on the graph.

- a = a (x) = 1
- b = b (x) = a1 * x + a3
- c = c (x) = - (x ^ 3 + a2 * x ^ 2 + a4 * x + a6)

- ayy + by + c = 0
- D = bb-4ac
- y1 = (- b-sqrt (D)) / (2a)
- y2 = (- b + sqrt (D)) / (2a)

Implementation

private void button1_Click(object sender, EventArgs e) { LockForm(); //    double a1 = GetA1(); double a2 = GetA2(); double a3 = GetA3(); double a4 = GetA4(); double a6 = GetA6(); //    X    double xmin = GetXmin(); double xmax = GetXmax(); ulong n = GetN(); // http://stackoverflow.com/questions/10622674/chart-creating-dynamically-in-net-c-sharp var series1 = new Series { Name = "Series1", Color = Color.Black, IsVisibleInLegend = false, IsXValueIndexed = true, ChartType = SeriesChartType.Line }; var series2 = new Series { Name = "Series2", Color = Color.Black, IsVisibleInLegend = false, IsXValueIndexed = true, ChartType = SeriesChartType.Line }; var sb = new StringBuilder(); var sb1 = new StringBuilder(); sb.AppendLine("y^2+a1*x*y+a3*y = x^3+a2*x^2+a4*x+a6"); sb.AppendLine("a1=" + a1); sb.AppendLine("a2=" + a2); sb.AppendLine("a3=" + a3); sb.AppendLine("a4=" + a4); sb.AppendLine("a6=" + a6); sb.AppendLine(); sb.AppendLine("# X Y1 Y2"); sb1.AppendLine("# X Y1 Y2"); for (ulong i = 0; i <= n; i++) { double x = (xmin*(n - i) + xmax*i)/n; //       X const double a = 1; double b = a1*x + a3; double c = -(x*x*x + a2*x*x + a4*x + a6); //            double d = b*b - 4*a*c; if (d < 0) continue; double y1 = (-b - Math.Sqrt(d))/(2*a); double y2 = (-b + Math.Sqrt(d))/(2*a); series1.Points.AddXY(x, y1); series2.Points.AddXY(x, y2); sb.AppendLine(x + " " + y1 + " " + y2); sb1.AppendLine(x + " " + y1 + " " + y2); } //      SetChart(series1, series2); SetReport(sb.ToString()); SetReport1(sb1.ToString()); UnlockForm(); ActivatePage(2); } 

Result

Elliptic curve E in the residue ring Z | n

If an elliptic curve E is considered for a finite residue ring Z | n, then the task of visualizing an elliptic curve is more difficult.
In this case, we can propose a standard, easily programmable algorithm for rendezvous connecting the values ​​of the left and right sides of the equation of an elliptic curve E:

- arguments N a1 a2 a3 a4 a6

1. caching in tables the values ​​of the left and right sides of the equation
2. build indexes for table columns
3. make join tables by calculated values
4. the resulting points after combining the tables depict in the graph.

To work with the cached values ​​of the left and right sides of the equation of the elliptic curve E, we will use DBMS, which will allow us to perform the work on indexing the columns of the tables and combining these tables in the most optimal way.

t1
x key1 = x ^ 3 + a2 * x ^ 2 + a4 * x + a6 mod N
one…
2 ...
3 ...
...
N rN

t2
y key2 = y ^ 2 + a3 * y mod N
one…
2 ...
3 ...
...
N lN

t3
xy key3 = a1 * x * y mod N
eleven…
12…
...
NN ...

if (a1! = 0 mod N) select t1.x, t2.y from t1, t2, t3 where (key1 = key2 + key3 or key1 + N = key2 + key3) and t1.x = t3.x and t2. y = t3.y
if (a1 == 0 mod N) select t1.x, t2.y from t1, t2 where key1 = key2

Implementation

- DBMS - SQLite

  private void button1_Click(object sender, EventArgs e) { LockForm(); //    Z|n var n = GetN(); //    var a1 = GetA1(); var a2 = GetA2(); var a3 = GetA3(); var a4 = GetA4(); var a6 = GetA6(); // http://stackoverflow.com/questions/9173485/how-can-i-create-an-in-memory-sqlite-database var connection = new SQLiteConnection("Data Source=:memory:"); connection.Open(); //   string[] sqls1 = { "CREATE TABLE t1 (x INTEGER , key1 INTEGER )", "CREATE TABLE t2 (y INTEGER , key2 INTEGER )", "CREATE TABLE t3 (x INTEGER , y INTEGER , key3 INTEGER )" }; foreach (var sql in sqls1) new SQLiteCommand(sql, connection).ExecuteNonQuery(); //     for (ulong x = 0; x < n; x++) { var x2 = (x*x)%n; var x3 = (x2*x)%n; var a2X2 = (a2*x2)%n; var a4X = (a4*x)%n; var key1 = (x3 + a2X2 + a4X + a6)%n; var sql = string.Format("INSERT INTO t1 (x, key1) VALUES ({0},{1})", x, key1); new SQLiteCommand(sql, connection).ExecuteNonQuery(); } for (ulong y = 0; y < n; y++) { var y2 = y*y%n; var a3Y = (a3*y)%n; var key2 = (y2 + a3Y)%n; var sql = string.Format("INSERT INTO t2 (y, key2) VALUES ({0},{1})", y, key2); new SQLiteCommand(sql, connection).ExecuteNonQuery(); } if ((a1%n) != 0) for (ulong x = 0; x < n; x++) { var a1X = (a1*x)%n; for (ulong y = 0; y < n; y++) { var key3 = (a1X*y)%n; var sql = string.Format("INSERT INTO t3 (x, y, key3) VALUES ({0},{1},{2})", x, y, key3); new SQLiteCommand(sql, connection).ExecuteNonQuery(); } } //     string[] sqls2 = { "CREATE INDEX t1key1 ON t1 (key1)", "CREATE INDEX t2key2 ON t2 (key2)", "CREATE INDEX t3key3 ON t3 (key3)", "CREATE UNIQUE INDEX t1x ON t1 (x)", "CREATE UNIQUE INDEX t2y ON t2 (y)", "CREATE INDEX t3x ON t3 (x)", "CREATE INDEX t3y ON t3 (y)" }; foreach (var sql in sqls2) new SQLiteCommand(sql, connection).ExecuteNonQuery(); // http://stackoverflow.com/questions/10622674/chart-creating-dynamically-in-net-c-sharp var series1 = new Series { Name = "Series1", Color = Color.Black, IsVisibleInLegend = false, IsXValueIndexed = true, ChartType = SeriesChartType.Point }; //  JOIN     //   DBMS         var select = ((a1%n) == 0) ? "SELECT t1.x,t2.y FROM t1, t2 WHERE key1=key2" : "SELECT t1.x,t2.y FROM t1, t2, t3 WHERE (key1=key2+key3 or key1+" + n + "=key2+key3) AND t1.x=t3.x AND t2.y=t3.y"; var reader = new SQLiteCommand(select, connection).ExecuteReader(); var sb = new StringBuilder(); var sb1 = new StringBuilder(); sb.AppendLine("y^2+a1*x*y+a3*y = x^3+a2*x^2+a4*x+a6 mod n"); sb.AppendLine("n=" + n); sb.AppendLine("a1=" + a1); sb.AppendLine("a2=" + a2); sb.AppendLine("a3=" + a3); sb.AppendLine("a4=" + a4); sb.AppendLine("a6=" + a6); sb.AppendLine(); sb.AppendLine("# X Y"); sb1.AppendLine("# X Y"); while (reader.Read()) { var x = Convert.ToInt32(reader[0]); var y = Convert.ToInt32(reader[1]); series1.Points.AddXY(x, y); sb.AppendLine(x + " " + y); sb1.AppendLine(x + " " + y); } //      SetChart(series1); SetReport(sb.ToString()); SetReport1(sb1.ToString()); connection.Close(); UnlockForm(); ActivatePage(2); } 

Result

Q.E.D

Source codes of programs are available at https://github.com/dprotopopov/mssove3