associativity ec

https://file.scirp.org/Html/1-5301366_80983.htm

https://brilliant.org/wiki/cubic-discriminant/

We can compute the discriminant of any power of a polynomial. For example, the quadratic discriminant is given by \Delta_2 = b^2 - 4acΔ2?=b2?4ac. But it gets more complicated for higher-degree polynomials.

The discriminant of a cubic polynomial ax^3 + bx^2 + cx + dax3+bx2+cx+d is given by

\Delta_3 = b^2 c^2 - 4ac^3 - 4b^3 d - 27a^2 d^2 + 18abcd.Δ3?=b2c2?4ac3?4b3d?27a2d2+18abcd.

If \Delta_3 > 0Δ3?>0, then the equation has three distinct real roots.
If \Delta_3 = 0Δ3?=0, then the equation has a repeated root and all its roots are real.
If \Delta_3 < 0Δ3?<0, then the equation has one real root and two non-real complex conjugate roots.

Discriminant, in mathematics, a parameter of an object or system calculated as an aid to its classification or solution. In the case of a quadratic equation ax² + bx + c = 0, the discriminant is b² ? 4ac; for a cubic equation x³ + ax² + bx + c = 0, the discriminant is a²b² + 18abc ? 4b³ ? 4a³c ? 27c². The roots of a quadratic or cubic equation with real coefficients are real and distinct if the discriminant is positive, are real with at least two equal if the discriminant is zero, and include a conjugate pair of complex roots if the discriminant is negative. A discriminant can be found for the general quadratic, or conic, equation ax² + bxy + cy² + dx + ey + f = 0; it indicates whether the conic represented is an ellipse, a hyperbola, or a parabola.

In this paper we revisit the addition of elliptic curves and give an algebraic proof to the associative law by use of MATHEMATICA. The existing proofs of the associative law are rather complicated and hard to understand for beginners. An ‘‘elementary” proof to it based on algebra has not been given as far as we know. Undergraduates or non-experts can master the addition of elliptic curves through this paper. After mastering it they should challenge the elliptic curve cryptography.

Keywords:

Elliptic Curve, Addition, Associative Law, MATHEMATICA, Elliptic Curve Cryptography

1. Introduction

Ciphering is essential for the security of internet. The RSA cryptography [1] [2] [3] is now commonly used. However, in the very near future the RSA cryptography will be replaced by the elliptic curve cryptography because of its efficiency; the RSA system is based on 2048 bits, while the elliptic system is based on 224 bits (2016, [4] ).

The target reader of this note is undergraduates or non-experts. Those who are interested in cryptography are strongly encouraged to master the theory of elliptic curve cryptography as soon as possible. For this purpose they must study an additional structure of elliptic curves. However, it is not so hard except for the associative law.

As far as we know an algebraic proof to it has not yet been given¹. Therefore, we give an ‘‘elementary” proof by use of MATHEMATICA for them.

2. Addition of Points of an Elliptic Curve

Let us start by recalling the definition of an elliptic curve [5] [6]

??2=??3+????+??y2=x3+ax+b(1)

where a and b are some real constants. In the following we consider only real category. The discriminant of the cubic equation

??3+????+??=0x3+ax+b=0

is given by

??=?4??3?27??2D=?4a3?27b2(2)

(see for example [5] ) and we assume ??<0D<0 in the following, so the point crossing the real axis is just one.

For the graph of the elliptic curve (1)

??={(??,??)∈??2∣∣??2=??3+????+??}E={(x,y)∈R2?|?y2=x3+ax+b}(3)

we want to introduce an addition, which is essential in the elliptic curve cryptography. For the purpose we must add the infinity point ??=(∞,∞)O=(∞,∞) to (3). As a result, our space is not ??2R2 but a two dimensional sphere ??2∪??=??2R2∪O=S2 . Later it turns out that O is the identity element of the addition, see (10), (11). This justifies the notation O for the infinity point.

Here we note

??=(??,??)∈??????=(??,???)∈??P=(x,y)∈E????P=(x,?y)∈E(4)

where we have adopted the notation ????P for the mirror image of ??P with respect to the real axis, see (11).

Let us introduce the addition in E. For two points ??1,??2∈??P1,P2∈E we associate another point ??3∈??P3∈E . Consider the straight line passing through ??1P1 and ??2P2 . We set R the crossing point of the line and the elliptic curve.

A simple-minded candidate of the addition is

??1⊕??2=??P1⊕P2=R

Unfortunately, this is not good because the associative law does not hold. Instead, we take the reflection point of R

??1⊕??2=???≡??3.P1⊕P2=?R≡P3.(5)

This is correct as shown in the paper. See the following Figure 1.

Next, we want to express the addition above by use of the coordinate system. For the purpose we set

??1=(??1,??1),??2=(??2,??2)and??3=(??3,??3).P1=(x1,y1),?P2=(x2,y2)??and??P3=(x3,y3).

Formula The addition formula

(??1,??1)⊕(??2,??2)=(??3,??3)(x1,y1)⊕(x2,y2)=(x3,y3)

is given by

??3=(??2???1??2???1)2?(??1+??2),x3=(y2?y1x2?x1)2?(x1+x2),

??3=?(??2???1??2???1)3+(??2???1??2???1)(2??1+??2)???1.y3=?(y2?y1x2?x1)3+(y2?y1x2?x1)(2x1+x2)?y1.(6)

Proof To give an elementary proof for undergraduates or non-experts is educational.

First of all we set the coordinate of the point ??=(????,????)R=(xr,yr) and look for ????xr and ????yr . The straight line passing through ??1P1 and ??2P2 is given by

??=??2???1??2???1(?????1)+??1.y=y2?y1x2?x1(x?x1)+y1.

By taking ?????1x?x1 into consideration we have

??2=??3+????+??=(?????1+??1)3+??(?????1+??1)+??=(?????1)3+3(?????1)2??1+3(?????1)??21+??(?????1)+??31+????1+??=(?????1)3+3(?????1)2??1+3(?????1)??21+??(?????1)+??21.y2=x3+ax+b=(x?x1+x1)3+a(x?x1+x1)+b=(x?x1)3+3(x?x1)2x1+3(x?x1)x12+a(x?x1)+x13+ax1+b=(x?x1)3+3(x?x1)2x1+3(x?x1)x12+a(x?x1)+y12.

We substitute the straight line for the equation above

(??2???1??2???1)2(?????1)2+2??2???1??2???1(?????1)??1+??21=(?????1)3+3(?????1)2??1+3(?????1)??21+??(?????1)+??21.(y2?y1x2?x1)2(x?x1)2+2y2?y1x2?x1(x?x1)y1+y12=(x?x1)3+3(x?x1)2x1+3(x?x1)x12+a(x?x1)+y12.

A short calculation gives

(??2???1??2???1)2(?????1)+2??2???1??2???1??1=(?????1)2+3??1(?????1)+3??21+??(y2?y1x2?x1)2(x?x1)+2y2?y1x2?x1y1=(x?x1)2+3x1(x?x1)+3x12+a

and

(?????1)2?{(??2???1??2???1)2?3??1}(?????1)+3??21?2??2???1??2???1??1+??=0.(x?x1)2?{(y2?y1x2?x1)2?3x1}(x?x1)+3x12?2y2?y1x2?x1y1+a=0.

This is a quadratic equation and it is easy to solve

?????1=12{(??2???1??2???1)2?3??1±{(??2???1??2???1)2?3??1}2?4(3??21?2??2???1??2???1??1+??)￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣√}.x?x1=12{(y2?y1x2?x1)2?3x1±{(y2?y1x2?x1)2?3x1}2?4(3x12?2y2?y1x2?x1y1+a)}.

Here we set

(#)={(??2???1??2???1)2?3??1}2?4(3??21?2??2???1??2???1??1+??).(#)={(y2?y1x2?x1)2?3x1}2?4(3x12?2y2?y1x2?x1y1+a).

By expanding and arranging (#)(#) we have

(#)=(??2???1??2???1)4?6??1(??2???1??2???1)2+8??2???1??2???1??1?3??21?4??.(#)=(y2?y1x2?x1)4?6x1(y2?y1x2?x1)2+8y2?y1x2?x1y1?3x12?4a.

Some calculation (this is a key point) gives

(#)=(??2???1??2???1)4?6??1(??2???1??2???1)2?4(??2???1)2??2???1+4(??2???1)2??2???1+8??2???1??2???1??1?3??21?4??=(??2???1??2???1)4?{6??1+4(??2???1)}(??2???1??2???1)2+4(??2???1){(??2???1)+2??1}??2???1?3??21?4??=(??2???1??2???1)4?2(2??2+??1)(??2???1??2???1)2+4??22???21??2???1?3??21?4??(#)=(y2?y1x2?x1)4?6x1(y2?y1x2?x1)2?4(y2?y1)2x2?x1??+4(y2?y1)2x2?x1+8y2?y1x2?x1y1?3x12?4a=(y2?y1x2?x1)4??{6x1+4(x2?x1)}(y2?y1x2?x1)2??+4(y2?y1){(y2?y1)+2y1}x2?x1?3x12?4a=(y2?y1x2?x1)4?2(2x2+x1)(y2?y1x2?x1)2+4y22?y12x2?x1?3x12?4a

=(??2???1??2???1)4?2(2??2+??1)(??2???1??2???1)2+4(??22+??2??1+??21+??)?3??21?4??=(??2???1??2???1)4?2(2??2+??1)(??2???1??2???1)2+4??22+4??2??1+??21=(??2???1??2???1)4?2(2??2+??1)(??2???1??2???1)2+(2??2+??1)2={(??2???1??2???1)2?2??2???1}2=(y2?y1x2?x1)4?2(2x2+x1)(y2?y1x2?x1)2+4(x22+x2x1+x12+a)?3x12?4a=(y2?y1x2?x1)4?2(2x2+x1)(y2?y1x2?x1)2+4x22+4x2x1+x12=(y2?y1x2?x1)4?2(2x2+x1)(y2?y1x2?x1)2+(2x2+x1)2={(y2?y1x2?x1)2?2x2?x1}2

where in the process we have used the equation

??22???21=(??32+????2+??)?(??31+????1+??)=(??2???1)(??22+??2??1+??21+??).y22?y12=(x23+ax2+b)?(x13+ax1+b)=(x2?x1)(x22+x2x1+x12+a).

Therefore

?????1=12{(??2???1??2???1)2?3??1+(??2???1??2???1)2?2??2???1}=12{2(??2???1??2???1)2?4??1?2??2}=(??2???1??2???1)2?(2??1+??2)x?x1=12{(y2?y1x2?x1)2?3x1+(y2?y1x2?x1)2?2x2?x1}=12{2(y2?y1x2?x1)2?4x1?2x2}=(y2?y1x2?x1)2?(2x1+x2)

and we finally obtain

????=(??2???1??2???1)2?(??1+??2),xr=(y2?y1x2?x1)2?(x1+x2),

which is symmetric in 1 and 2. Another solution is ??=??2x=x2 (check this).

This gives

????=??2???1??2???1(???????1)+??1=??2???1??2???1{(??2???1??2???1)2?(2??1+??2)}+??1=(??2???1??2???1)3?(??2???1??2???1)(2??1+??2)+??1.yr=y2?y1x2?x1(xr?x1)+y1=y2?y1x2?x1{(y2?y1x2?x1)2?(2x1+x2)}+y1=(y2?y1x2?x1)3?(y2?y1x2?x1)(2x1+x2)+y1.

As a result we have

(??3,??3)=(????,?????)(x3,y3)=(xr,?yr)

and this gives the Formula (6).

Comment From the geometric definition of the addition (5) it is easy to see the commutativity

??1⊕??2=??2⊕??1.P1⊕P2=P2⊕P1.

However, it is not clear to see this from the Formula (6). Then, a small change of ??3y3 in (6) gives

??3=?(??2???1??2???1)3+(??2???1??2???1)(??1+??2)+??2??1???1??2??2???1,y3=?(y2?y1x2?x1)3+(y2?y1x2?x1)(x1+x2)+y2x1?y1x2x2?x1,(7)

which is anti-symmetric in 1 and 2. The commutativity is very clear. In our opinion this formula is best.

Next, we must define the addition ??⊕??P⊕P of the same point P. The definition is usually performed by differential. By noting

lim2→1??2???1??2???1=??′1lim2→1y2?y1x2?x1=y′1

the differential of ??2=??3+????+??y2=x3+ax+b at (??1,??1)(x1,y1) gives

2??1??′1=3??21+?????′1=3??21+??2??1.2y1y′1=3x12+a???y′1=3x12+a2y1.

If we set for ??(??,??)P(x,y)

??⊕??=??3or(??,??)⊕(??,??)=(??3,??3)P⊕P=P3???or???(x,y)⊕(x,y)=(x3,y3)(8)

then we obtain

??3=(3??2+??2??)2?2??,x3=(3x2+a2y)2?2x,

??3=?(3??2+??2??)3+(3??2+??2??)3?????y3=?(3x2+a2y)3+(3x2+a2y)3x?y(9)

by applying the argument above to (6). See the following Figure 2.

There are tasks left behind. Our tasks are to show

??⊕??=??⊕??=??P⊕O=O⊕P=P(10)

and

??⊕(???)=(???)⊕??=??.P⊕(?P)=(?P)⊕P=O.(11)

Exercise Consider a proof with the geometric method.

Last, we must prove the associative law

(??1⊕??2)⊕??3=??1⊕(??2⊕??3),(P1⊕P2)⊕P3=P1⊕(P2⊕P3),(12)

which is very hard for undergraduates (hard even for experts).

The geometric method usually goes like Figure 3 ( ??1=??P1=P , ??2=??P2=Q and ??3=??P3=R in this figure)

However, this is not a proof but a circumstantial evidence. Therefore, we give an algebraic proof by use of MATHEMATICA².

For the purpose let us calculate the difference

(??1⊕??2)⊕??3???1⊕(??2⊕??3)(P1⊕P2)⊕P3?P1⊕(P2⊕P3)(13)

by MATHEMATICA. In the following program we set

(??1⊕??2)⊕??3???1⊕(??2⊕??3)=(?????????,?????????).(P1⊕P2)⊕P3?P1⊕(P2⊕P3)=(CC?FF,DD?GG).(14)

and use the Formula (7) because of its high symmetry. Associativity holds when the right hand side vanishes.

Beginning of MATHEMATICA

Readers must input and execute the following program in standard form of MATHEMATICA.

We set

??=(??2???1??2???1)2?(??1+??2);s=(y2?y1x2?x1)2?(x1+x2);

??=?(??2???1??2???1)3+(??2???1??2???1)(??1+??2)+Det[(??1??1??2??2)]??2???1;t=?(y2?y1x2?x1)3+(y2?y1x2?x1)(x1+x2)+Det[(x1x2y1y2)]x2?x1;

and

????=(??3?????3???)2?(??+??3);CC=(y3?tx3?s)2?(s+x3);

????=?(??3?????3???)3+(??3?????3???)(??+??3)+Det[(??????3??3)]??3???;DD=?(y3?tx3?s)3+(y3?tx3?s)(s+x3)+Det[(sx3ty3)]x3?s;

and also set

??=(??3???2??3???2)2?(??2+??3);u=(y3?y2x3?x2)2?(x2+x3);

??=?(??3???2??3???2)3+(??3???2??3???2)(??2+??3)+Det[(??2??2??3??3)]??3???2;v=?(y3?y2x3?x2)3+(y3?y2x3?x2)(x2+x3)+Det[(x2x3y2y3)]x3?x2;

and

????=(?????1?????1)2?(??1+??);FF=(v?y1u?x1)2?(x1+u);

????=?(?????1?????1)3+(?????1?????1)(??1+??)+Det[(??1??1????)]?????1.GG=?(v?y1u?x1)3+(v?y1u?x1)(x1+u)+Det[(x1uy1v)]u?x1.

Moreover, we set

??=(??1???2)2?(??1???2)2(??1+??2+??3);P=(y1?y2)2?(x1?x2)2(x1+x2+x3);

??=(??2???3)2?(??2???3)2(??1+??2+??3);Q=(y2?y3)2?(x2?x3)2(x1+x2+x3);

??=(??2???3)??21+(??3???1)??22+(??1???2)??23+(??1???2)(??2???3)(??3???1)(??1+??2+??3).R=(x2?x3)y12+(x3?x1)y22+(x1?x2)y32??+(x1?x2)(x2?x3)(x3?x1)(x1+x2+x3).

Here, ??2P2 ( ??2Q2 ) appears in the denominator of ????CC ( ????FF ) and ??3P3 ( ??3Q3 ) in the denominator of ????DD (GG). The homogeneous polynomials P and Q are invariant under the permutation of 1,2,31,2,3 , whereas R changes sign.

For

????=??2??2(?????????)??;????=??3??3(?????????)??;AA=P2Q2(CC?FF)R;?BB=P3Q3(DD?GG)R;

execute the following

Factor[????]Factor[AA]

Factor[????]Factor[BB]

Ending of MATHEMATICA

It takes about several seconds for a standard present day PC before MATHEMATICA outputs two huge homogeneous polynomials in ??1x1 , ??2x2 , ??3x3 , ??1y1 , ??2y2 and ??3y3 of integer coefficients. The “degrees” of ????AA and ????BB are 9 and 31/2, respectively, when “degree” 1 is assigned to ??1x1 , ??2x2 , ??3x3 and 3/2 for ??1y1 , ??2y2 and ??3y3 , see the curve Equation (1). In other words, ????AA and ????BB are universal polynomials of elliptic curves which are independent of the parameters a and b. More than 10 pages are required to write down the outputs. As we will see their explicit forms are irrelevant for the discussion of the associativity, we do not display them here. These polynomials have many interesting features.

From the program we have

?????????=??????2??2??,?????????=??????3??3??.CC?FF=AAP2Q2R,?DD?GG=BBP3Q3R.(15)

It is very interesting and important that both have a common factor R. Note that we have not imposed the equations

???????21=??31+????1+????22=??32+????2+????23=??33+????3+??{y12=x13+ax1+by22=x23+ax2+by32=x33+ax3+b(16)

up to this point.

Last, we show

??=0R=0(17)

under the condition (16), which finishes the proof of associativity (14).

Here, let us give an educational proof for undergraduates. We treat the following determinant :

??=∣∣∣∣∣1??1??211??2??221??3??23∣∣∣∣∣X=|111x1x2x3y12y22y32|(18)

Direct calculation gives

??=??2??23+??3??21+??1??22???2??21???1??23???3??22=?{(??2???3)??21+(??3???1)??22+(??1???2)??23}.X=x2y32+x3y12+x1y22?x2y12?x1y32?x3y22=?{(x2?x3)y12+(x3?x1)y22+(x1?x2)y32}.(19)

On the other hand, from (16) we have

??=∣∣∣∣∣1??1??31+????1+??1??2??32+????2+??1??3??33+????3+??∣∣∣∣∣=∣∣∣∣∣1??1??31+????11??2??32+????21??3??33+????3∣∣∣∣∣=∣∣∣∣∣1??1??311??2??321??3??33∣∣∣∣∣X=|111x1x2x3x13+ax1+bx23+ax2+bx33+ax3+b|=|111x1x2x3x13+ax1x23+ax2x33+ax3|=|111x1x2x3x13x23x33|

by some fundamental operations.

Moreover, we have

??=∣∣∣∣∣1??1??310??2???1??32???310??3???1??33???31∣∣∣∣∣=(??2???1)(??3???1)∣∣∣∣∣1??1??3101??22+??2??1+??2101??23+??3??1+??21∣∣∣∣∣=(??2???1)(??3???1)∣∣∣∣∣1??1??3101??22+??2??1+??2100(??3???2)(??3+??2+??1)∣∣∣∣∣=(??2???1)(??3???1)(??3???2)(??3+??2+??1)=(??1???2)(??2???3)(??3???1)(??1+??2+??3)X=|100x1x2?x1x3?x1x13x23?x13x33?x13|=(x2?x1)(x3?x1)|100x111x13x22+x2x1+x12x32+x3x1+x12|=(x2?x1)(x3?x1)|100x110x13x22+x2x1+x12(x3?x2)(x3+x2+x1)|=(x2?x1)(x3?x1)(x3?x2)(x3+x2+x1)=(x1?x2)(x2?x3)(x3?x1)(x1+x2+x3)(20)

by some fundamental operations. As a result, we obtain

??=(??2???3)??21+(??3???1)??22+(??1???2)??23+(??1???2)(??2???3)(??3???1)(??1+??2+??3)=???+??=0R=(x2?x3)y12+(x3?x1)y22+(x1?x2)y32??+(x1?x2)(x2?x3)(x3?x1)(x1+x2+x3)=?X+X=0

by (19) and (20).

As shown in the paper the elementary proof of the associative law of the points of an elliptic curve is not easy. However, it is not necessarily a bad thing for the encryption system.

In this section we reproved the following

Theorem The system {??,⊕}{E,⊕} becomes an additive (abelian) group.

3. Concluding Remarks

We conclude the paper by making some comments on the elliptic curve cryptography [7] [8] .

Let p be a huge prime number and ????Fp be the finite field

????={0,1,2,?,???1},Fp={0,1,2,?,p?1},

see for example [5] .

Our target is an elliptic curve on ????Fp

????={(??,??)∣∣??2=??3+????+??(mod??)}.Ep={(x,y)?|y2=x3+ax+b?(modp)}.

For this case ????Ep becomes a finite set. We assume that ??P and ??∈????Q∈Ep satisfy the relation

??=??⊕??(mod??)Q=n⊕P?(?modp)

where

??⊕??=??⊕??⊕?⊕??(??-times).n⊕P=P⊕P⊕?⊕P?(n-?times).

Problem For given P and Q is it possible to find n in polynomial time?

This is called the discrete logarithm problem and it is known as a very hard one to solve [9] . The security of the elliptic curve cryptography (which is worth studying for undergraduates or non-experts) is based on this hard problem.

Acknowledgements

We wishes to thank Ryu Sasaki for useful suggestions and comments.

Cite this paper

Fujii, K. and Oike, H. (2017) An Algebraic Proof of the Associative Law of Elliptic Curves. Advances in Pure Mathematics, 7, 649-659. https://doi.org/10.4236/apm.2017.712040

References

NOTES

¹We don’t admit usual geometric proofs in standard textbooks of elliptic curves.

²We expect that undergraduates in the world can use MATHEMATICA or MAPLE, etc.

associativity ec

原文：https://www.cnblogs.com/Janly/p/14653316.html