当前位置：文档库 › Pairing-friendly elliptic curves of prime order

Pairing-friendly elliptic curves of prime order

Pairing-Friendly Elliptic Curves of Prime Order

Paulo S.L.M.Barreto1and Michael Naehrig2

1Escola Polit′e cnica,Universidade de S?a o Paulo.

Av.Prof.Luciano Gualberto,tr.3,n.158.

BR05508-900,S?a o Paulo(SP),Brazil.

pbarreto@https://www.wendangku.net/doc/1517365556.html,p.br

2Lehrstuhl f¨u r Theoretische Informationstechnik,

Rheinisch-Westf¨a lische Technische Hochschule Aachen.

Sommerfeldstr.24.

D-52074Aachen,Germany.

mnaehrig@ti.rwth-aachen.de

Abstract.Previously known techniques to construct pairing-friendly

curves of prime or near-prime order are restricted to embedding de-

gree k 6.More general methods produce curves over F p where the

bit length of p is often twice as large as that of the order r of the

subgroup with embedding degree k;the best published results achieve

ρ≡log(p)/log(r)～5/4.In this paper we make the?rst step towards

surpassing these limitations by describing a method to construct elliptic

curves of prime order and embedding degree k=12.The new curves lead

to very e?cient implementation:non-pairing cryptosystem operations

only need F p and F p2arithmetic,and pairing values can be compressed

to one sixth of their length in a way compatible with point reduction

techniques.We also discuss the role of large CM discriminants D to min-

imizeρ;in particular,for embedding degree k=2q where q is prime we

show that the ability to handle log(D)/log(r)～(q?3)/(q?1)enables

building curves withρ～q/(q?1).

Keywords:elliptic curves,pairing-based cryptosystems.

1Introduction

A non-supersingular elliptic curve over F p is called pairing-friendly if it contains a subgroup of order r whose embedding degree k is not too large,which means that computations in the?eld F p k are feasible.The optimal case occurs when the entire curve has prime order and the desired embedding degree.

Pairing-friendly curves of prime or near-prime order are absolutely essential in certain pairing-based schemes like short signatures with longer useful life. For instance,the length of BLS signatures[5]is the size of the base?eld p; at the128-bit security level the scheme should be de?ned on a group of256-bit order r and be mapped to a?nite?eld of roughly3072-bit size p k.In the optimal case,the embedding degree should be k=12.Of course,other systems

would bene?t as well,since the space requirements for all quantities involved in cryptographic protocols except pairing values would be kept to a minimum (pairing compression techniques[16,10]would help reducing the bandwidth for pairing values as well).

The pioneering work of Miyaji,Nakabayashi,and Takano[13]describes how to construct elliptic curves of prime order and embedding degree k∈{3,4,6}. Such curves are now dubbed MNT curves,and satisfy p～r by the Hasse bound. Extensions of the original MNT construction to curves of near-prime order were investigated by Scott and Barreto[17],and more recently by Galbraith,McKee, and Valen?c a[9]3.Unfortunately,those methods are restricted to k 6and hence only allow for a tradeo?:one has to choose between increasing the base?eld to a512-bit prime p(thus doubling the signature size,which ceases to be“short”) or contenting oneself with the lower security level of a1536-bit?nite?eld F p6.

Letρ≡log(p)/log(r)be the ratio between the bit lengths of the?nite ?eld and the order of the subgroup with embedding degree k.Several methods have been proposed to construct curves with arbitrary k,including a“folklore”algorithm[4,chapter9]credited to Cocks and Pinch[7]and related methods due to Barreto,Lynn,and Scott[1]and to Dupont,Enge,and Morain[8].In general these algorithms only achieveρ～2.

Algebraic methods may produce curves withρcloser to unity for certain values of k.Such techniques include the families of curves described by Barreto, Lynn,and Scott[3],and by Brezing and Weng[7].The latter presents the best known results,achievingρ～5/4for families of curves with k=8or k=24, andρ～(k+2)/(k?1)for prime k(henceρ 5/4for prime k 13).Such ratios are already useful under many circumstances.Still,for most embedding degrees the value ofρis larger than this;for instance,the best published value for k=12isρ～3/2.Besides,the use of prime k precludes many optimizations that are only possible for even k[2],making the computation of pairings much less e?cient.

In spite of all these e?orts,constructing pairing-friendly curves with prime order has remained an elusive open problem since it was posed by Boneh et al.[5,section3.5](see also[6,section4.5]).

This paper is organised as follows.

Our main contribution,described in section2,is a surprisingly simple algo-rithm to construct curves of prime order and embedding degree k=12.The resulting security enhancement is even better than the lower bound of k=10 required by Boneh et https://www.wendangku.net/doc/1517365556.html,ing the proposed method,even a160-bit signature maps to1920-bit?eld,where the best algorithms to compute discrete logarithms are worse than Pollard-rho in the elliptic group itself.

We next discuss how to compress the representations of points and pairing values to one sixth of their expected length for the proposed curves in section3. It turns out that non-pairing operations only need arithmetic over F p and F p2,

and it is possible to compute pairings compressed to one sixth of their length without resorting to full arithmetic on?elds larger than F p2.

Finally,we show in section4that the ability to handle large complex multi-plication(CM)discriminants may have a positive in?uence on the minimization ofρ.In particular,for embedding degree k=2q where q is prime we describe how to build curves withρ～q/(q?1)and log(D)/log(r)～(q?3)/(q?1).Such discriminants are thus much smaller than expected from random curves with the same embedding degree.We also brie?y discuss the possibility of building curves of nearly-prime order over extension?elds.

We conclude and summarise our results in section5.

2The proposed method for k=12

Theorem1.There exists an e?cient algorithm to construct elliptic curves of prime order(of nearly arbitrary bitlength)and embedding degree k=12over a prime?eld.

Proof.We follow the strategy of parametrising p(x),n(x)and t(x),and using the property that n|Φk(t?1)as in[1].SinceΦ12is quartic and we know from the Hasse bound that n～p～t2,we must take t(x)to be a quadratic polynomial such that n(x)is a quartic factor ofΦ12(t?1).

Galbraith et al.showed[9]that the only quadratic polynomials u(x)such thatΦ12(u(x))splits into two irreducible quartic factors are u(x)=2x2and u(x)=6x2.Setting the trace of the Frobenius to be t(x)=6x2+1,we obtain

Φ12(t(x)?1)=n(x)n(?x),

where n(x)=36x4+36x3+18x2+6x+1.From the relation n=p+1?t we get the irreducible polynomial p(x)=n(x)+t(x)?1=36x4+36x3+24x2+6x+1. The CM norm equation becomes

DV2=4p?t2=3(6x2+4x+1)2.

Assuming that,for some x0,both n=n(x0)and p=p(x0)evaluate to prime numbers,the CM method for discriminant D=3[12,14]produces curves of form E(F p):y2=x3+b,with b=0.

Finding b is actually very simple:take the smallest b=0such that b+1is a

√

quadratic residue mod p and the point G=(1,

4Since the curve order n(x)is a large prime,there is no point of form(0,y),which would necessarily have order3.

In summary,we have the following parametrisation,where x may take either positive or negative values:

t=6x2+1,

n=36x4+36x3+18x2+6x+1,

p=36x4+36x3+24x2+6x+1,

DV2=108x4+144x3+84x2+24x+3=3(6x2+4x+1)2.

The choice u(x)=2x2as indicated in[9]is not considered,since in this case DV2factors as a square free product of irreducible polynomials which in general leads to an enormous CM discriminant D and therefore is not practical.This would also be the case if one took u(x)to be a linear polynomial.

Algorithm1shows how the CM method simpli?es in our setting.The al-gorithm takes as input value the desired bitlength of the primes p and n,and returns instances of these primes computed as indicated in the proof of theo-rem1,plus a parameter b∈F p such that the curve E(F p):y2=x3+b has order n over the?eld F p,and the coordinate y of a sample generator G=(1,y). Appendix A gives a few examples of cryptographic interest.Algorithm1tends to produce the smallest p and n of the desired bitlength,but it is straightfor-ward to modify it so that the output parameters meet other simple criteria(for instance,the examples in appendix A were selected to maximize p and n while keeping b=3).

The parametrisation given above may also be deduced in terms of[7].Choos-ing a polynomial u(x)such thatΦk(u(x))splits may then be interpreted as choosing a suitable number?eld in the following way.Let l(x)be an irreducible factor ofΦk(u(x))and consider the number?eld

K=Q[x]/(l(x)).

As u(x)is a root ofΦk over K it is a primitive k-th root of unity modulo l.If D is chosen such that?D is a square in K we set t(x)=u(x)i+1mod l(x) and V(x):=(u(x)i?1)√

Input:the approximate desired size m of the curve order(in bits).

Output:parameters p,n,b,y such that the curve y2=x3+b has order n over F p and the point G=(1,y)is a generator of the curve.

1:Let P(x)≡36x4+36x3+24x2+6x+1

2:Compute the smallest x≈2m/4such that?log2P(?x)?=m.

3:loop

4:t←6x2+1

5:p←P(?x),n←p+1?t

6:if p and n are prime then

7:exit loop

8:end if

9:p←P(x),n←p+1?t

10:if p and n are prime then

11:exit loop

12:end if

13:x←x+1.

14:end loop

15:b←0

16:repeat

17:repeat

18:b←b+1

19:until b+1is a quadratic residue mod p

20:Compute y such that y2=b+1mod p

21:G←(1,y)on the curve E:y2=x3+b

22:until nG=∞

23:return p,n,b,y.

Furthermore,for e?ciency reasons in the pairing computation it is desirable to generate curves of prime order n such that n has a low Hamming weight.Constructing such curves for k =12or ?(k )>4is still a research problem.3Six-to-one point and pairing compression

A fascinating possibility suggested by the proposed curves is to enable cryp-tosystems more e?cient than what was attainable with most previously known curves.We now consider two such improvements,namely,point compression and pairing compression,both to about one sixth of the requirements one would expect in naive implementations.

The basic idea for point compression is not only to restrict the ?rst pairing argument to E (F p ),but also to take the second argument Q ∈E (F p 12)as the im-age ψ(Q ′)of a point on a sextic twist E ′(F p 2),where ψ:E ′(F p 2)→E (F p 12)is an injective group homomorphism.This way one would work only with E (F p )and E ′(F p 2)for non-pairing operations like key generation,and map from E ′(F p 2)to E (F p 12)only when actually computing pairing values.As it turns out,it is possible to do better than this,namely,one can work with smaller ?elds,as we show next.

Lemma 1.There exists ξ∈F ?p 2such that X 6?ξis irreducible over F p 2[X ]

whenever p ≡1(mod 6).

Proof.Since p 2≡1(mod 6),the order of F p 2=p 2?1is a multiple of 6.Thus for any primitive root a ∈F p 2,the cube roots of unity are {1,ζ,ζ2}where ζ≡a (p 2?1)/3.Hence every cube u 3∈F ?p 2has three distinct cube roots,namely,

{u,ζu,ζ2u },which means that only one third of the elements of F ?p 2are cubes.

Analogously,only one half of the elements of F ?p 2are squares.Therefore,there

must be some element ξ∈F ?p 2that is neither a square nor a cube,and hence

X 6?ξis irreducible over F p 2[X ].??

Any ξ∈F ?p 2provided by lemma 1may be used to represent F p 12as F p 2[X ]/(X 6?ξ)and to de?ne a sextic twist E ′(F p 2):y ′2=x ′3+b/ξ.A sensible strategy to obtain ξwithout resorting to full F p 12arithmetic is to set 1/ξ=λ2μ3where λ∈F p is a noncube and μ∈F p 2is a nonsquare.

Let z ∈F p 12be a root of X 6?ξ.The corresponding map ψ:E ′(F p 2)→E (F p 12)is (x ′,y ′)→(z 2x ′,z 3y ′).Notice that x =z 2x ′∈F p 6and y =z 3y ′∈F p 4.Also,since any element of F p 12has the form a 5z 5+a 4z 4+a 3z 3+a 2z 2+a 1z +a 0the computation of ψ(Q ′)does not incur any multiplication overhead,and its rather sparse structure favours e?cient implementation of the pairing algorithm.

Alternatively,one may use ξ5instead of ξif the ?rst choice produces a twist E ′of wrong order (ξ2,ξ3,and ξ4give quadratic and cubic twists).

These considerations open the way to compressing pairing values to one sixth of their length in a way that is compatible with point reduction (that is,the technique of keeping only one point coordinate and entirely discarding the other

one).Notice that the map(x′,y′)→(z2x′,z3y′)produces a point on E(F p12)

whose x-coordinate is in F p6and whose y-coordinate is in F p4.

Now suppose that we keep only the y-coordinate of the point Q′=(x′,y′) on the twist E′(F p2):y′2=x′3+b/ξ(this is contrary to the conventional

choice of keeping only the x-coordinate).There are three points associated to this y-coordinate corresponding to the three cube roots of y′2?b/ξ.One of the points is Q′.Upon mapping onto E(F p12),it turns out that those points map to

conjugates over F p4(i.e.their images are of form Q,[p4]Q and[p8]Q)provided Q′is an n-torsion point.This can be seen from the following arguments.Notice that the order of the twist is#E′(F p2)=(p+1?t)(p?1+t)=n(2p?n)and hence there exist n-torsion points.Letφbe the p-th power Frobenius endomorphism

and tr F

p6:E(F p12)→E(F p6),R→R+φ6(R)the trace map over F p6.An

explicit computation leads to the following lemma.

Lemma2.Let Q′=(x′,y′)∈E′(F p2)and Q=ψ(Q′).Then tr F

(Q)=Q+φ6(Q)=O.

The Frobenius endomorphism has two eigenspaces in E(F p12)[n]for the eigenval-ues1,p.The1-eigenspace consists of all points in E(F p)while the p-Eigenspace is the set of points of trace zero.Therefore we obtain the following lemma which shows that for an n-torsion point whose F p6-trace is O computing the p-multiple is the same as computing the Frobenius endomorphism.

Lemma3.Let Q∈E(F p12)[n].Then tr F

(Q)=O i?φ(Q)=[p]Q.

Let Q=ψ(Q′)for an n-torsion point Q′on the sextic twist.From lemma2we see that we may apply lemma3and compute[p4]Q=φ4(Q)=((z2)p4x′,z3y′) as well as[p8]Q=φ8(Q)=((z2)p2x′,z3y′).The points Q,[p4]Q and[p8]Q share the same y-coordinate and therefore have to be the images underψof the above mentioned three points corresponding to the given y-coordinate on the twist.

The above shows that the pairing values computed from the three points are also conjugates over F p4(i.e.they are of the form e,e p4and e p8).Thus,the F p4-trace of these pairing values is the same for any of the three points.In other words,the choice of the cube root is irrelevant to compute the compressed pair-

ingε(P,Q′)≡tr F

p4(e(P,ψ(Q′)))=e(P,ψ(Q′))+e(P,ψ(Q′))p4+e(P,ψ(Q′))p8,

whose length is one third of the length of e(P,ψ(Q′)).

One even may go one step further and not only discard the x-coordinate of Q′but also discard one bit of its y-coordinate.This means we do not distinguish between Q′and?Q′.With help of the following lemma we can show that pairing compression up to one sixth of the actual pairing length is possible.

Lemma4.Letζbe an n-th root of unity in F p12and tr F

:F p12→F p2the

?nite?eld trace over F p2.Then tr F

p2(ζ?1)=tr F

(ζ).

Proof.Since n dividesΦ12(t?1)it dividesΦ12(p)=p4?p2+1.So n also divides p6+1=(p2+1)(p4?p2+1).Therefore sinceζis an n-th root of unity we have ζ?1=ζp6.We now see that tr F

(ζ?1)=ζ?1+ζ?p2+ζ?p4+ζ?p6+ζ?p8+ζ?p10=ζp6+ζp8+ζp10+ζ+ζp2+ζp4=tr F

(ζ).??

Note that all pairing values are n-th roots of unity in F p12and hence

tr F

p2(e(P,ψ(Q′)))=tr F

(e(P,ψ(Q′))?1)=tr F

(e(P,ψ(?Q′))).Together with

the transitivity of traces using the above condition on F p4-traces,this yields that the F p2-traces of the pairing values are equal for all points(x′,±y′),(ζ3x′,±y′) and(ζ23x′,±y′)whereζ33=1in F p2.

The advantage of this approach is that one can not only work exclusively on F p and F p2for non-pairing operations,but also represent points on E′(F p2)by the positive or negative of their y-coordinates alone in most protocols,yet obtain a unique compressed pairing value over F p2.We point out that the compression ratio of1/6is better than what is attainable on any practical supersingular Abelian variety,namely,8/30,as shown by Rubin and Silverberg[15].

Laddering techniques as those described in[16]to compute pairings may even make it unnecessary to implement full arithmetic over any?eld higher than F p2. Similar e?ects may be achieved in a torus-based setting as suggested in[10].If the x-coordinate corresponding to a point in E′(F p2)with given y-coordinate y′is needed,one may obtain it by simply computing a cube root of y′2?b/ξ.In appendix B we discuss the computation of cube roots in F?

4Considerations on composite order

Under some circumstances,a reasonably small cofactor may be quite acceptable. For instance,if256-bit prime?elds do not have a substantial impact on band-width occupation,the Brezing-Weng family of curves for k=8andρ～5/4 could provide roughly200-bit group orders and map the discrete logarithm on the curve to a2048-bit?nite?eld.Besides,as we already pointed out even val-ues of k are advantageous from the point of view of e?cient implementation of the pairing algorithm.It is thus interesting to investigate ways to produce more curves that meet the conditions that k be even andρ>1be as small as possible (say,ρ 5/4).

A naive approach to solving the norm equation DV2=4hΦk(t?1)?(t?2)2, namely,by choosing t and hoping to be able to handle the resulting D,is in general bound to failure since D～t?(k),where?(k)is Euler’s totient function. For instance,for k=2q where q is an odd prime we expect to?nd D～t q?1.

However,it would be quite simple to obtain curves with k=2q if we could handle a CM discriminant D as large as t q?3,attainingρ≡log(p)/log(r)～q/(q?1)as the following reasoning reveals.Let the trace of Frobenius have the form t=?4u2+2for some u(notice that t is negative),and let x=t?1.

Assume thatΦk(x)takes a prime value.Then set:

h=?(x?1)/4,

r=Φk(x)

=x q?1?x q?2+x q?3?x q?4+x q?5?···?x+1

=x q?1?x q?3(x?1)?x q?5(x?1)?···?x2(x?1)?(x?1),

p=hr+t?1,

DV2=4hr?(t?2)2

=?(x?1)x q?1+x q?3(x?1)2+x q?5(x?1)2+···+(x?1)2?(x?1)2 =?(x?1)x2[x q?3?(x?1)(x q?5+x q?7+···+1)].

By construction,the?(x?1)x2factor is a square,so D is the square-free part of z=x q?3?(x?1)(x q?5+x q?7+···+1).Since p=hr+t?1,it is also clear thatρ～q/(q?1).For instance,if k=10(i.e.ρ～5/4)we get z=x2?x+1,and a simple search produces parameters like these:

t=?931556989582:40bits

r=753074106157227719531468778253698105623799226081:160bits

p=175382861816372173247473133505975362972517516867279787545493:197bits ρ～1.237425

D=867798424841873127503473:80bits

Another example,now for k=14(i.e.ρ～7/6)where z=x4?x3+x2?x+1:

t=?82011134:27bits

r=304254450525046050085067914513460261078757135361:158bits

p=6238063280153705754947329076599940825481364534683333889:183bits

ρ～1.153987

D=45236739484946456935793243535361:106bits

Unfortunately,with currently available CM technology the only case where this construction is tractable occurs for k=6,where we get D=1but also ρ～3/2,much worse than plain MNT curves that attainρ～1.

4.1Curves over extension?elds

Another interesting observation is that,while none of the currently known methods to construct pairing-friendly curves for arbitrary k is able to produce curves over an extension?eld F p m,it may be possible to?ll this gap if su?-ciently large D can be handled.As Galbraith et al.point out[9],parametris-ing t=5x2+1causesΦ5(t?1)to split asΦ5(t?1)=r(x)r(?x),where

r(x)=25x4+25x3+15x2+5x+1.We observe that with cofactor h=4,this gives hr+t?1=(10x2+5x+2)2,a perfect square.This means that?nding an odd value x∈Z such that r and p=10x2+5x+2are both prime enables constructing an elliptic curve over a?nite?eld F p2with near-prime order n=4r. The CM equation here has the form DV2=5(5x2±2x+1)(15x2±10x+3). Solving a Pell-like equation can make one but not both of the factors5x2±2x+1 or15x2±10x+3to assume the form dy2for small d and some y.One might hope

that techniques like Hensel lifting could reduce the square-free part of the other factor to O(x),but it is not clear how to harmonise such techniques to solutions of the Pell-like equation.As a consequence,we expect that D～p～r1/2; practical values of p would need D～2100at least.

Nevertheless,such a parametrisation hints that algebraic methods to build ordinary pairing-friendly curves over extension?elds might exist for other em-bedding degrees,and deserved further research.

5Conclusion

We have presented a very simple algorithm to construct pairing-friendly curves of prime order and embedding degree k=12.This closes(and actually exceeds) the open problem proposed by Boneh et al.[5,section3.5]and enhances the se-curity level of most pairing-based cryptosystems,while also reducing bandwidth occupation(by either points or pairing values)down to1/6of the expected requirements;such levels of security and compression are better than what is attainable with any supersingular Abelian variety up to at least genus6.We leave it as an open problem the task of extending the method for higher values of k.

We have also discussed ways to produce curves of composite order and rea-sonably small cofactor as long as large discriminants fall within reach of CM methods,and pointed out the possibility of closing yet another problem,namely, building pairing-friendly curves of nearly-prime order over extension?elds.Fur-ther exploration of such possibilities is left for future research.

6Acknowledgments

We are grateful to Peter Birkner,Dan Boneh,Steven Galbraith,Florian He?, Tanja Lange,Ben Lynn,Alfred Menezes,Mike Scott,Fr′e Vercauteren,and Felipe Voloch for their valuable comments on an earlier version of this work.

References

1.P.S.L.M.Barreto,B.Lynn,and M.Scott.Constructing elliptic curves with pre-

scribed embedding degrees.In Security in Communication Networks–SCN’2002, volume2576of Lecture Notes in Computer Science,pages263–273.Springer-Verlag,2002.

2.P.S.L.M.Barreto,B.Lynn,and M.Scott.On the selection of pairing-friendly

groups.In Selected Areas in Cryptography–SAC’2003,volume3006of Lecture Notes in Computer Science,pages17–25.Springer-Verlag,2003.

3.P.S.L.M.Barreto,B.Lynn,and M.Scott.E?cient implementation of pairing-

based cryptosystems.Journal of Cryptology,17(4):321–334,2004.

4.I.Blake,G.Seroussi,and N.Smart.Advances in Elliptic Curve Cryptography.

Number317in London Mathematical Society Lecture Note Series.Cambridge University Press,Cambridge,UK,2005.

5. D.Boneh,B.Lynn,and H.Shacham.Short signatures from the Weil pairing.In

Advances in Cryptology–Asiacrypt’2001,volume2248of Lecture Notes in Com-puter Science,pages514–532.Springer-Verlag,2002.

6. D.Boneh,B.Lynn,and H.Shacham.Short signatures from the Weil pairing.

Journal of Cryptology,17(4):297–319,2004.

7. F.Brezing and A.Weng.Elliptic curves suitable for pairing based cryptog-

raphy.Cryptology ePrint Archive,Report2003/143,2003.Available from https://www.wendangku.net/doc/1517365556.html,/2003/143.

8.R.Dupont,A.Enge,and F.Morain.Building curves with arbitrary small MOV

degree over?nite prime?elds.Journal of Cryptology,18(2):79–89,2005.

9.S.Galbraith,J.McKee,and P.Valen?c a.Ordinary abelian varieties having small

embedding degree.Cryptology ePrint Archive,Report2004/365,2004.Available from https://www.wendangku.net/doc/1517365556.html,/2004/365.

10.R.Granger,D.Page,and M.Stam.On small characteristic algebraic tori in

pairing-based cryptography.Cryptology ePrint Archive,Report2004/132,2004.

Available from https://www.wendangku.net/doc/1517365556.html,/2004/132.

11.IEEE Computer Society,New York,USA.IEEE Standard Speci?cations for Public-

Key Cryptography–IEEE Std1363-2000,2000.

https://www.wendangku.net/doc/1517365556.html,y and H.G.Zimmer.Constructing elliptic curves with given group order

over large?nite?elds.In Algorithmic Number Theory Symposium–ANTS-I, volume877of Lecture Notes in Computer Science,pages250–263.Springer-Verlag, 1994.

13. A.Miyaji,M.Nakabayashi,and S.Takano.New explicit conditions of elliptic curve

traces for FR-reduction.IEICE Transactions on Fundamentals,E84-A(5):1234–1243,2001.

14. F.Morain.Building cyclic elliptic curves modulo large primes.In Advances in

Cryptology–Eurocrypt’1991,volume547of Lecture Notes in Computer Science, pages328–336.Springer-Verlag,1991.

15.K.Rubin and A.Silverberg.Supersingular abelian varieties in cryptology.In

Advances in Cryptology–Crypto’2002,volume2442of Lecture Notes in Computer Science,pages336–353.Springer-Verlag,2002.

16.M.Scott and https://www.wendangku.net/doc/1517365556.html,pressed pairings.In Advances in Cryptology

–Crypto’2004,volume3152of Lecture Notes in Computer Science,pages140–156, Santa Barbara,USA,2004.Springer-Verlag.

17.M.Scott and P.S.L.M.Barreto.Generating more MNT elliptic curves.Designs,

Codes and Cryptography,2005.To appear.

A Some curves of prime order and k=12

All of the following curves satisfy the equation E(F p):y2=x3+3,with prime order n and trace of the Frobenius t.A sample generator for any of them is

G=(1,2).In all cases p≡3(mod4)and p≡4(mod9)(to simplify the computation of square and cube roots),and the bitlengths of p and n are equal. The?eld F p2is represented as F p[X]/(X2+1),and i is a root of X2+1.The sextic twist for all examples has the form E′(F p2):y′2=x′3+3/ξ,where 1/ξ=λ2μ3=?8+8i,λ=2,andμ=1+i.

160bits:

p=1461501624496790265145448589920785493717258890819

n=1461501624496790265145447380994971188499300027613

t=1208925814305217958863207

192bits:

p=6277101719531269400517043710060892862318604713139674509723

n=6277101719531269400517043709981664699904401744160036556389

t=79228162414202968979637953335

224bits:

p=26959946667149205758383469736921695435015736735261155141423417423923 n=26959946667149205758383469736921690242718878200571531029749235996909 t=5192296858534689624111674181427015

256bits:

p=115792089237314936872688561244471742058375878355761205198700409522629\ 664518163

n=115792089237314936872688561244471742058035595988840268584488757999429\ 535617037

t=340282366920936614211651523200128901127

B Computing cube roots

Each prime number of form p(x)=36x4+36x3+24x2+6x+1is congruent to 6x2+6x+1(mod9)and hence for all values of x∈Z it holds that p(x)≡1 (mod9)or p(x)≡4(mod9).In the second case where we get a prime p≡4 (mod9)computing cube roots modulo p only takes one exponentiation which may be seen from the following.

Letαbe a primitive element of F?p.The set of all cubes in F?p is exactly {α3l|l∈Z}.Now let a be a cube in F?p.Then a(p?1)/3≡1(mod p).Therefore we get a simple possibility to compute a cube root r of a by one exponentiation

r≡a(2p+1)/9(mod p).

Since(2p+1)/9is the inverse to3modulo(p?1)/3,this clearly gives a cube root of a.

The examples given in appendix A all have p≡4(mod9).For recovering the x-coordinate of points on E′(F p2)given only their y-coordinate as it was

.We consider indicated in section3one needs to compute a cube root in F?

the case p≡4(mod9).Then p2≡7(mod9).For a cube a∈F?p2it holds a(p2?1)/3=1for the same reasons as in the F p case.Again the computation of a cube root only takes one exponentiation r=a(p2+2)/9.

关于时间管理的英语作文 manage time

How to manage time Time treats everyone fairly that we all have 24 hours per day. Some of us are capable to make good use of time while some find it hard to do so. Knowing how to manage them is essential in our life. Take myself as an example. When I was still a senior high student, I was fully occupied with my studies. Therefore, I hardly had spare time to have fun or develop my hobbies. But things were changed after I entered university. I got more free time than ever before. But ironically, I found it difficult to adjust this kind of brand-new school life and there was no such thing called time management on my mind. It was not until the second year that I realized I had wasted my whole year doing nothing. I could have taken up a Spanish course. I could have read ten books about the stories of successful people. I could have applied for a part-time job to earn some working experiences. B ut I didn’t spend my time on any of them. I felt guilty whenever I looked back to the moments that I just sat around doing nothing. It’s said that better late than never. At least I had the consciousness that I should stop wasting my time. Making up my mind is the first step for me to learn to manage my time. Next, I wrote a timetable, setting some targets that I had to finish each day. For instance, on Monday, I must read two pieces of news and review all the lessons that I have learnt on that day. By the way, the daily plan that I made was flexible. If there’s something unexpected that I had to finish first, I would reduce the time for resting or delay my target to the next day. Also, I would try to achieve those targets ahead of time that I planed so that I could reserve some more time to relax or do something out of my plan. At the beginning, it’s kind of difficult to s tick to the plan. But as time went by, having a plan for time in advance became a part of my life. At the same time, I gradually became a well-organized person. Now I’ve grasped the time management skill and I’m able to use my time efficiently.

英语演讲稿：未来的工作

英语演讲稿：未来的工作这篇《英语演讲稿范文：未来的工作》，是特地，希望对大家有所帮助！热门演讲推荐：竞聘演讲稿 | 国旗下演讲稿 | 英语演讲稿 | 师德师风演讲稿 | 年会主持词 | 领导致辞 everybody good afternoon:. first of all thank the teacher gave me a story in my own future ideal job. everyone has a dream job. my dream is to bee a boss, own a pany. in order to achieve my dreams, i need to find a good job, to accumulate some experience and wealth, it is the necessary things of course, in the school good achievement and rich knowledge is also very important. good achievement and rich experience can let me work to make the right choice, have more opportunities and achievements. at the same time, munication is very important, because it determines whether my pany has a good future development. so i need to exercise their municative ability. i need to use all of the free time to learn

幼儿园教职工大会主持词三篇

幼儿园教职工大会主持词三篇根据大会日程安排，**县机关幼儿园第一届二次教代会现在正式开幕。这次大会代表共×××名。应到代表×××名，实到25名，符合法定人数，能够开会。现在我向大家介绍今天到会的特邀代表：教育工会委员许友贵老师、封任辉老师；机关幼儿园前任园长曹晓虹老师；机关幼儿园前任工会主席徐学芬老师。现在我宣布：**县机关幼儿园第一届二次教代会现在开幕。大会第一项：请全体起立，奏《中华人民共和国国歌》，请坐下。大会第二项：请**县教育工会委员许友贵老师讲话。大会第三项：请幼儿园副园长李亚丽老师代表园行政致贺词。大会第四项：请幼儿园园长皆映萍老师做《幼儿园园务工作报告》。大会第五项：请副园长王艳琼老师做《幼儿园后勤工作报告》。大会第六项：请幼儿园工会主席周映存老师做《幼儿园工会工作报告》大会第七项：请皆园长就本次教代会所征集的提案做《幼儿园提案工作报告》。各位代表：今天早上的议程到此结束，请各位到西院合影留念。下午：各位代表，今天下午2：30—3：30我们实行了大会的第一项和第二项议程：分组讨论各种报告和代表提案；行政领导、各组负责人及相关人员召开了意见或建议反馈会议。现在我们实行今天下午的第三项议程：请各位代表就提交本次会议的报告、提案实行表决。

1、同意《幼儿园园务工作报告》的请举手。不同意请举手。通过。 2、同意《幼儿园后勤工作报告》的请举手。不同意请举手。通过。 3、同意《幼儿园工会工作报告》的请举手。不同意请举手。通过。 4、同意《幼儿园提案工作报告》的请举手。不同意请举手。通过。大会第四项议程：请皆园长就各位代表团讨论的意见和建议作整改说明。大会第五项议程：请幼儿园工会主席周映存致闭幕词。各位代表：**县机关幼儿园第一届二次教代会经过一天的时间圆满地完成大会议程，现在闭幕。【篇二】今天是立秋的第四天，在二十四节气中，立秋寓意着万物成熟丰收的季节到了。在这个丰收的季节里，我们又将迎来一个新的学期，当看到大群孩子涌入我们幼儿园的场面，想想就觉得热血沸腾！在过去的一学期里，在坐的各位与我们全体教职工用责任感和事业心，确保了幼儿园各项工作正常、有序的展开，我们对这个充满快乐与幸福的大家庭付出了真心，才会如此的热爱这份职业，珍惜这个岗位，并为其付出更多也无怨无悔。在这里让我们掌声送给自己！今天的会议分为三项：第一项是分享；第二项是各园对近期工作的总结与倾诉；第三项是由经理为我们作出工作指导。我要与大家分享的是一份《家庭教育手册》。大家都知道，七月份经理和我们分享了一篇《日本启蒙教育启示录》，看完之后，我感

关于坚持的英语演讲稿

关于坚持的英语演讲稿 Results are not important, but they can persist for many years as a commemoration of. Many years ago, as a result of habits and overeating formed one of obesity, as well as indicators of overall physical disorders, so that affects my work and life. In friends to encourage and supervise, the participated in the team Now considered to have been more than three years, neither the fine rain, regardless of winter heat, a day out with 5:00 time. The beginning, have been discouraged, suffering, and disappointment, but in the end of the urging of friends, to re-get up, stand on the playground. 成绩并不重要，但可以作为坚持多年晨跑的一个纪念。多年前，由于庸懒习惯和暴饮暴食，形成了一身的肥胖，以及体检指标的全盘失常，以致于影响到了我的工作和生活。在好友的鼓励和督促下，参加了晨跑队伍。现在算来，已经三年多了，无论天晴下雨，不管寒冬酷暑，每天五点准时起来出门晨跑。开始时，也曾气馁过、痛苦过、失望过，但最后都在好友们的催促下，重新爬起来，站到了操场上。 In fact, I did not build big, nor strong muscles, not a sport-born people. Over the past few years to adhere to it, because I have a team behind, the strength of a strongteam here, very grateful to our team, for a long time, we encourage each other, and with sweat, enjoying common health happy. For example, Friends of the several run in order to maintain order and unable to attend the 10，000 meters race, and they are always concerned about the brothers and promptly inform the place and time, gives us confidence and courage. At the same time, also came on their own inner desire and pursuit for a good health, who wrote many of their own log in order to refuel for their own, and inspiring. 其实我没有高大身材，也没健壮肌肉，天生不属于运动型的人。几年来能够坚持下来，因为我的背后有一个团队，有着强大团队的力量，在这里，非常感谢我们的晨跑队，长期以来，我们相互鼓励着，一起流汗，共同享受着健康带来的快

家庭教育手册培训资料.docx

日本家庭教育手册，先进的教育理念值得我们学习！导读： 1999年4月，日本文部省颁布了《家庭教育手册》，国内教育学者编译了中文版本，全文分为“家庭是什么”、“家教”、“同情心”、“个性与理想”、“游戏”等五大板块，内容通俗易懂，却极有深度和针对性。邻国十几年前的家教手册，在中国的今天，依然还属前沿，实在是值得反思。本手册内容齐全，科学性强，推荐大家收藏，常读常思常用。（一）家庭是什么孩子最大的愿望是家里人都能愉快地过日子当问及孩子 " 你对家庭有什么更高的期望" 时，孩子回答得最多的是" 家里人都能愉快地过日子。" 孩子们在企求这么理所当然的事，作为父母应该认真面对这样的现实。

只要给孩子提供必要的东西，孩子就能自然地成长的时代已经过去了。现在，安宁、愉快的家庭需要全家人有意识的共同努力。为了孩子，为了自己，请对家庭进行一次再认识吧。不会珍惜自己的人也不会珍惜孩子养育孩子确实很重要，但是整天神经绷得紧紧的也吃不消，父母的烦躁不安会传染给孩子。正因为养育孩子很辛苦，所以，拥有属于自己的时间，保持心理健康很重要。父母应互相配合，共同承担。有效利用孩子去托幼机构的时间，可让你的身心有个 " 休整 "。另外，有什么事别自己一个人烦恼。鼓起勇气去家庭教育咨询中心、保健中心、儿童咨询所等处跟专家谈谈。在家里，父母充满幸福的笑容，会使孩子感受到幸福。 "养育孩子是母亲的事 " ，有这种想法的父亲要当心认为，在现代家庭里，父亲的权威变得越来越弱，对孩子辨别善恶、分清好坏的社会教育也越来越马虎。通常，父亲和母亲的育儿方针基本一致，但父亲和母亲站在不同的角度教育孩子，能纠正过于密切的母子关系。父亲自然地参与养育孩子，发挥父亲的影响力，父母的互相积极很有必要。母亲应注

Ellipticine_DNA拓扑异构酶II抑制剂_CAS号519-23-3说明书_AbMole中国

分子量246.31溶解性（25°C ） DMSO 10 mM 分子式C17H14N2Water CAS 号519-23-3Ethanol 储存条件 3年 -20°C 粉末状生物活性 Ellipticine 是一种DNA 拓扑异构酶II 抑制剂。Ellipticine 玫瑰树碱作用的另一种方式是通过其与细胞色素P450（CYP ）和过氧化物酶的氧化介导的共价DNA 加合物的形成。Ellipticine 还可以作为生物转化酶的抑制剂或诱导剂，从而调节其自身的代谢，从而产生其遗传毒性和药理作用。体内研究显示，Ellipticine 治疗导致在几种健康?官（肝，肾，肺，脾，乳腺，心脏和脑）和乳腺癌DNA 中产生玫瑰树碱衍生的DNA 加合物。在这些腺癌中产生的玫瑰树碱衍生的DNA 加合物的水平几乎是正常健康乳腺组织的2倍。实验操作来自于公开的文献，仅供参考细胞实验细胞系MCF-7, U87MG, CCRF-CEM, UKF-NB-3 and UKF-NB-4 neuroblastoma cell lines 方法 Cells in exponential growth were seeded at 1×10 per well in a 96-well microplate. After incubation (48 hours) at 37 °C in 5% CO2saturated atmosphere the MTT solution (2 mg/ml PBS) was added, the microplates were incubated for 4 hours and cells lysed in 50%N,N-dimethylformamide containing 20% of sodium dodecyl sulfate (SDS), pH 4.5. The absorbance at 570 nm was measured for each well by multiwell ELISA reader Versamax (Molecular devices, CA, USA). The mean absorbance of medium controls was subtracted as a background. The viability of control cells was taken as 100% and the values of treated cells were calculated as a percentage of control. The IC50 values were calculated from at least 3 independent experiments using linear regression of the dose-log response curves by SOFTmaxPro. 浓度0, 0.1, 1, 5 or 10 μM 处理时间 48 hours 动物实验动物模型配制剂量给药处理不同实验动物依据体表面积的等效剂量转换表（数据来源于FDA 指南）小鼠大鼠兔豚鼠仓鼠狗重量 (kg)0.020.15 1.80.40.0810体表面积 (m )0.0070.0250.150.050.020.5K 系数 3 6 12 8 5 20 动物 A (mg/kg) = 动物 B (mg/kg) × 动物 B 的K 系数动物 A 的K 系数例如，依据体表面积折算法，将白藜芦醇用于小鼠的剂量22.4 mg/kg 换算成大鼠的剂量，需要将22.4 mg/kg 乘以小鼠的K 系数（3），再除以大鼠的K 系数（6），得到白藜芦醇用于大鼠的等效剂量为11.2 mg/kg 。 Ellipticine 目录号M9023 化学数据 42m m m m m

IEC CURVES SI VI EI

Functions 1 Phase Overcurrent Protection When the phase current exceeds the low-set I> setting value, the overcurrent low-set element starts and delivers a start signal to the display panel and a group of preassigned relay outputs. After a delay time, determined by the inverse time current characteristic curve selected and the measured current or by definite time t>, this overcurrent element operates and delivers a trip signal to the display panel and a group of relay outputs that are configured to link to the low-set phase overcurrent tripping. When the phase current exceeds the high-set I>> setting value, the overcurrent high-set element starts and delivers a start signal to the display panel and a group of preassigned relay outputs. After a preset time, determined by t>>, this overcurrent element operates and delivers a trip signal to the display panel and a group of relay outputs that are configured to link to high-set phase overcurrent tripping. 2 Earth-Fault Protection When the earth-fault current exceeds the low-set Io> setting value, the earth-fault low-set element starts and delivers a start signal to the display panel and a group of preassigned relay outputs. After a delay time, determined by the inverse time current characteristic curve selected and the measured current or by definite time to>, this earth-fault element operates and delivers a trip signal to the display panel and a group of relay outputs that are configured to link to the low-set earth-fault tripping.When the earth-fault current exceeds the high-set Io>> setting value, the earth-fault high-set element starts and delivers a start signal to the display panel and a group of preassigned relay outputs. After a preset time, determined by to>>, this earth-fault element operates and delivers a trip signal to the display panel and a group of relay outputs that are configured to link to high-set earth-fault tripping. Introduction The MK2200 combined overcurrent and earth-fault relay is a digital microprocessor based relay. This relay employs extensive advance numerical techniques implemented in real-time, for the computation of measured input quantity. Other advance features include programmable control output, metering and fault data recording. Application The MK2200 combined overcurrent and earth-fault relay is used where time graded overcurrent and earth fault protection is required. Features ? Multifunction numerical relay ? Three-phase, low-set and high-set phase overcurrent ? Two sets of low-set and high-set setting for phase overcurrent ? Low-set and high-set earth fault ? Two sets of low-set and high-set setting for earth fault ? Four selectable IDMT characteristic curves ? Definite time for low-set and high-set ? Numeric display of phase and earth fault currents ? Display of relay settings ? 9 non- volatile records of previous trip-ping currents ? Recording of relay start time ? Highly flexible programmable relay outputs ? Multifunction external digital input ? Isolated RS485 Modbus - RTU communication ? Selectable 50 Hz / 60 Hz C o m b i n e d O v e r c u r r e n t & E a r t h F a u l t R e l a y M K 2200MK2200

关于管理的英语演讲

1.How to build a business that lasts100years 0:11Imagine that you are a product designer.And you've designed a product,a new type of product,called the human immune system.You're pitching this product to a skeptical,strictly no-nonsense manager.Let's call him Bob.I think we all know at least one Bob,right?How would that go? 0:34Bob,I've got this incredible idea for a completely new type of personal health product.It's called the human immune system.I can see from your face that you're having some problems with this.Don't worry.I know it's very complicated.I don't want to take you through the gory details,I just want to tell you about some of the amazing features of this product.First of all,it cleverly uses redundancy by having millions of copies of each component--leukocytes,white blood cells--before they're actually needed,to create a massive buffer against the unexpected.And it cleverly leverages diversity by having not just leukocytes but B cells,T cells,natural killer cells,antibodies.The components don't really matter.The point is that together,this diversity of different approaches can cope with more or less anything that evolution has been able to throw up.And the design is completely modular.You have the surface barrier of the human skin,you have the very rapidly reacting innate immune system and then you have the highly targeted adaptive immune system.The point is,that if one system fails,another can take over,creating a virtually foolproof system. 1:54I can see I'm losing you,Bob,but stay with me,because here is the really killer feature.The product is completely adaptive.It's able to actually develop targeted antibodies to threats that it's never even met before.It actually also does this with incredible prudence,detecting and reacting to every tiny threat,and furthermore, remembering every previous threat,in case they are ever encountered again.What I'm pitching you today is actually not a stand-alone product.The product is embedded in the larger system of the human body,and it works in complete harmony with that system,to create this unprecedented level of biological protection.So Bob,just tell me honestly,what do you think of my product? 2:47And Bob may say something like,I sincerely appreciate the effort and passion that have gone into your presentation,blah blah blah-- 2:56(Laughter) 2:58But honestly,it's total nonsense.You seem to be saying that the key selling points of your product are that it is inefficient and complex.Didn't they teach you 80-20?And furthermore,you're saying that this product is siloed.It overreacts, makes things up as it goes along and is actually designed for somebody else's benefit. I'm sorry to break it to you,but I don't think this one is a winner.

关于工作的优秀英语演讲稿

关于工作的优秀英语演讲稿 Different people have various ambitions. Some want to be engineers or doctors in the future. Some want to be scientists or businessmen. Still some wish to be teachers or lawers when they grow up in the days to come. Unlike other people, I prefer to be a farmer. However, it is not easy to be a farmer for Iwill be looked upon by others. Anyway,what I am trying to do is to make great contributions to agriculture. It is well known that farming is the basic of the country. Above all, farming is not only a challenge but also a good opportunity for the young. We can also make a big profit by growing vegetables and food in a scientific way. Besides we can apply what we have learned in school to farming. Thus our countryside will become more and more properous. I believe that any man with knowledge can do whatever they can so long as this job can meet his or her interest. All the working position can provide him with a good chance to become a talent. 1 ————来源网络整理，仅供供参考

李季湄日本的《家庭教育手册》(二)

李季湄日本的《家庭教育手册》（二）家教 ·不知为什么，孩子的缺点跟父母总很相似那些“只要自己好就行，别的我不管”、不守公德的人，让人讨厌、不可信赖。如果自己的孩子这样做时，大众不予以纠正，孩子会误认为自己做得对，这样就可能慢慢变成一个不讨人喜欢的人。应抛弃“只要自己的孩子好就行，别的我不管”的想法。孩子做错事时，要以父母之爱严正斥责、严加管教。同时，大人自己也要注意尽量不做出轨的事，做能一直让孩子依赖、尊敬的父母。 ·“规矩”是为谁定的在家里，孩子们有时候守规矩，有时候“犯规”，由此逐渐学会处理人与人之间的关系，了解社会规则的重要性。家规不仅包括日常问候、门限时间、关灯时间等，还包括不给别人添麻烦、不撒谎等社会规范。为了让孩子懂规矩并一直遵守规矩，父母要经过认真讨论，定出明确的家规，父母和孩子一起遵守这个家规。另外，倾听孩子 __、和孩子共同定家规也很重要。 ·如果你想让孩子不幸，那就什么都给他买吧如果父母不加考虑，尽给孩子买东西，容易使孩子失去为了得到自己想要的东西而努力、忍耐、多加思考的精神，而变得什么都想要、不能自控。

不管孩子怎么闹缠人，不必要的东西不给买。不要给太多的零花钱。让孩子在定额的零花钱中自己安排、调整怎样花。如果真为孩子着想，比起在孩子身上花很多钱，更应在孩子身上花费心血，倾注父母之爱。 ·如果让孩子帮着做家务，他将变得很能干孩子们有自我中心的言行、自立推迟等倾向，主要因为自我责任感没有形成。日本的父母太宠爱孩子，好多人没有受过“自己的事儿自己做”的家教。在家里定出规矩，让孩子分担家务，对培养孩子的责任感、自立心、感受到自己是有用的人等方面很重要。让孩子从“把用过的东西好”等小事做起，养成和父母一起做家务的习惯。 ·如果孩子最好的朋友是电视，那太寂寞啦如果孩子整天呆在屋里看电视、看录像、玩电子游戏的话，容易造成与他人、与大自然接触的体验不够，与他人不能很好地交流，缺乏同情心，生与死的现实感薄弱，不能区别现实与假想世界，给孩子身心的健康成长留下阴影。给孩子创设与其他小朋友一起玩、自然体验的机会，并让其积极参加。定出不多看电视、录像，不多玩电子游戏的规矩，并使孩子养成遵守这些规矩的习惯。 ·给孩子单独房间的同时，也给他定好规矩吧

A new elliptic contour extraction method for reference hole detection in robotic drilling

INDUSTRIAL AND COMMERCIAL APPLICATION A new elliptic contour extraction method for reference hole detection in robotic drilling Biao Mei ?Weidong Zhu ?Guorui Yan ? Yinglin Ke Received:29September 2013/Accepted:22July 2014/Published online:3August 2014óSpringer-Verlag London 2014 Abstract In robotic drilling of aircraft structures,refer-ence holes are pre-drilled on aircraft structures and then detected by vision systems in the drilling process to com-pensate for the relative positioning errors between the robot tool center point and the workpiece,thus achieving improved position accuracy of drilled holes.In this paper,a novel elliptic contour extraction method based on salient region detection and optimization with snakes model is proposed for reference hole detection.Firstly,salient region detection is used for segmenting the region of ref-erence hole from the background,and the resultant image of this operation is used for contours retrieving.Secondly,the initial contour of the reference hole is obtained from the retrieved contours using the voting method.Then the initial contour of the reference hole is further re?ned with the snakes model through energy minimizing of the snake.Finally,the elliptical parameters of the reference hole are computed by ?tting an ellipse to the evolving result of the snake.The robustness and accuracy of reference hole detection with respect to noise and environmental distur-bance are enhanced signi?cantly through saliency estima-tion and optimization with the snakes model.Experimental results reveal that the proposed method can be applied to detect reference holes accurately and robustly in the jam-ming environment of aircraft assembly. Keywords Ellipse áContour extraction áSalient áVoting áSnakes áRobotic drilling 1Introduction With the improvement of the position accuracy of indus-trial robots and the development of stiffness compensation and off-line programming,robotic drilling system has become an effective ?exible fastener hole drilling platform for aircraft industry [1].In the process of robotic drilling,the system needs a mathematical model of the workpiece as the basis for creating the robot programs.However,sig-ni?cant differences of position and shape often exist between the workpiece and its mathematical model,lead-ing to incorrect positions of drilled fastener holes.There-fore,robotic drilling systems [2,3]are often integrated with a vision-based measurement unit to improve the position accuracy of the drilled fastener holes.To modify the drilling positions of fastener holes according to the actual workpiece in the assembly environment,typically a set of reference holes are drilled in advance on the work-piece.The actual position of the reference holes in the assembly environment are measured with the vision unit of the robotic drilling system,and the drilling positions of the fastener holes can be corrected according to the deviations between the actual positions and nominal positions of the reference holes. The detection of reference holes is based on accurate contour extraction and description of reference holes in images.In addition,due to the in?uence of noise,illumi-nation intensity and re?ection,accurate detection of ref-erence holes requires more robust algorithms than other applications.This paper focuses on improving the anti-noise performance and weakening the environmental impact in reference hole detection as well as ensuring the accuracy and effectiveness of the vision-based measure-ment.The contours of reference holes,although should be circular in theory,are elliptic in images taken with 2D B.Mei áW.Zhu (&)áG.Yan áY.Ke The State Key Lab of Fluid Power Transmission and Control,Department of Mechanical Engineering,Zhejiang University,Hangzhou 310027,China e-mail:wdzhu@https://www.wendangku.net/doc/1517365556.html, Pattern Anal Applic (2015)18:695–712DOI 10.1007/s10044-014-0394-6