Introduction

The elliptic curves are a very fashionable subject in mathematics. They are the basis of the demonstration of Fermat’s great theorem by Andrew Wiles, it was proposed for cryptographic use independently by Neal Koblitz[1] and Victor Miller in 1985, claim that elliptic curve cryptography requires much smaller keys than those used in conventional public key cryptosystems, while maintaining an equal level of security. In 2008, Virat introduced the elliptic curves over local ring F_p[] = F_p[X]/(X²)[2], and a proposed a new public key cryptosystem which is a variant of the ElGamal cryptosystem on an elliptic curve, in 2013 Chillali generalized the Virat result for the ring F_p

Chillali and Abdelalim constructed a ring F_p[e₁,e₂,e₃], defined an elliptic curve over E_a,b(F_p[e₁,e₂,e₃]) and they showed that Card(E_a,b(^Fp[e₁,e₂,e₃])) ≥ (Card(E_a,b(^Fp))− 3)ⁿ +Card(E_a,b(Fp)) [4].

In this work we will generalize the construction of Fp[e₁,e₂,e₃] to Fp[e₁,..,e_n], but not a local ring to define a group law in F_p[e₁,..,e_n],we localized the ring F_p[e₁,..,e_n] in a maximal ideal, and we give it a group law and show that Card(E_a,b(F_p[e₁,..,e_n])) ≥ (Card(E_a,b(Fp)) − 3)ⁿ + Card(E_a,b(Fp)), then shows the discrete logarithmic complexity is Ω(N) Such that N = E_a,b(F_p) by using the attacks baby step/giant step and ρ−Pollard.

Let p be an odd prime number and n be an integer such that n ≥ 1. we consider the ring A_n = F_p[e₁,…,e_n] = ^{a₀+a₁e₁+…+a_ne_n/a₀,a₁,…,a_n ^∈Fp, e_ie_i = e_i and e_ie_j = 0 if i , j}. F_p[e₁,…,e_n,] is vector space over F_p with basis (1,e₁,…,e_n). We have

X +Y = (x₀ +y₀)+(x₁ +x₁)e₁ +…+(x_n +y_n)e_n and X.Y = t₀ +t₁e₁ +…+t_ne_n with:

⁽ t₀ = x₀y₀                                      if    i = 0

t_i = x_iy₀ +x₀y_i +x_iy_i if           i , 0

Proposition 1. Let X = x₀ +x₁e₁ +…+x_ne_n ^∈Fp[e₁,…,e_n] then X is invertible if and only if x₀ , 0 and x_i , −x₀ for all i ^∈{1,…,n^}.

Proof. Let X = x₀+x₁e₁+…+x_ne_n ∈^F_p[e₁,…,e_n] a invertible element, there Y = y₀ +y₁e₁ +…+y_ne_n ∈Fp[e₁,…,e_n] such that X.Y = 1, this implies that

⁽ x₀y₀ = 1                         if     i = 0

x_iy₀ +x₀y_i +x_iy_i = 0 if           i , 0

therefore, x₀ , 0 and x_i ,−x₀ for all i ∈{1,…,n}. In this case:

( y0 = x0−1                                  if    i = 0

yi = −(x0 +xi)−1xix0−1 if         i , 0

The other since is evident.

Proposition 2. The ideal P = (e₁,…,e_n) is a maximal

(prime) of a ring F_p[e₁,…,e_n].

Proof. We have F_p[e₁,…,e_n]/P ‘ F_p is a field, there P is maximal.

Proposition 3. Let S = Fp[e₁,…,e_n]− P = {s₀ + s₁e₁ + … + s_ne_n/s₀ ∈ Fp,s₀ , 0}. Then the localized of Fp[e₁,…,e_n] in P is:

AP = {xs00++xs11ee11++……++sxnneenn /x0,x1,…,xn,s0,s1,…,sn ∈Fp,s0 , 0}

= {x0 +x1e1 +…+xnen /x0,x1,…,xn,s1,…,sn ∈Fp}

1+s₁e₁ +…+s_ne_n

A_P is a local ring its maximal ideal is

M = {1+x1se11e+1+……++xnsnenen /x1,…,xn,s1,…,sn ∈Fp} and the residual field is K ^‘Fp.

Proposition 4. The homomorphism :

π : A_P                       −→ F_p

x1+0+sx₁1ee₁1++……++sx_nnee_nn −^→  x₀

is a surjective homomorphism of rings.

2     The Elliptic Curve over the ring A_P

Let n ∈ _N^∗, A = Fp[e₁,…,e_n], p a prime number p ≥ 5, P = (e₁,…,e_n) and A_P the localized of A in P .

Definition 1. An elliptic curve over ring A_P is curve that is given by such Weierstrass equation:

Y²Z = X³ +aXZ² +bZ³

with a,b ∈ A_P and 4a³ + 27b² is invertible on A_P , and the reduction over F_p is

Y²Z = X³ +π(a)XZ² +π(b)Z³

E_a,b(Fp) = ^{[X : Y : Z] ^∈_P²(Fp)/Y²Z = X³ +aXZ² +bZ^3}

E_a,b(A) = ^{[X : Y : Z] ^∈_P²(A)/Y²Z = X³ +aXZ² +bZ^3} Ea,b(AP ) = {[X : Y : Z] ∈P2(AP )/Y2Z = X3 +aXZ2 +bZ3}

Theorem 1. The mapping
φ : Ea,b(A) [x : y : z]	−→ −→	Ea,b(AP ) [1x : y1 : 1z ]

is injective.

Proof. Let [x : y : z],[x⁰ : y⁰ : z⁰] ∈ E_a,b(A) Suppose that [x : y : z] = [x⁰ : y⁰ : z⁰]

⇒ ∃λ ∈ A such that (x⁰,y⁰,z⁰) = λ(x,y,z)

⇒ (x⁰,y⁰,z⁰) = (λx,λy,λz)

⇒ x⁰ = λx, y λy and z⁰ = λz

⇒  and

Then [

we deduce that φ([x : y : z]) = φ([x⁰ : y⁰ : z⁰])

Then φ is well defined.

f : A ^−→ A^P is injective. Note that mapping x _{−→ 1}x

We deduce φ is injective.

Theorem 2. Let a,b ∈_Fp, the mapping

ϕ : Ea,b(AP )     −→                  Ea,b(A)

[sx1 : sy2 : sz3] −→ [xs2s3 : ys1s3 : zs1s2] is surjective.

Proof. Let [_s^x1 : ^{y                z             0         0         0}                       (A )

Suppose that [_s

Then ∃λ ∈ A∗P such that (sx1 s2 s3                           (s1, s2, sz3)

⇒ sx00 = λsx1; sy200 = λsy2; sz3sz3

1

⇒ s1s2s3 sx100 = λs2s3x; s1s2s3 sy200 = λs1s3y; s1s2s3 sz300 = λs1s2z

Then ϕ[sx00 : sy00 : sy00 ] = ϕ[s1s2s3 sx00 : s1s2s3 sy00 : s1s2s3 sz300 ]

Then ϕ is well defined.

Let [x : y : z] ∈ E_a,b(A), we have ϕ[₁^x : ^y₁ : ₁^z ] = [x : y : z].

Finally the mapping ϕ is surjective.

Corollary 1. Let a,b ∈_Fp, then

Card(E_a,b(A_P )) = Card(E_a,b(A))

Proposition 5. A Weierstrass equation is defined a elliptic curve over A_P if and only if the reduction ever F_p is a elliptic curve.

Proposition 6. Let a,b ∈ A_P such that 4a³+27b² is invertible on A_P .The set E_a,b(A_P ) together with a special point O = [0 : 1 : 0], a commutative binary operation denoted by +. It is well known that the binary operation + endows the set E_a,b(A_P ) with an abelian group with O as identity element.

Proof. The proof in M.Virat theses[2] page 56, based on [5] page 117 corollary 6.6 and [6] page 63.

Proposition 7. Let P = [x : y : z] and P ⁰ = [x⁰ : y⁰ : z⁰] in E_a,b(A_P ), we have

1. if π_Ea,b(A_P )(P ) , π_Ea,b(A_P )(P ⁰) then P + P ⁰ = [p₁ : q₁ : r₁] with p1 = y2x0z0 − zxy02 − a(zx0 + xz0)(zx0 − xz0)+(2yy0 −

3bzz⁰)(zx^{0 −}xz⁰)

q1 = yy0(z0y − zy0) − a(xyz02 − z2x0y0) + (−2azz0 − 3xx⁰)(x⁰y ⁻xy⁰)⁻3bzz⁰(z⁰y ⁻zy⁰) r₁ = (zy⁰ +z⁰y)(z⁰y ⁻zy⁰)+(3xx⁰ +azz⁰)(zx^{0 −}xz⁰)

2. if π_Ea,b(R)(P ) = π_Ea,b(R)(P ⁰) then P + P ⁰ = [p₂ : q₂ : r₂] with

p₂ = (yy⁰ − bzz⁰)(x⁰y + xy⁰) + (a²zz⁰ − 2axx⁰)(zy⁰ + z0y)−3b(xyz02 +z2x0y0)−a(yzx02 +x2y0z0)

q2 = y2y02 + 3ax2x02 + (−a3 − 9b2)z2z02 − a2(zx0 + xz⁰)^{2 −}2a²zxz⁰x⁰ +(9bxx^{0 −}3abzz⁰)(zx⁰ +xz⁰) r₂ = (yy⁰ + 3bzz⁰)(zy⁰ + z⁰y) + (3xx⁰ + 2azz⁰)(x⁰y + xy⁰)+a(xyz⁰² +z²x⁰y⁰)

Proof. The proof in M.Virat theses[2] page 57 Proposition 2.1.2. based on formulas I, II and III in the article of H.Lange and W.Ruppert[7].

Corollary 2. The mapping

πE(A_P ) : E(AP )           ⁻−^→→   [π(x) :Eπ((Fyp) :⁾ π(z)] is a [x : y : z] homomorphism of groups.

Theorem 3. Let a,b ∈_Fp. Then

Card(E_a,b(A)) > (Card(E_a,b(Fp))−3)ⁿ +Card(E_a,b(Fp))

Proof. The proof for n = 3 exist in article of A.Chilali, S.Abdelalim[4].

For n ∈_N^∗ We consider the set:

T = {[x : y : z]/y²z = x³ +axz² +bz³}

= {[x : 0 : z]/0 = x³ +axz² +bz³} = {[x : 0 : 1]/0 = x³ +ax +b}

then Card(T ) is exactly the number of the solution of

the equation x³ +ax +b = 0 therefore Card(T ) ≤ 3.

Let

G = Ea,n(Fp)−T

= {[x : y : z] ∈_P²(Fp)/y²z = x³ +axz² +bz³ avec y , 0}

= {[x : 1 : z] ∈_P²(Fp)/z = x³ +axz² +bz³}

= ^{[x : 1 : z] ^∈P²(Fp)/[x : 1 : z] ^∈ E_a,n(Fp)^} therefore Card(G) ≥ Card(E_a,n(Fp))−3 We consider the mapping:

α : Gn                     −→                     Ea,b(A)

([xi : yi : zi])ii==1n −→ [Pni=0xiei : 1 : Pin=0ziei] We have:

n                               n

(Xxiei)3 = X(xiei)3

i=0              i=0 n              n

X              2 = X(ziei)2

(        ziei)

i=0             i=0 n n           n

                       X              X

a(        xiei)(             ziei)2 = aX(xiei)(ziei)2

i=0                   i=0                               i=1

Since [x_i : 1 : z_i] ∈ E_a,n(Fp) then z_i = x_i³ +ax_iz_i² +bz_i³. It is clear that : ziei = (xiei)2 +a(xiei)(ziei)2 +b(ziei)3, ∀i ∈{1,..,n}

n                         n                                   n                                                  n

Xziei = X(xiei)3 +aX(xiei)(ziei)2 +bX(ziei)3

i=0                      i=0                                i=0                                               i=0

n                            n                                   n                       n                                   n

X X 3 +a(Xxiei)(Xziei)2 +b(Xziei)3 ziei = ( xiei)

i=0              i=0                  i=0                  i=0                  i=0 we deduce that:

n                                n

                             X                    X

[        x_ie_i : 1 :           z_ie_i] ∈ E_a,b(A)

i=0                            i=0

α is injective. Then

Ea,n(Fp) ⊆ Ea,b(A) α(Gⁿ) ⊆ E_a,b(A)

and E_a,n(Fp)∩α(Gⁿ) = {[0 : 1 : 0]}

We result that

Card(E_a,b(A)) ≥ Card(α(Gⁿ))+Card(E_a,n(Fp))−1

Since α is injective, then

Card(Gⁿ) = Card(G)^{n ≥} Card(E_a,n(Fp)⁻3)ⁿ we deduce that:

Card(E_a,b(A)) ^≥ Card(E_a,n(Fp)⁻1)ⁿ +Card(E_a,n(Fp))

Corollary 3. Let a and b two elements of F_p. Then

Card(E_a,b(A_P )) > (Card(E_a,b(Fp))−3)ⁿ +Card(E_a,b(Fp))

Proof. In Corollary 1 Card(E_a,b(A_P )) = Card(E_a,b(A)), and in Theorem 3

Card(E_a,b(A)) > (Card(E_a,b(Fp))−3)ⁿ +Card(E_a,b(Fp)) we deduce that:

Card(E_a,b(A_P )) > (Card(E_a,b(Fp))−3)ⁿ +Card(E_a,b(Fp))

3 The discrete logarithm problem: complexity and security

The discrete logarithm problem for G may be stated as: Given g ∈ G and h ∈< g >, find an integer x such that h = g^x and ord(g) = q a prime number.

Baby-Step/Giant-Step Method: The idea behind the Baby-Step/Giant-Step method is a standard divideand-conquer approach found in many areas of computer science. We write

x = x0 +x1dqc

Now, since 0 ≤ x ≤ q, we have that 0 ≤ x₀,x₁ ≤ dqc We first compute the Baby-Steps gi ←− gi,f or0 ≤ i ≤dqc

The pairs (g_i,i) are stored in a table so that one can easily search for items indexed by the first entry in the pair. This can be accomplished by sorting the table on the first entry, or more efficiently by the use of hash tables. To compute and store the Baby-Steps clearly requires O(dqc) time and a similar amount of storage.

We now compute the Giant-Steps h_j ←− h.g^−jdqc for 0 ≤ j ≤dqc , and try to find a match in the table of BabySteps, i.e. we try to find a value g_i such that g_i = h_j. If such a match occurs we have x₀ = i and x₁ = j.

since, if g_i = h_j , we have gⁱ = h.g^−jdqc

i.e gi+jdqc = h

Notice that the time to compute the Giant-Steps is at_√ most O( q).

Hence, the overall time and space complexity of the_√ Baby-Step/Giant-Step method is O( q)[8].

Pollard-Type Methods: We define a partition G = S₀ ∪ S₁ ∪S₂ and the function

 (hy,a,a+b mod(q))        if   f (y,a,b) =  (y2,2a mod(q),2b mod(q)) if    (gy,a+1 mod(q),b)     if 

y ∈ S0 y ∈ S1 y ∈ S2

Note that if y = g^ah^b, Then, taking (z,k,l) = (y,a,b), z = g^kh^l.

Then, it is possible to iterate f until finding two identical results: (y,a,b) = (z,k,l) and

gahb = y = z = gkhl ⇒ gl−k = hl−b

As g^x = h, we have

ga−k = gx(l−b) ⇒ x(l −b) = (a−k) mod(q)

if l −b Is invertible modulo q, We find the solution x = (a⁻k)(l ⁻b)⁻¹ mod(q)

√

The time and space complexity of the method is O(           q).

Let Card(E_a,b(A_P )) = M and Card(E_a,b)(F_p) = N n ≥ 3, and N ≥ 7[8].

Theorem 4._√         The time for solving DLP in E_a,b(A_P ) is Ω(N),

and O(         N) for solving DLP in E_a,b(F_p).

Proof._√ Its clear that for solving DLP in E_a,b(F_p) is

O(_√N). We have the time for solving DLP in E_a,b(A_P ) is

O(         M). And: M ≥ (N −3)ⁿ +N

⇒ M_√ ≥ (N −3)³ +N ≥ N² because n ≥ 3 and N ≥ 7

⇒ _√M ≥ N

⇒        M = Ω(N)

Then the time complexity for solving DLP in_√          E_a,b(A_P ) is

Ω(N) Instead of O(           N) for E_a,b(F_p).

Example:

Let n = 3, p = 5, a = 1 and b = 1.

E_1,1(F₅) = {[0 : 1 : 0],[0 : 1 : 1],[0 : 4 : 1],[2 : 1 : 1],[2 : 4 : 1],[3 : 1 : 1],[3 : 4 : 1],[4 : 2 : 1],[4 : 3 : 1]}

We have Card(E_1,1(F₅)) = 9. Then

Card(E₁,1(A_P )) ≥ (E₁,1(^F5) − 3)³ + Card(E₁,1(^F5)) = 225 The following table gives the difficulty of calculating in A = F₅[e₁,e₂,e₃], and in E₁,₁(A) as a function of the F₅ addition and the multiplication.

Operations	+ in F5	× in F5
+ in F5[e1,e2,e3]	3	0
× in F5[e1,e2,e3]	6	10
+ in E1,1(F5[e1,e2,e3])	582	870
+ in E1,1(F5)	6	4

Note        that       the        computational         difficulty        in

E₁,₁(^F₅[e₁,e₂,e₃]) is much more difficult than in E₁,₁(^F₅).

4              The fundamental algorithms

4.1       Algorithms in A

Algorithm 1 sum_1(p)

Input:(X = (x₀,x₁,…,x_n),Y = (y₀,y₁,…,y_n));

Output:(Z = X +Y); for i = 0 to n do: z_i = x_i +y_i;

end for; return Z = (z₀,z₁,…,z_n); end;

Algorithm 2 prod_1(p)

Input:(X = (x₀,x₁,…,x_n),Y = (y₀,y₁,…,y_n)); Output:(Z = X.Y); z₀ = x₀.y₀; for i = 1 to n do:

zi = x0yi +xiyi +xiy0;

en for; return Z = (z₀,z₁,…,z_n); end;

Algorithm 3 if _invertible_1(p)

Input:(X = (x₀,x₁,…,x_n)) Output:(true,false)

for i = 1 to n do if (x₀ +x_i == 0 mod(p) or x₀ = 0) return false;

end if

end for; return true; end;

Algorithm 4 invertible_1(p)

Input:(X = (x₀,x₁,…,x_n)); Output:(Z = X⁻¹); if (if _invertible_1(X) == f alse);

print(“X is not invertible); return null;

end if;

;

for i = 1 to n do

z_i ; end for; return Z = (z₀,z₁,…,z_n); end;

Algorithm 5 projection_1(p)

Input:(X = (x₀,x₁,…,x_n)); Output: x₀; return x₀; end;

 

4.2       Algorithms in A_P

Algorithm 6 prod_2(p)

Input: (X = ((x₀,x₁,…,x_n),(1,s₁,…,s_n)),

Y = ((y₀,y₁,…,y_n),(1,t₁,…,t_n)));

Output: XY;

• = pod_1((x₀,x₁,…,x_n),(y₀,y₁,…,y_n));
• = pod_1((1,s₁,…,s_n),(1,t₁,…,t_n));

Z = (A,B); return Z; end;

Algorithm 7 sum_2(p)

Input: (X = ((x₀,x₁,…,x_n),(1,s₁,…,s_n)),

Y = ((y₀,y₁,…,y_n),(1,t₁,…,t_n)));

Output: X +Y;

• = sum_1(prod_1((x₀,x₁,…,x_n),(1,t₁,…,t_n)), prod_1((y₀,y₁,…,y_n),(1,s₁,…,s_n)));
• = pud_1((1,s₁,…,s_n),(1,t₁,…,t_n));

Z = (A,B); return Z; end;

Algorithm 8 projection_2(p)

Input:(X = ((x₀,x₁,…,x_n),(1,s₁,…,s_n)));

Output: x₀; return x₀; end;

4.3        Algorithms in E_a,b(A_P )

Algorithm 9 projection_3(p)

Input:(X,Y,Z); Output: (π(X),π(Y),π(Z)); return (projection_2(X),projection_2(Y), projection_2(Z)) ;

end;

In this algorithm the + and . in A_P for simplicity

Algorithm 10 sum_3(p)

Input: (X = (x,y,z),Y = (x⁰,y⁰,z⁰)); Output: X +Y = (p,q,r);

if projection_3(X) = prejection_3(Y) then;

p = y2x0z0 − zxy02 − a(zx0 + xz0)(zx0 − xz0) + (2yy0 −

3bzz⁰)(zx^{0 −}xz⁰); q = yy0(z0y−zy0)−a(xyz02−z2x0y0)+(−2azz0 −3xx0)(x0y−

xy⁰)⁻3bzz⁰(z⁰y ⁻zy⁰);

r = (zy⁰ +z⁰y)(z⁰y −zy⁰)+(3xx⁰ +azz⁰)(zx⁰ −xz⁰);

else

p = (yy^{0 −} bzz⁰)(x⁰y + xy⁰) + (a²zz^{0 −} 2axx⁰)(zy⁰ + z⁰y) ⁻ 3b(xyz⁰² +z²x⁰y⁰)⁻a(yzx⁰² +x²y⁰z⁰) ; q = y2y02 + 3ax2x02 + (−a3 − 9b2)z2z02 − a2(zx0 + xz0)2 − 2a²zxz⁰x⁰ +(9bxx⁰ −3abzz⁰)(zx⁰ +xz⁰); r = (yy⁰ + 3bzz⁰)(zy⁰ + z⁰y) + (3xx⁰ + 2azz⁰)(x⁰y + xy⁰) +

a(xyz⁰² +z²x⁰y⁰); end if; return (p,q,r); fin ;

5        Conclusion

In this work we study the elliptic curves over a special ring, and we construct a new groups with intractable discrete logarithm problem is therefore of great importance, This allows to define more secure cryptographic cryptosystems.

1. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, (48): 203-209, 1987.
2. Virat. Courbe elliptique sur un anneau et applications cryptographiques. Thése Docteur en Sciences, Nice-Sophia Antipolis. (2009).
3. Abdelhakim Chillali. Elliptic Curve Over Special Ideal Ring. Int. J. Open Problems Compt. Math., Vol. 6, No. 2, June 2013.
4. Chilali, S.Abdelalim. The Eliptic Curves Ea;b(Fp[e1; e2; e3]) Gulf Journal of Mathematics Vol 3, Issue 2 (2015) 49-53.
5. Mumford, J. Fogarty, and F. Kirwan.Geometric Invariant Theory , volume 34 of A Series of Modern Surveys in Mathematics . Springer-Verlag, 3e edition, 1994.
6. M. Katz and B.Mazur. Arithmetic Moduli of Elliptic Curves. Number 108 in Annals of Mathematics Studies. Princeton University Press, 1985.
7. Lange and W.Ruppert. Complete systems of addition laws on abelian varieties. Invent.Math. 79, 603-610(1985).
8. Nigel P. Smart. Cryptography Made Simple. Springer International Publishing, 2016.
9. Joseph H. Silverman. The Arithmetic of Elliptic Curves. Springer, 1986.
10. Lawrence C.Washington. Elliptic Curves Number Theory and Cryptography. Chapman & HallCRC 2008.
11. Andreas Enge. Elleptic Curves And Their Applications To Cryptography, An Introduction. Kluwers Academic Publishers, 1999.