APM  Vol.7 No.12 , December 2017
An Algebraic Proof of the Associative Law of Elliptic Curves
ABSTRACT
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.

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 given1. 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]

y 2 = x 3 + a x + b (1)

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

x 3 + a x + b = 0

is given by

D = 4 a 3 27 b 2 (2)

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

For the graph of the elliptic curve (1)

E = { ( x , y ) R 2 | y 2 = x 3 + a x + 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 R 2 but a two dimensional sphere R 2 O = S 2 . 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 P 1 , P 2 E we associate another point P 3 E . Consider the straight line passing through P 1 and P 2 . We set R the crossing point of the line and the elliptic curve.

A simple-minded candidate of the addition is

P 1 P 2 = R

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

P 1 P 2 = R P 3 . (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

P 1 = ( x 1 , y 1 ) , P 2 = ( x 2 , y 2 ) and P 3 = ( x 3 , y 3 ) .

Formula The addition formula

( x 1 , y 1 ) ( x 2 , y 2 ) = ( x 3 , y 3 )

is given by

x 3 = ( y 2 y 1 x 2 x 1 ) 2 ( x 1 + x 2 ) ,

Figure 1. Addition P 1 P 2 .

y 3 = ( y 2 y 1 x 2 x 1 ) 3 + ( y 2 y 1 x 2 x 1 ) ( 2 x 1 + x 2 ) y 1 . (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 = ( x r , y r ) and look for x r and y r . The straight line passing through P 1 and P 2 is given by

y = y 2 y 1 x 2 x 1 ( x x 1 ) + y 1 .

By taking x x 1 into consideration we have

y 2 = x 3 + a x + b = ( x x 1 + x 1 ) 3 + a ( x x 1 + x 1 ) + b = ( x x 1 ) 3 + 3 ( x x 1 ) 2 x 1 + 3 ( x x 1 ) x 1 2 + a ( x x 1 ) + x 1 3 + a x 1 + b = ( x x 1 ) 3 + 3 ( x x 1 ) 2 x 1 + 3 ( x x 1 ) x 1 2 + a ( x x 1 ) + y 1 2 .

We substitute the straight line for the equation above

( y 2 y 1 x 2 x 1 ) 2 ( x x 1 ) 2 + 2 y 2 y 1 x 2 x 1 ( x x 1 ) y 1 + y 1 2 = ( x x 1 ) 3 + 3 ( x x 1 ) 2 x 1 + 3 ( x x 1 ) x 1 2 + a ( x x 1 ) + y 1 2 .

A short calculation gives

( y 2 y 1 x 2 x 1 ) 2 ( x x 1 ) + 2 y 2 y 1 x 2 x 1 y 1 = ( x x 1 ) 2 + 3 x 1 ( x x 1 ) + 3 x 1 2 + a

and

( x x 1 ) 2 { ( y 2 y 1 x 2 x 1 ) 2 3 x 1 } ( x x 1 ) + 3 x 1 2 2 y 2 y 1 x 2 x 1 y 1 + a = 0.

This is a quadratic equation and it is easy to solve

x x 1 = 1 2 { ( y 2 y 1 x 2 x 1 ) 2 3 x 1 ± { ( y 2 y 1 x 2 x 1 ) 2 3 x 1 } 2 4 ( 3 x 1 2 2 y 2 y 1 x 2 x 1 y 1 + a ) } .

Here we set

( # ) = { ( y 2 y 1 x 2 x 1 ) 2 3 x 1 } 2 4 ( 3 x 1 2 2 y 2 y 1 x 2 x 1 y 1 + a ) .

By expanding and arranging ( # ) we have

( # ) = ( y 2 y 1 x 2 x 1 ) 4 6 x 1 ( y 2 y 1 x 2 x 1 ) 2 + 8 y 2 y 1 x 2 x 1 y 1 3 x 1 2 4 a .

Some calculation (this is a key point) gives

( # ) = ( y 2 y 1 x 2 x 1 ) 4 6 x 1 ( y 2 y 1 x 2 x 1 ) 2 4 ( y 2 y 1 ) 2 x 2 x 1 + 4 ( y 2 y 1 ) 2 x 2 x 1 + 8 y 2 y 1 x 2 x 1 y 1 3 x 1 2 4 a = ( y 2 y 1 x 2 x 1 ) 4 { 6 x 1 + 4 ( x 2 x 1 ) } ( y 2 y 1 x 2 x 1 ) 2 + 4 ( y 2 y 1 ) { ( y 2 y 1 ) + 2 y 1 } x 2 x 1 3 x 1 2 4 a = ( y 2 y 1 x 2 x 1 ) 4 2 ( 2 x 2 + x 1 ) ( y 2 y 1 x 2 x 1 ) 2 + 4 y 2 2 y 1 2 x 2 x 1 3 x 1 2 4 a

= ( y 2 y 1 x 2 x 1 ) 4 2 ( 2 x 2 + x 1 ) ( y 2 y 1 x 2 x 1 ) 2 + 4 ( x 2 2 + x 2 x 1 + x 1 2 + a ) 3 x 1 2 4 a = ( y 2 y 1 x 2 x 1 ) 4 2 ( 2 x 2 + x 1 ) ( y 2 y 1 x 2 x 1 ) 2 + 4 x 2 2 + 4 x 2 x 1 + x 1 2 = ( y 2 y 1 x 2 x 1 ) 4 2 ( 2 x 2 + x 1 ) ( y 2 y 1 x 2 x 1 ) 2 + ( 2 x 2 + x 1 ) 2 = { ( y 2 y 1 x 2 x 1 ) 2 2 x 2 x 1 } 2

where in the process we have used the equation

y 2 2 y 1 2 = ( x 2 3 + a x 2 + b ) ( x 1 3 + a x 1 + b ) = ( x 2 x 1 ) ( x 2 2 + x 2 x 1 + x 1 2 + a ) .

Therefore

x x 1 = 1 2 { ( y 2 y 1 x 2 x 1 ) 2 3 x 1 + ( y 2 y 1 x 2 x 1 ) 2 2 x 2 x 1 } = 1 2 { 2 ( y 2 y 1 x 2 x 1 ) 2 4 x 1 2 x 2 } = ( y 2 y 1 x 2 x 1 ) 2 ( 2 x 1 + x 2 )

and we finally obtain

x r = ( y 2 y 1 x 2 x 1 ) 2 ( x 1 + x 2 ) ,

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

This gives

y r = y 2 y 1 x 2 x 1 ( x r x 1 ) + y 1 = y 2 y 1 x 2 x 1 { ( y 2 y 1 x 2 x 1 ) 2 ( 2 x 1 + x 2 ) } + y 1 = ( y 2 y 1 x 2 x 1 ) 3 ( y 2 y 1 x 2 x 1 ) ( 2 x 1 + x 2 ) + y 1 .

As a result we have

( x 3 , y 3 ) = ( x r , y r )

and this gives the Formula (6).

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

P 1 P 2 = P 2 P 1 .

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

y 3 = ( y 2 y 1 x 2 x 1 ) 3 + ( y 2 y 1 x 2 x 1 ) ( x 1 + x 2 ) + y 2 x 1 y 1 x 2 x 2 x 1 , (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

lim 2 1 y 2 y 1 x 2 x 1 = y 1

the differential of y 2 = x 3 + a x + b at ( x 1 , y 1 ) gives

2 y 1 y 1 = 3 x 1 2 + a y 1 = 3 x 1 2 + a 2 y 1 .

If we set for P ( x , y )

P P = P 3 or ( x , y ) ( x , y ) = ( x 3 , y 3 ) (8)

then we obtain

x 3 = ( 3 x 2 + a 2 y ) 2 2 x ,

y 3 = ( 3 x 2 + a 2 y ) 3 + ( 3 x 2 + a 2 y ) 3 x 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

( P 1 P 2 ) P 3 = P 1 ( P 2 P 3 ) , (12)

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

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

Figure 2. Addition P1 = P2 = P.

Figure 3. Associativity ( P Q ) R = P ( Q R ) .

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

For the purpose let us calculate the difference

( P 1 P 2 ) P 3 P 1 ( P 2 P 3 ) (13)

by MATHEMATICA. In the following program we set

( P 1 P 2 ) P 3 P 1 ( P 2 P 3 ) = ( C C F F , D D G G ) . (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

s = ( y 2 y 1 x 2 x 1 ) 2 ( x 1 + x 2 ) ;

t = ( y 2 y 1 x 2 x 1 ) 3 + ( y 2 y 1 x 2 x 1 ) ( x 1 + x 2 ) + Det [ ( x 1 x 2 y 1 y 2 ) ] x 2 x 1 ;

and

C C = ( y 3 t x 3 s ) 2 ( s + x 3 ) ;

D D = ( y 3 t x 3 s ) 3 + ( y 3 t x 3 s ) ( s + x 3 ) + Det [ ( s x 3 t y 3 ) ] x 3 s ;

and also set

u = ( y 3 y 2 x 3 x 2 ) 2 ( x 2 + x 3 ) ;

v = ( y 3 y 2 x 3 x 2 ) 3 + ( y 3 y 2 x 3 x 2 ) ( x 2 + x 3 ) + Det [ ( x 2 x 3 y 2 y 3 ) ] x 3 x 2 ;

and

F F = ( v y 1 u x 1 ) 2 ( x 1 + u ) ;

G G = ( v y 1 u x 1 ) 3 + ( v y 1 u x 1 ) ( x 1 + u ) + Det [ ( x 1 u y 1 v ) ] u x 1 .

Moreover, we set

P = ( y 1 y 2 ) 2 ( x 1 x 2 ) 2 ( x 1 + x 2 + x 3 ) ;

Q = ( y 2 y 3 ) 2 ( x 2 x 3 ) 2 ( x 1 + x 2 + x 3 ) ;

R = ( x 2 x 3 ) y 1 2 + ( x 3 x 1 ) y 2 2 + ( x 1 x 2 ) y 3 2 + ( x 1 x 2 ) ( x 2 x 3 ) ( x 3 x 1 ) ( x 1 + x 2 + x 3 ) .

Here, P 2 ( Q 2 ) appears in the denominator of C C ( F F ) and P 3 ( Q 3 ) in the denominator of D D (GG). The homogeneous polynomials P and Q are invariant under the permutation of 1,2,3 , whereas R changes sign.

For

A A = P 2 Q 2 ( C C F F ) R ; B B = P 3 Q 3 ( D D G G ) R ;

execute the following

Factor [ A A ]

Factor [ B B ]

Ending of MATHEMATICA

It takes about several seconds for a standard present day PC before MATHEMATICA outputs two huge homogeneous polynomials in x 1 , x 2 , x 3 , y 1 , y 2 and y 3 of integer coefficients. The “degrees” of A A and B B are 9 and 31/2, respectively, when “degree” 1 is assigned to x 1 , x 2 , x 3 and 3/2 for y 1 , y 2 and y 3 , see the curve Equation (1). In other words, A A and B B 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

C C F F = A A P 2 Q 2 R , D D G G = B B P 3 Q 3 R . (15)

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

{ y 1 2 = x 1 3 + a x 1 + b y 2 2 = x 2 3 + a x 2 + b y 3 2 = x 3 3 + a x 3 + b (16)

up to this point.

Last, we show

R = 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 :

X = | 1 1 1 x 1 x 2 x 3 y 1 2 y 2 2 y 3 2 | (18)

Direct calculation gives

X = x 2 y 3 2 + x 3 y 1 2 + x 1 y 2 2 x 2 y 1 2 x 1 y 3 2 x 3 y 2 2 = { ( x 2 x 3 ) y 1 2 + ( x 3 x 1 ) y 2 2 + ( x 1 x 2 ) y 3 2 } . (19)

On the other hand, from (16) we have

X = | 1 1 1 x 1 x 2 x 3 x 1 3 + a x 1 + b x 2 3 + a x 2 + b x 3 3 + a x 3 + b | = | 1 1 1 x 1 x 2 x 3 x 1 3 + a x 1 x 2 3 + a x 2 x 3 3 + a x 3 | = | 1 1 1 x 1 x 2 x 3 x 1 3 x 2 3 x 3 3 |

by some fundamental operations.

Moreover, we have

X = | 1 0 0 x 1 x 2 x 1 x 3 x 1 x 1 3 x 2 3 x 1 3 x 3 3 x 1 3 | = ( x 2 x 1 ) ( x 3 x 1 ) | 1 0 0 x 1 1 1 x 1 3 x 2 2 + x 2 x 1 + x 1 2 x 3 2 + x 3 x 1 + x 1 2 | = ( x 2 x 1 ) ( x 3 x 1 ) | 1 0 0 x 1 1 0 x 1 3 x 2 2 + x 2 x 1 + x 1 2 ( x 3 x 2 ) ( x 3 + x 2 + x 1 ) | = ( x 2 x 1 ) ( x 3 x 1 ) ( x 3 x 2 ) ( x 3 + x 2 + x 1 ) = ( x 1 x 2 ) ( x 2 x 3 ) ( x 3 x 1 ) ( x 1 + x 2 + x 3 ) (20)

by some fundamental operations. As a result, we obtain

R = ( x 2 x 3 ) y 1 2 + ( x 3 x 1 ) y 2 2 + ( x 1 x 2 ) y 3 2 + ( x 1 x 2 ) ( x 2 x 3 ) ( x 3 x 1 ) ( x 1 + x 2 + x 3 ) = 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 F p be the finite field

F p = { 0,1,2, , p 1 } ,

see for example [5] .

Our target is an elliptic curve on F p

E p = { ( x , y ) | y 2 = x 3 + a x + b ( mod p ) } .

For this case E p becomes a finite set. We assume that P and Q E p satisfy the relation

Q = n P ( mod p )

where

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.

NOTES

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

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

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. doi: 10.4236/apm.2017.712040.
References
[1]   Diffie, W. and Hellman, M. (1976) New Directions in Cryptography. IEEE Transactions on Information Theory, 22, 644-654.
https://doi.org/10.1109/TIT.1976.1055638

[2]   Rivest, R.L., Shamir, A. and Adleman, L. (1978) A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21, 120-126.
https://doi.org/10.1145/359340.359342

[3]   ELGamal, T. (1985) A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, 469-472.
https://doi.org/10.1109/TIT.1985.1057074

[4]   Nakanishi, T. (2017) Mechanisms of Modern Cryptography. Kyoritsu Smart Selection 12, Kyoritsu Shuppan.

[5]   Silverman, J.H. (2006) A Friendly Introduction to NUMBER THEORY. 3rd Edition, Pearson Education, London.

[6]   Silverman, J.H. and Tate, J. (1992) Rational Points on Elliptic Curves. Springer-Verlag, Berlin.
https://doi.org/10.1007/978-1-4757-4252-7

[7]   Koblitz, N. (1987) Elliptic Curve Cryptosystems. Mathematics of Computation, 48, 203-209.
https://doi.org/10.1090/S0025-5718-1987-0866109-5

[8]   Fujii, K. (2014-2016) Public-Key Cryptography and Its Decoding by Quantum Computation (in Japanese). Lecture Note at Yokohama City University, Yokohama, 39.

[9]   Shor, P.W. (1999) Polynomial—Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 41, 303-332.
https://doi.org/10.1137/S0036144598347011

 
 
Top