Edwards Curves and Gaussian Hypergeometric Series Mohammad Sadek and Nermine El-Sissi 5 1 0 2 n a J Abstract 4 1 LetE beanellipticcurvedescribedbyeitheranEdwardsmodeloratwistedEdwards ] model over Fp, namely, E is defined by one of the following equations x2+y2 = a2(1+ T x2y2), a5−a6≡0 mod p,or, ax2+y2 =1+dx2y2, ad(a−d)6≡0 modp, respectively. We N express the number of rational points of E over F using the Gaussian hypergeometric . p h φ φ at series 2F1 x where ǫ and φ are the trivial and quadratic characters over Fp m  ǫ  (cid:12) [ respectively. This(cid:12)(cid:12)enablesus toevaluate|E(Fp)| forsomeelliptic curvesE,andprovethe existence of isogenies between E and Legendre elliptic curves over F . 1 p v 6 2 1 Introduction 5 3 0 In [4] Greene initiated the study of Gaussian hypergeometric series over finite fields. . 1 These series are analogous to the classical hypergeometric series. Several authors man- 0 5 aged to find congruence relations satisfied by special values of these series, see [6]. Many 1 : special values of these series were determined. v i One of the striking aspects of hypergeometric series is that some of their special X values are linked to the number of rational points on some families of algebraic curves r a over finite fields. Two families of elliptic curves were discussed in [5]. The number of rational points of an elliptic curve E described by a Legendre model, namely, y2 = x(x−1)(x−λ), λ(λ−1) 6≡ 0 modp, over the finite field F satisfies the following identity p φ φ |E(F )| = 1+p+pφ(−1)· F λ p 2 1   ǫ (cid:12) (cid:12)   (cid:12) Mathematics Subject Classification: 11T24,14H52 1 where ǫ and φ are the trivial and quadratic characters over F respectively. The p φ φ latter identity was used to evaluate the hypergeometric series F λ when 2 1   ǫ (cid:12) λ ∈ {−1,1/2,2}. If E is defined by a Clausen model, y2 = (x−1)(x2+λ),λ((cid:12)λ+1) 6≡ 0 (cid:12) mod p, then φ φ φ λ (1+p−|E(F )|)2 = p+p2φ(λ+1)· F . p 3 2  λ+1 ǫ ǫ (cid:12) (cid:12)   (cid:12) φ φ φ λ Againthiswasexploitedinordertoevaluatethehypergeometricseries F 3 2  λ+1 ǫ ǫ (cid:12) at some specific values of λ.  (cid:12)(cid:12)  More Gaussian hypergeometric series appear in formulas describing the number of rational points on higher genus curves over finite fields. Some of these formulas can be found in [1] where the following family of algebraic curves are discussed yl = x(x−1)(x−λ), λ(λ−1) 6≡ 0 mod p, l ≥ 2. In this note we are interested in elliptic curves described by Edwards models or twisted Edwards models, namely x2 +y2 = a2(1+x2y2), a5 −a 6≡ 0 mod p; ax2 +y2 = 1+dx2y2, ad(a−d) 6≡ 0 mod p respectively. Edwards models of elliptic curves were proposed in [3] and have been used since then inmany cryptographic applications. Themainadvantageenjoyed bythese curves is that the group law is simpler to state than on other models representing elliptic curves. In addition, any elliptic curve defined over an algebraically closed field k can be expressed in the form x2+y2 = a2(1+x2y2). Twisted Edwards models appeared for the first time in [2] to express more elliptic curves over finite fields with the addition law being easily formulated. We show that the number of rational points on an Edwards curve E over a finite φ φ field F can be written in terms of the Gaussian hypergeometric series F x . p 2 1   ǫ (cid:12) Consequently, we evaluate |E(F )| for some E. Then we prove that every Edw(cid:12)ards p (cid:12) 2 F curve is isogenous to a Legendre curve over . Finally, it turns out that the number p of rational points on a twisted Edwards curve E is described using special values of φ φ the hypergeometric series F x . This sets the stage for evaluating |E(F )| for 2 1 p   ǫ (cid:12) some twisted Edwards curvesE. (cid:12)  (cid:12) 2 Gaussian hypergeometric series Throughout the note p will be an odd prime unless otherwise stated. We extend multi- plicative characters χ defined over F to F by setting χ(0) = 0. We write χ to denote ×p p 1/χ. The trivial and quadratic characters will be denoted by ǫ and φ respectively. Let J(A,B) denote the Jacobi sum J(A,B) = A(x)B(1−x) xX∈Fp where A and B are characters over F . Let A ,A ,...,A and B ,...,B be characters p 0 1 n 1 n F defined over . The Gaussian hypergeometric series is p A A ... A p A χ A χ A χ 0 1 n 0 1 n F x := ... χ(x) n+1 n   p−1 χ B χ B χ B1 ... Bn(cid:12) Xχ (cid:18) (cid:19)(cid:18) 1 (cid:19) (cid:18) n (cid:19) (cid:12)   (cid:12) F where the sum is over all characters over and p A B(−1) B(−1) := J(A,B) = A(x)B(1−x). B p p (cid:18) (cid:19) xX∈Fp A The following properties of the symbol can be found in [4]. B (cid:18) (cid:19) Lemma 2.1. For any characters A and B over F , one has: p p A a) A(1 + x) = δ(x) + χ(x) where δ(x) = 1 if x = 0 and δ(x) = 1 if p−1 χ χ (cid:18) (cid:19) X x 6= 0; p Aχ b) A(1−x) = δ(x)+ χ(x) where δ(x) = 1 if x = 0 and δ(x) = 0 if p−1 χ χ (cid:18) (cid:19) X x 6= 0; 3 A A c) = ; B AB (cid:18) (cid:19) (cid:18) (cid:19) A BA d) = B(−1); B B (cid:18) (cid:19) (cid:18) (cid:19) A A 1 p−1 e) = = − + δ(A) where δ(A) = 1 if A = ǫ and δ(A) = 0 otherwise; ǫ A p p (cid:18) (cid:19) (cid:18) (cid:19) B2χ2 φBχ Bχ φ −1 f) = Bχ(4). χ χ B2χ φB (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) 3 Rational points on Edwards curves Let E be an elliptic curve over a field k with chark 6= 2 defined by an Edwards model x2 +y2 = a2(1+x2y2), where a5 −a 6= 0. Such an elliptic curve will be called an Edwards curve. If (x ,y ) and (x ,y ) are two 1 1 2 2 points on E, then these two points add up to 1 x y +x y 1 y y −x x 1 2 2 1 1 2 1 2 x = · , y = · . 3 3 a 1+x x y y a 1−x x y y 1 2 1 2 1 2 1 2 There are two points at infinity, namely if we homogenize the defining equation, we get x2z2 +y2z2 = a2(z4 +x2y2) and the points at infinity are (x : y : z) ∈ {(1 : 0 : 0),(0 : 1 : 0)}. We will need the following lemma to count rational points on an Edwards curve. Lemma 3.1. Let A be a character on F and a ∈ F . The following identities hold: p p× A2 φA A(4) if A 6= ǫ a) = A (cid:18)A(cid:19)  (cid:0)p−p2(cid:1) if A = ǫ A2 pA(a2) φA if A 6= ǫ b) A(a2−x2) = pA(4a2) = A A  xX∈Fp (cid:18) (cid:19)  p−2 (cid:0) (cid:1) if A = ǫ Proof: a) In Lemma 2.1 f), put B = ǫ and χ = A. This yields A2 φA A φ −1 = A(4). A A A φ (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19)(cid:18) (cid:19) 4 φA According to Lemma 2.1 e), the product above is A(4) if A 6= ǫ, and it is (2 − A (cid:18) (cid:19) φA p) A(4) if A = ǫ. A (cid:18) (cid:19) To prove b), we notice that 1 x 1 x A(a2 −x2) = A 4a2 A − A + 2 2a 2 2a xX∈Fp (cid:0) (cid:1)xX∈Fp (cid:18) (cid:19) (cid:18) (cid:19) 1 x Setting u = − , the above sum becomes 2 2a A(a2 −x2) = A 4a2 A(u)A(1−u) xX∈Fp (cid:0) (cid:1)uX∈Fp A = A(4a2)J(A,A) = pA(−4a2) . A (cid:18) (cid:19) 2 A A Using Lemma 2.1 d), one has = A(−1). Part b) now follows from a). ✷ A A (cid:18) (cid:19) (cid:18) (cid:19) The following theorem relates the number of rational points on an Edwards curves F over to a Gaussian hypergeometric series. p Theorem 3.2. Let E/F be described by x2+y2 = a2(1+x2y2) where a5 6≡ a mod p, p p is an odd prime. Then φ φ |E(F )| = 1+p+p· F 1−a4 . p 2 1   ǫ (cid:12) (cid:12)   (cid:12) Proof: The defining equation of E can be written as: a2 −x2 y2 = . 1−a2x2 5 Bearing in mind that there are two points at infinity, one has a2 −x2 |E(F )| = 2+p+ φ p 1−a2x2 x∈FpX\{±a−1} (cid:18) (cid:19) a2 −a 2 − = 2+p+ φ 1+ a 2 −x2 x∈FpX\{±a−1} (cid:18) − (cid:19) a2 −a 2 p φ a2 −a 2 − − = 2+p+ δ + χ a 2 −x2 p−1 χ a 2 −x2 x∈FpX\{±a−1}h (cid:18) − (cid:19) Xχ (cid:18) (cid:19) (cid:18) − (cid:19)i p φ a2 −a 2 − = 2+p+ χ p−1 χ a 2 −x2 x∈FpX\{±a−1}Xχ (cid:18) (cid:19) (cid:18) − (cid:19) p φ = 2+p+ χ a2 −a 2 χ(a 2 −x2). − − p−1 χ Xχ (cid:18) (cid:19) (cid:0) (cid:1)xX∈Fp The third equality follows from Lemma 2.1 a). Now we use Lemma 3.1 b) to obtain the following identity: p φ φχ φ |E(F )| = 2+p+ p χ a 2 χ a2 −a 2 + (p−2) . p − − p−1 χ χ ǫ h Xχ6=ǫ(cid:18) (cid:19)(cid:18) (cid:19) (cid:0) (cid:1) (cid:0) (cid:1) (cid:18) (cid:19) i φ φχ φχ Lemma 2.1 d) gives = χ(−1) = χ(−1), thus χ χ χ (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) p2 φχ φχ 2−p |E(F )| = 2+p+ χ 1−a4 + p p−1 χ χ p2 hXχ6=ǫ(cid:18) (cid:19)(cid:18) (cid:19) (cid:0) (cid:1) i p2 φχ φχ φ 2 2−p = 2+p+ χ 1−a4 − + p−1 χ χ ǫ p2 hXχ (cid:18) (cid:19)(cid:18) (cid:19) (cid:0) (cid:1) (cid:18) (cid:19) i φ φ = 1+p+p· F 1−a4 . 2 1   ǫ (cid:12) (cid:12)   ✷ (cid:12) The Legendre family of elliptic curves is the one defined by E : y2 = x(x−1)(x−λ), λ(λ−1) 6≡ 0 mod p. λ φ φ Theorem 1 in [5] states that |E (F )| = 1 + p + pφ(−1) · F λ . Since two λ p 2 1   ǫ (cid:12) elliptic curves over Fp are isogenous if and only if they have the same nu(cid:12)(cid:12)mber of rational 6 points, comparing |E (F )| to the number of rational points of an Edwards curve E over λ p F defined by x2+y2 = a2(1+x2y2), see Theorem 3.2, yields that E is isogenous to the p Legendre elliptic curve E if p ≡ 1 mod 4. In fact, every Edwards curve is isogenous 1 a4 F− to a Legendre curve over . p Corollary 3.3. Let E be defined by x2 + y2 = a2(1 + x2y2) over F , where p is an p odd prime and a5 6≡ a mod p. Then E is isogenous to the Legendre elliptic curve E : y2 = x(x−1)(x−a4). a4 φ φ Proof: According to Theorem 1 in [5], |E (F )| = 1+ p +pφ(−1) · F a4 . a4 p 2 1   ǫ (cid:12) The following identity is Theorem 4.4 (i) of [4]  (cid:12)  (cid:12) φ φ φ φ F x = φ(−1)· F 1−x . 2 1 2 1     ǫ ǫ (cid:12) (cid:12) (cid:12) (cid:12)     Now set x = a4 and use Theorem(cid:12) 3.2. Consequently, E a(cid:12)nd E have the same number a4 F F ✷ of rational points over . It follows that they are isogenous over . p p We recall the following Proposition which can be found as Theorem 2 in [5]. Proposition 3.4. Let p be an odd prime. If λ ∈ {−1,1/2,2}, then φ φ 0 if p ≡ 3 mod 4, F λ = 2 1 ǫ   2x·(−1)(x+y+1)/2 if p ≡ 1 mod 4,x2 +y2 = p,x is odd. (cid:12)  p (cid:12)   Corollary 3.5. L(cid:12)et E/F be defined by x2 +y2 = a2(1+x2y2) where a5 6≡ a mod p. If p a4 ∈ {−1,1/2,2}, then 1+p if p ≡ 3 mod 4, |E(F )| = p  1+p+2x·(−1)(x+y+1)/2 if p ≡ 1 mod 4,x2 +y2 = p,x is odd.  Proof: This follows immediately from Corollary 3.3. ✷  4 Rational points on twisted Edwards curves Twisted Edwards curves were introduced in [2] as generalizations of Edwards curves. These curves include more elliptic curves over finite fields than Edwards curves do. A twisted Edwardscurveisanellipticcurve definedbythefollowingtwisted Edwards model ax2 +y2 = 1+dx2y2 7 where ad(a− d) 6= 0. For any field k with char(k) 6= 2, any elliptic curve over k with three k-rational points of order 2 is 2-isogenous over k to a twisted Edwards curve, see F Theorem 5.1 of [2], hence they have the same number of rational points over . p Lemma 4.1. The following equality holds for any character A over F p φχ χ χ(x2)φ(1−x2) = pφ(−1) + . χ φχ xX∈Fp (cid:20)(cid:18) (cid:19) (cid:18) (cid:19)(cid:21) Proof: We recall that the number of solutions of the equation z2 = a mod p is given by N = φ(a)+1. In fact N = 2 if a ∈ F 2,a 6= 0, N = 1, and N = 0 otherwise. We a a p 0 a consider the following sum: χ(x)φ(x)φ(1−x) = χ(x)φ(1−x)(N −1) x x x X X = χ(x)φ(1−x)N − χ(x)φ(1−x) x x x X X = 2 χ(x)φ(1−x)− χ(x)φ(1−x) x F2 x X∈ p X = χ(x2)φ(1−x2)− χ(x)φ(1−x). x x X X Therefore, χ(x2)φ(1−x2) = J(φχ,φ)+J(χ,φ) x X φχ χ = pφ(−1) + . φ φ (cid:20)(cid:18) (cid:19) (cid:18) (cid:19)(cid:21) φχ φχ χ χ ✷ Using Lemma 2.1 c), one has = , similarly = . φ χ φ φχ (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) Theorem 4.2. Let E/F be described by ax2+y2 = 1+dx2y2 where ad(a−d) 6≡ 0 mod p p, p is an odd prime. Then φ φ φ ǫ |E(F )| = 2+p+φ(a)+pφ(−a) F a 1d + F a 1d . p 2 1 − 2 1 −      ǫ φ (cid:12) (cid:12) (cid:12) (cid:12)      In particular, (cid:12) (cid:12) φ φ |E(F )| = 2+p−φ(d)+pφ(−a)· F a 1d . p 2 1 −   ǫ (cid:12) (cid:12)   (cid:12) 8 Proof: We observe that we can write the above twisted Edwards model as 1−y2 x2 = . a−dy2 We set b = a 1d. The number of rational points of E over F is given by − p 1−y2 |E(F )| = 2+p+ φ = 2+p+ φ 1−y2 φ a−dy2 p a−dy2 y∈Fp\X{√ad−1} (cid:18) (cid:19) yX∈Fp (cid:0) (cid:1) (cid:0) (cid:1) = 2+p+φ(a) φ(1−y2)φ(1−by2) yX∈Fp p φχ = 2+p+φ(a) φ(1−y2) δ(by2)+ χ(by2) . p−1 χ " # yX∈Fp Xχ (cid:18) (cid:19) The last equality follows from Lemma 2.1 b). According to Lemma 4.1, one obtains pφ(a) φχ |E(F )| = 2+p+φ(a)+ χ(b) χ(y2)φ(1−y2) p p−1 χ Xχ (cid:18) (cid:19) yX∈Fp p2φ(−a) φχ φχ χ = 2+p+φ(a)+ + χ(b) p−1 χ χ φχ χ (cid:18) (cid:19)(cid:20)(cid:18) (cid:19) (cid:18) (cid:19)(cid:21) X φ φ φ ǫ = 2+p+φ(a)+pφ(−a) F a 1d + F a 1d . 2 1 − 2 1 −      ǫ φ (cid:12) (cid:12) (cid:12) (cid:12)      (cid:12) (cid:12) However, Corollary 3.16 in [4] indicates that φ ǫ φ 1 p−1 F a 1d = φ(−a 1d)ǫ(1−a 1d)− φ(−1)ǫ(a 1d)+ φ(−1)δ(1−a 1d)δ(ǫ) 2 1 − − − − −   φ p p φ (cid:18) (cid:19) (cid:12) (cid:12)  (cid:12)  1 1 = − φ(−a 1d)− φ(−1). − p p ✷ This proves the theorem. Corollary 4.3. Let p be an odd prime. Let E/F be defined by ax2 + y2 = 1 + dx2y2 p where ad(a−d) 6≡ 0 mod p. If λ := a 1d ∈ {−1,1/2,2}, then − 2+p−φ(d) if p ≡ 3 mod 4, |E(F )| = p  2+p−φ(d)+2x·φ(a)·(−1)(x+y+1)/2 if p ≡ 1 mod 4,x2 +y2 = p,x is odd.   9 Proof: This follows from Theorem 4.2 and Proposition 3.4. ✷ We remark that any Legendre curve is isogenous to a twisted Edwards curve over F . Indeed, any elliptic curve E with three F -rational points of order 2 defined by p p y2 = x(x−a)(x−b) is isogenous to the twisted Edwards curve 4ax2+y2 = 1+4bx2y2, see Theorem 5.1 in[2]. Thus theformula forthe number ofrational pointsonaLegendre F elliptic curve over , Theorem 1 of [5], follows as a special case from Theorem 4.2. p References [1] R. Barmanand G. Kalita. Hypergeometric functions and a family of algebraic curves. Ramanujan J., 28:175–185,2012. [2] D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters. Twisted Edwards curves. In AFRICACRYPT, volume 5023 of LNCS, pages 389–405.Springer, 2008. [3] H. M. Edwards. A normalform for elliptic curves. Bulletin of the American Mathematical Society, 44(3):393–422,2007. [4] J. Greene. Hypergeometric series over finite fields. Trans. Amer. Math. Soc., 301(1):77–101,1987. [5] K.Ono. Values ofGaussianhypergeometricseries. Trans. Amer. Math. Soc., 350:1205–1223,1998. [6] R.OsburnandC.Schneider. Gaussianhypergeometricseriesandsupercongruences. Math. Comp., 78:275–292,2009. Department of Mathematics and Actuarial Science American University in Cairo [email protected] [email protected] 10