# Analysis of the Fault Attack ECDLP over Prime Field

Authors: Mingqiang Wang; Tao Zhan
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

In 2000, Biehl et al. proposed a fault-based attack on elliptic curve cryptography. In this paper, we refined the fault attack method. An elliptic curveE is defined over prime field 𝔽p with base point P∈E(𝔽p). Applying the fault attack on these curves, the discrete logarithm on the curve can be computed in subexponential time of Lp(1/2,1+o(1)). The runtime bound relies on heuristics conjecture about smooth numbers similar to the ones used by Lenstra, 1987.


---

## Body

## 1. Introduction

In 1996, a fault analysis attack was introduced by Boneh et al. [1]. Biehl et al. [2] proposed the first fault-based attack on elliptic curve cryptography [3, 4]. Their basic idea is to change the input points, elliptic curve parameters, or the base field in order to perform the operations in a weaker group where solving the elliptic curve discrete logarithm problem (ECDLP) is feasible. A basic assumption for this attack is that one of the two parameters of the governing elliptic curve equation is not involved for point operations formulas. In this way, the computation could be performed in a cryptographically less secure elliptic curve.In [2], it is claimed that the attacker can get the secret multiplier k with subexponential time, but the authors did not give the proof or even an outline of the proof. I find that this is not a trivial result. Since the distribution of the cardinality of elliptic curves over finite field 𝔽q is not uniform in the interval [q+1-2q,q+1+2q].In practice, in order to get a better function, the cryptosystem may be based on some special family of elliptic curve. Here, we assume that the fault attack is restricted on the following elliptic curve defined over prime field𝔽p:(1.1)y2=x3+Ax2+B,
which is denoted by EA,B. In this paper, we prove that the attacker can get the secret multiplier k with subexponential time when the fault attack is restricted to the elliptic curve family of EA,B. It is noted that we can get a simpler proof when the fault attack is based on the general elliptic curves.In Section2, the fault attack method is described in detail and some improvements of the fault attack are introduced. Firstly, we can control the order of the fault point in EA,B̂ by a suitable choice of the random key d. On the other hand, some points in EA,B can be chosen as fault point to increase the probability of success of the fault attack.Our analysis depends on the number of♯EA,B̂(𝔽p) with B̂∈𝔽p. In Section 3, we research the isomorphism classes of the elliptic curves expressed by form (1.1). By Deuring [5], we find that the density of ♯EA,B̂(𝔽p) with B̂∈𝔽p in [p+1-2p,p+1+2p] is large enough to ensure our method success.The analysis of our method in this paper shows that the performance of the algorithm is largely determined by the density of numbers built up from small primes in the neighborhood ofp+1 and the number of isomorphism classes of the elliptic curves which can be expressed by form (1.1). If a reasonable conjecture concerning the density of smooth integers is assumed, then the following can be proved.Suppose that0≤α≤1 and c is a positive constant; let Lx(α,c) denote(1.2)exp⁡(c(log⁡x)α(log⁡log⁡x)1-α).
There is a function K:ℝ>0→ℝ>0 with K(x)=Lx(1/2,1+o(1)) for x→∞. Then, with a suitable choice of parameters, ECDLP in the family of elliptic curves (1.1) can be determined by the attacker with probability at least 1-e-h within time K(p)M(p), where M(p)=O((logp)11) and h is the number of times Algorithm 2 is applied.The paper is organized as follows. In Section2, we describe the scalar multiplication algorithm and elliptic curve discrete logarithm problem and refine the fault attack method. In Section 3, we discuss the isomorphism class of elliptic curves expressed by form (1.1). In Section 4, the efficiency of the attack algorithm is considered.


## 2. Preliminaries

### 2.1. Scalar Multiplication Algorithm

LetEA,B be an elliptic curve of form (1.1) defined over finite field 𝔽p with p≠2,3 and Pi=:(xi,yi)∈EA,B(𝔽p), i=1,2,3, such that P1+P2=P3. The algorithm below is a description of the elliptic curve scalar multiplication (ECSM) on curves defined in its most common form:(2.1)x3=λ2-A-x1-x2,y3=-y1-(x3-x1)λ
with(2.2)λ={3x12+2Ax12y1ifx1=x2,andy1=y2,y1-y2x1-x2,otherwise.The fault attack is based on the fact that the curve coefficientB is not used in any of the addition formulas given above.


### 2.2. Elliptic Curve Discrete Logarithm Problem

LetE be an elliptic curve and P=(xP,yP)∈E. Given Q=(xQ,yQ)∈〈P〉, the discrete logarithm problem asks for the integer k such that Q=kP.If the order of the base pointP does not contain at least a large prime factor, then it is possible to use an extension for ECC of the Silver-Pohlig-Hellman algorithm [6] to solve the ECDLP as presented in Algorithm 1. Let n be the order of the base point P with a prime factor n=∏i=0j-1piei, where pi<pi+1, i=0,…,j-2.Algorithm 1:Silver-Pohlig-Hellman algorithm for solving the ECDLP.
Input:  P∈E(𝔽p), Q∈〈P〉, n=∏i=0j-1piei, where pi<pi+1, i=0,…,j-2.Output:  kmodn.(1) Fori=0 to j-1 do(1.1)Q′←𝒪, ki←0.(1.2)Pi←(n/pi)P.(1.3) Fort=0 to (ei-1) do(1.3.1) Qt,i←(n/pit+1)(Q+Q′).(1.3.2) Wt,i←logPiQt,i.{ECDLP in a subgroup of order ord(Pi).}(1.3.3) Q′←Q′-Wt,ipitP.(1.3.4) ki←ki+pitWt,i.(2) Use the CRT to solve the system of congruencesk≡kimodpiei.This gives uskmodn(3) Return(k)Algorithm 2:Basic fault attack on ECSM algorithm.
Input:  EA and P=(xP,yP)∈EA(𝔽p),Q=(xQ,yQ)=kP,w is a parameter to be chosen later and q is the order of point P.Output: Scalar k partially with a probability.(1) Randomly choosexP̂,yP̂∈𝔽p.(1.1)B̂←yP̂2-xP̂3-AxP̂2.(2)P̂←(xP̂,yP̂).(2.1) Obtainn=ord(P̂) in elliptic curve EA,B̂(𝔽p).(2.2) Choose an integer1<d<ord(P̂), compute dP̂.(3) Apply decryption oracle to computexkdP̂.(3.1)ykdP̂←xkdP̂3+AxkdP̂2+B̂.(4) If all the prime factors ofn are smaller than w, then(4.1) Utilize Algorithm2 with (dP̂,kdP̂,n) to obtain kmodn.(5) Return(kmodn)Without losing generality, we assume that the order of the base pointP is a prime number which is large enough for practical cryptosystems.


### 2.3. Fault Attack

In this section, we consider the following EC ElGamal cryptosystem. LetEA,B be an elliptic curve of form (1.1) defined over a prime field 𝔽p. Given a point P=(xP,yP)∈EA(𝔽p), we assume that Q=(xQ,yQ)=kP is the public key and 1≤k<ord(P) the secret key of some user, where ord(P) denotes the order of the base point P.Encryption: Input messagem, choose 1<d<ord(P) randomly, and return (dP,xdQ⨁m).Decryption: Input(H,m′), compute kH, and return (m′⨁xkH).The fault attack is that the attacker randomly chooses an elliptic curveEA,B̂ defined over prime field 𝔽p, finds a point P̂=(xP̂,yP̂)∈EA,B̂(𝔽p), and inputs (dP̂,m′) to the decryption oracle, then the attacker can get the x-coordinate of kdP̂. Having xkdP̂, we compute ykdP̂ by(2.3)ykdP̂=xkdP̂3+AxkdP̂2+B̂.In practice, we can computeEA,B̂ and P̂∈EA,B̂(𝔽p) as follows. Fix an element xP̂∈𝔽p, for any yP̂∈𝔽p, and define(2.4)B̂=:yP̂2-xP̂3-AxP̂2.
Let EA,B̂ be an elliptic curve of form (1.1) as follows:(2.5)y2=x3+Ax2+B̂,
clearly P̂=:(xP̂,yP̂)∈EA,B̂(𝔽p).Having the points pairdP̂,kdP̂∈EA,B̂(𝔽p), one can obtain kmodn, where n=ord(dP̂). This would be possible if all the prime factors of ♯EA,B̂(𝔽p) are smaller than order of P. The complete attack procedure is presented as Algorithm 2.By repeating Algorithm2, then applying CRT, we can get k from the congruences kmodn. The following lemma is useful for us to increase the efficiency of Algorithm 2.Lemma 2.1.
LetE be an elliptic curve defined over finite filed 𝔽q. Then,
(2.6)E(Fq)≃Zn1×Zn2
with n1∣n2 and n1∣q-1.For giving an elliptic curveEA,B̂ defined over finite field 𝔽p, we assume that EA,B̂(𝔽q)≃ℤn1×ℤn2. Then there exists a point P̂ such that ord(P̂)=n2. The number of such points is n1ϕ(n2), where ϕ(·) is the Euler function. Let n2=n2wn2′, where n2w is the product of all the prime factors of n2 which are smaller than w. If, in Step (2.2), we choose d satisfying n2′∣d and (d,n2w)=1, then the order of dP̂ is a w smooth integer.Certainly, of course, we can choose a pointP̂ in EA,B(𝔽p). The procedure of choosing such a point is similar as above.


## 2.1. Scalar Multiplication Algorithm

LetEA,B be an elliptic curve of form (1.1) defined over finite field 𝔽p with p≠2,3 and Pi=:(xi,yi)∈EA,B(𝔽p), i=1,2,3, such that P1+P2=P3. The algorithm below is a description of the elliptic curve scalar multiplication (ECSM) on curves defined in its most common form:(2.1)x3=λ2-A-x1-x2,y3=-y1-(x3-x1)λ
with(2.2)λ={3x12+2Ax12y1ifx1=x2,andy1=y2,y1-y2x1-x2,otherwise.The fault attack is based on the fact that the curve coefficientB is not used in any of the addition formulas given above.


## 2.2. Elliptic Curve Discrete Logarithm Problem

LetE be an elliptic curve and P=(xP,yP)∈E. Given Q=(xQ,yQ)∈〈P〉, the discrete logarithm problem asks for the integer k such that Q=kP.If the order of the base pointP does not contain at least a large prime factor, then it is possible to use an extension for ECC of the Silver-Pohlig-Hellman algorithm [6] to solve the ECDLP as presented in Algorithm 1. Let n be the order of the base point P with a prime factor n=∏i=0j-1piei, where pi<pi+1, i=0,…,j-2.Algorithm 1:Silver-Pohlig-Hellman algorithm for solving the ECDLP.
Input:  P∈E(𝔽p), Q∈〈P〉, n=∏i=0j-1piei, where pi<pi+1, i=0,…,j-2.Output:  kmodn.(1) Fori=0 to j-1 do(1.1)Q′←𝒪, ki←0.(1.2)Pi←(n/pi)P.(1.3) Fort=0 to (ei-1) do(1.3.1) Qt,i←(n/pit+1)(Q+Q′).(1.3.2) Wt,i←logPiQt,i.{ECDLP in a subgroup of order ord(Pi).}(1.3.3) Q′←Q′-Wt,ipitP.(1.3.4) ki←ki+pitWt,i.(2) Use the CRT to solve the system of congruencesk≡kimodpiei.This gives uskmodn(3) Return(k)Algorithm 2:Basic fault attack on ECSM algorithm.
Input:  EA and P=(xP,yP)∈EA(𝔽p),Q=(xQ,yQ)=kP,w is a parameter to be chosen later and q is the order of point P.Output: Scalar k partially with a probability.(1) Randomly choosexP̂,yP̂∈𝔽p.(1.1)B̂←yP̂2-xP̂3-AxP̂2.(2)P̂←(xP̂,yP̂).(2.1) Obtainn=ord(P̂) in elliptic curve EA,B̂(𝔽p).(2.2) Choose an integer1<d<ord(P̂), compute dP̂.(3) Apply decryption oracle to computexkdP̂.(3.1)ykdP̂←xkdP̂3+AxkdP̂2+B̂.(4) If all the prime factors ofn are smaller than w, then(4.1) Utilize Algorithm2 with (dP̂,kdP̂,n) to obtain kmodn.(5) Return(kmodn)Without losing generality, we assume that the order of the base pointP is a prime number which is large enough for practical cryptosystems.


## 2.3. Fault Attack

In this section, we consider the following EC ElGamal cryptosystem. LetEA,B be an elliptic curve of form (1.1) defined over a prime field 𝔽p. Given a point P=(xP,yP)∈EA(𝔽p), we assume that Q=(xQ,yQ)=kP is the public key and 1≤k<ord(P) the secret key of some user, where ord(P) denotes the order of the base point P.Encryption: Input messagem, choose 1<d<ord(P) randomly, and return (dP,xdQ⨁m).Decryption: Input(H,m′), compute kH, and return (m′⨁xkH).The fault attack is that the attacker randomly chooses an elliptic curveEA,B̂ defined over prime field 𝔽p, finds a point P̂=(xP̂,yP̂)∈EA,B̂(𝔽p), and inputs (dP̂,m′) to the decryption oracle, then the attacker can get the x-coordinate of kdP̂. Having xkdP̂, we compute ykdP̂ by(2.3)ykdP̂=xkdP̂3+AxkdP̂2+B̂.In practice, we can computeEA,B̂ and P̂∈EA,B̂(𝔽p) as follows. Fix an element xP̂∈𝔽p, for any yP̂∈𝔽p, and define(2.4)B̂=:yP̂2-xP̂3-AxP̂2.
Let EA,B̂ be an elliptic curve of form (1.1) as follows:(2.5)y2=x3+Ax2+B̂,
clearly P̂=:(xP̂,yP̂)∈EA,B̂(𝔽p).Having the points pairdP̂,kdP̂∈EA,B̂(𝔽p), one can obtain kmodn, where n=ord(dP̂). This would be possible if all the prime factors of ♯EA,B̂(𝔽p) are smaller than order of P. The complete attack procedure is presented as Algorithm 2.By repeating Algorithm2, then applying CRT, we can get k from the congruences kmodn. The following lemma is useful for us to increase the efficiency of Algorithm 2.Lemma 2.1.
LetE be an elliptic curve defined over finite filed 𝔽q. Then,
(2.6)E(Fq)≃Zn1×Zn2
with n1∣n2 and n1∣q-1.For giving an elliptic curveEA,B̂ defined over finite field 𝔽p, we assume that EA,B̂(𝔽q)≃ℤn1×ℤn2. Then there exists a point P̂ such that ord(P̂)=n2. The number of such points is n1ϕ(n2), where ϕ(·) is the Euler function. Let n2=n2wn2′, where n2w is the product of all the prime factors of n2 which are smaller than w. If, in Step (2.2), we choose d satisfying n2′∣d and (d,n2w)=1, then the order of dP̂ is a w smooth integer.Certainly, of course, we can choose a pointP̂ in EA,B(𝔽p). The procedure of choosing such a point is similar as above.


## 3. The Isomorphism Classes

In this section, we count the number of isomorphism classes over𝔽p of elliptic curves (1.1) defined over a prime field 𝔽p.It is easy to see that the discriminantΔ and the j invariant of the formula (1.1) are equal to -16((4/27)A4(1-A2)+4A2B+27B2) and -(43A6)/Δ, respectively. Hence, the number of elliptic curves over the prime field 𝔽p with A fixed is the number of B∈𝔽p with(3.1)427A4(1-A2)+4A2B+27B2≠0.
Let T be the number of the solutions of the following equation in 𝔽p:(3.2)27x2+4A2x+427A4(1-A2)=0.
It is easy to see that T≤2. Hence, we conclude that the number of elliptic curves over 𝔽p with B fixed is equal to p-T.EA,B is isomorphic to EA,B̂ if and only if there exists an admissible transform:(3.3)x¯=u2x+r,y¯=u3y+u2sx+t,
where r,s,t∈𝔽p and u∈𝔽p*. Therefore, EA,B≅EA,B̂ if and only if there exist u∈𝔽p*,r∈𝔽p such that the following conditions hold:(i)
u6=1 and A=Au4+3u4r;(ii)
3u2r2+2u2rA=0 and Ar2+r3+B̂=B.GivenA,B,B̂, let T′ denote the number of the solutions (u,r) of (i) and (ii); it is easy to see that T′≤6. For any p≠2,3, the number of the automorphism of elliptic curve EA,B is at most 3. Hence, we have(3.4)∑EA,B̂1♯Aut(EA,B̂)′≥p-T6,
where ∑EA,B̂′is over a set of representatives of the isomorphism classes. We express this by writing(3.5)♯′{EA,B̂:EA,B̂ellipticcurveofform(1.1)withB̂∈Fp}≅Fp,
and in similar expression below, ♯′ denotes the weighted cardinality, the isomorphism class of EA,B̂ being counted with the weight 1/(♯Aut(EA,B̂)).For any elliptic curveE over 𝔽p, we have(3.6)♯E(Fp)=p+1-t,witht∈Z,|t|≤2p,
which is obtained by a theorem of Hasse. Let, conversely, p be a prime >3 and let t be an integer satisfying |t|≤2p. Then, the weighted number of elliptic curves E over 𝔽p with ♯E(𝔽p)=p+1-t, up to isomorphism is given by a formula that is basically due to Deuring [5]; see also [7–9]:(3.7)♯′{E:EellipticcurveoverFp,♯E(Fp)=p+1-t}≅Fp=H(t2-4p),
where H(t2-4p) denotes the Kronecker class number of t2-4p.For the Kronecker class number, the following result is useful.Lemma 3.1 (see [10]).
There exist effectively computable positive constantsc1,c2 such that for each z∈ℤ>1 there is Δ*=Δ*(z)<-4 such that
(3.8)c1-Δlog⁡z≤H(Δ)≤c2-Δlog⁡|Δ|loglog|Δ|
for all Δ∈ℤ with -z≤Δ<0,Δ≡0,or1mod4, except that the left inequality may be invalid if Δ0=Δ*, where Δ0 is the fundamental discriminant associated with Δ.Let(3.9)♯′{EA,B̂:B̂∈Fp,♯EA,B̂(Fp)=p+1-t}≅Fp=:Ht.In order to apply Algorithm2, we divide 𝔽p into two parts SQRp and SNQRp as follows:(3.10)SQRp={B̂:B̂∈Fp,andxP̂3+AxP̂2+B̂isaquadraticresidueinFp},SQNRp={B̂:B̂∈Fp,andxP̂3+AxP̂2+B̂isaquadraticnonresidueinFp}.
Since Ht≤H(t2-4p), Lemma 2.1 cannot be applied directly in the following estimation. In order to apply Lemma 2.1, SQRp should be partitioned into two parts SQR1p and SQR2p as follows:(3.11)SQR1p={B̂:B̂∈SQRp,♯EA,B̂(Fp)=p+1-t,withHt≥plog⁡p},SQR2p={B̂:B̂∈SQRp,♯EA,B̂(Fp)=p+1-t,withHt<plog⁡p}.Let(3.12)TQR1p={s:s∈Z,andthereexistsB̂∈SQR1psuchthats=♯EA,B̂(Fp)}.Theorem 3.2.
There exist an effectively computable positive constantc3 such that, for each prime number p>3, the following assertion is valid. If S is a set of integers s∈TQR1p with
(3.13)|s-(p+1)|≤p,
then
(3.14)♯{EA,B̂:B̂∈SQR1p,♯EA,B̂(Fp)∈S}≅Fp≥c3(♯S-2)plog⁡p.Proof.
The proof of Theorem3.3 is similar to the proof of (1.9) in [10]; for self-containdeness, we give it here. The left-hand side of the inequality equals
(3.15)∑t∈Z,p+1-t∈SHt.
Applying Lemma 3.1 with z=4p, we note that |t2-4p|≥3p if p+1-t∈S. Since S⊆TQR1p, it suffices to prove that there are at most two integers t, |t|≤p, for which the fundamental discriminant associated with t2-4p equals Δ*. Let L=Δ*, and let t be such an integer. Then, the zeros α,α¯ of
(3.16)X2-tX+p
belong to the ring of integers 𝒪L of L. Also, αα¯=p, and by the unique prime ideal factorization in 𝒪L and the fact that A*={1,-1} (because Δ*<-4) this determines α up to conjugation and sign. Hence, t=α+α¯ is determined up to sign, as required. This completes the proof.Theorem 3.3.
There is a positive effectively computable constantc4 such that, for each prime number p>3, the following assertion is valid. Let S be a set of integers s∈TQR1p with
(3.17)|s-(p+1)|≤p,
and let yP̂ be defined as above. Then, the number N of pair (B̂,xP̂)∈𝔽p2 for which
(3.18)4A2+27B̂≠0,♯EA,B̂(Fp)∈S,
where xP̂3+AxP̂2+B̂=yP̂2, is at least c4(♯S-2)(p3/logp).Proof.
The number to be estimated equals the number of pairs(B̂,yP̂)∈𝔽p2 for which EA,B̂ is an elliptic curve over 𝔽p with (xP̂,yP̂)∈EA,B̂(𝔽p) and ♯EA,B̂(𝔽p)∈S. Each elliptic curve EA¯ over 𝔽p is isomorphic to EA,B̂ for exactly T′/♯AutE, value of A¯∈𝔽p. Each EA,B̂ exactly gives rise to two points (xP̂,yP̂). Thus, the number to be estimated equals
(3.19)∑EA,B̂2T′♯Aut(EA,B̂)′,
where the sum ranges over the elliptic curves EA,B̂ over 𝔽p, up to isomorphism, for which ♯EA,B̂(𝔽p)∈S. Applying Theorem 3.2, we obtain the result.Theorem 3.4.
There exists a positive effectively computable constantc5 such that, for each prime number p>3, the following assertion is valid. Let
(3.20)Sw={s∈TQR1p:|s-(p+1)|<p,andeachprimedividingsis≤w},
and let yP̂ be defined as above. Then, the number N of triple (B̂,xP̂)∈𝔽p2 for which
(3.21)4A2+27B̂≠0,♯EA,B̂(Fp)∈Sw,
where xP̂3+AxP̂2+B̂=yP̂2, is at least c5(♯Sw-2p3/logp).Proof.
This can be deduced from Theorem3.3 immediately.Theorem 3.5.
There exists a positive effectively computable constantc6 such that the cardinality of TQR1p is at least c6p/(logp(loglogp)).Proof.
The map(3.22)ϕ:Fp⟼FpB̂⟼xP̂3+AxP̂2+B̂
is a bijective map. By the definition of SQRp and SQNRp, we have ♯SQRp=♯SQNRp=(p-1)/2. By (3.6), the trace t of any elliptic curve E over 𝔽p satisfies |t|≤2p; hence, the cardinality of SQR2p is at most
(3.23)2pplog⁡p≤2plog⁡p.
Therefore, the cardinality of SQR1p is
(3.24)SQRp-SQR2p≥p-2plog⁡p.
From the discussion about the isomorphism classes of elliptic curves and the fact that Ht≤H(t2-4p), we have
(3.25)♯TQR1p≥♯SQR1p-TH(Δ).
Applying Lemma 2.1, we get the proof of the result.
LetT1=TQR1p⋂(p+1-p,p+1+p). Our attack method depends on the following reasonable heuristic assumption.Heuristic Assumption:The setTQR1pis uniformly distributed in the interval(p+1-2p,p+1+2p).
By the assumption, one can deduce that♯TQR1p≈2♯T1.Theorem 3.6.
There exists an effectively computable constantc7>1 with the following property. Let w∈ℤ>1 and
(3.26)♯Sw={s∈TQR1p:|s-(p+1)|<p,andeachprimedividingsis≤w}.
Let f(w)=♯Sw/♯T1 denotes the probability that a random integer in the interval (p+1-p,p+1+p) has all its prime factors <w. The probability of success of Algorithm 2 on input P,Q∈EA,B,w is at least 1-c7-hf(w)/(logp)2(loglogp), where h is the number of times that Algorithm 2 is applied.Proof.
By Theorem3.5, the failure probability of repeating Algorithm 2  h times equals (1-N/p2)h, where
(3.27)Np2≥c5♯Sw-2♯T1♯T1plog⁡p≥c5f(w)♯T1plog⁡p≥c5c6f(w)(log⁡p)2(log⁡log⁡p).
It follows that
(3.28)(1-Np2)h≤e-c5c6h(f(w)/((log⁡p)2(log⁡log⁡p))).
Consequently, the desired result follows.


## 4. Efficiency

In the case of factoring, the best rigorously analyzed result is Corollary 1.2 of [11], which states that all prime factors of n that are less than w can be found in time Lw(2/3,c)log2n. Schoof [12] presents a deterministic algorithm to compute the number of 𝔽p-points of an elliptic curve that is defined over a finite field 𝔽p and takes O(log9p) elementary operations.Theorem3.6 shows that, in order to have a reasonable chance of success, one should choose the number h of the same order of magnitude as O((logp)2(loglogp)/f(w)). In Algorithm 2, for any yP̂, we can obtain B̂∈SQRp. From the discussion in Theorem 3.6, the probability of B̂∈SQR2p is approximately 1/logp. Hence, the cases of B̂∈SQR2p are neglected, which does not affect the analysis result. Therefore, the time spent on Algorithm 2 is O(hLw(2/3,c)M(p)), where M(p)=O(log11p). The time required by Algorithm 2 is w. Hence, to minimize the estimated running time, the number w should be chosen such that Lw(2/3,c)/f(w)+w is minimal.A theorem of Canfield et al. [13] implies the following result. Let α be a positive real number. Then, the probability that a random positive integer s<x has all its prime factors less than Lx(1/2,1)α is Lx(1/2,1)-1/2α+o(1) for x→∞. The conjecture we need is that the same result is valid if s is a random integer in the interval (x+1-x,x+1+x). Putting x=p, we see that the conjecture implies that(4.1)f(Lp(12,1)α)=Lp(12,1)-1/2α+o(1)forp⟶∞,
for any fixed positive α, with f(w)=♯Sw/♯T1.The following identities are useful for our estimation:(4.2)Lp(α,cα)Lp(β,cβ)=Lp(max⁡{α,β},cmax⁡{α,β}),LLp(α,cα)(β,cβ)=Lp(αβ,cβcαβ),
where lower-order terms in the exponent are neglected.Withw=Lp(1/2,1)α, the conjecture would imply that(4.3)Lw(2/3,c)f(w)+w=Lp(12,1)1/2α+o(1)+Lp(12,1)α/2,forp⟶∞,
which suggests that for the optimal choice of w we have(4.4)w=Lp(12,1),Lw(2/3,c)f(w)=Lp(12,1)1+o(1),forp⟶∞.These arguments lead to the following conjectural running time estimation for solving the discrete logarithm problem on elliptic curve of form (1.1) over prime field.Theorem 4.1.
There is a functionK:ℝ>0→ℝ>0 with
(4.5)K(x)=Lx(12,1+o(1))forx⟶∞
such that the following assertion is true. Let p be a prime number that is not 2 or 3. Then, we can find the discrete logarithm of Montgomery elliptic curve over prime filed 𝔽p within time O(K(p)M(p)).



---

*Source: 580749-2011-11-03.xml*