vcctor. The major advantage of this technique compared with the SVD is the low computational cost while achieving the same accuracy. The cost of both methods measured in flops is given in the second row of Tablc I . To givc more numcrical stability to the new approach and further reduce the computational cost, products of type H,7. H,, are avoided. Note that this product i s basic in Harley's schema. Since conrl(HF.H,,j = [cond(HJ2, this leads to an unnecessary worsening of the condition of the system. Using these arguments the following more efficient algorithm for the estimation of the epipolar geometry is proposed: (i) Find transformjitions T,. and T, by performing a QR decomposition on C/r and Ur,respectively. (ii) Transform the image co-ordinates according to transformations U , = T,.U,.and U, = T,Uk (iii) Find the essential matrix E corresponding to the transformed co-ordinates. Here the least eigenvector of H, should be estimated by performing a QR decomposition and two steps of the inverse iteration algorithm on the resulting triangular matrix. (iv) Set E = TTET,. The introduced numerical optimisations of the NEPA algorithm provides the same accuracy in the results at lower computational cost. This important property makes the method very suitable for real-time applications. Selected re.wlts: The proposed technique has been evaluated by estimating the epipolar geometry for real images. Several comparisons with results obtained using other previously reported methods have been conducted. In these comparisons both performance and complexity have been evaluated. A comprehensive report of this comparative evaluation will be presented elsewhere. In this Letter a result obtained for the scene GWEN is reported. The epipolar lines obtained with the proposed algorithm are shown in Fig. 1. In this representation both stereo images are shown in the background. Superimposed on Fig. ILI the matched points are highlighted; the epipolar lines corresponding to these points are shown in Fig. lh. 0 IEE 2001 I 1 Decenzber 2000 E1cctrotiic.r Lettecr Online iVo: 20010675 DOI: 10.1049/el:20010675 E. lxquierdo (Deppartmrnt of Electronic Engiiieering, Queen Mciry and Westfield College, tiniversity of London, Mile End Roud, London El 4NS, United Kingdom) E-mail: e.izquierdo@elec.qmw.ac.uk V. Cuerra (Group of Nunzericrrl Methods. Institute of Math, Cj,hernetics and Physim, Havanu, Cuhu) 2 9 cy =z + z/u with 2,y E Fq It is well known that Fq(o)x, denoting the multiplicative group of nonzero elements in Fq(o): is a cyclic group of order q2 1. The Galois group GaI(F,(w)IF,,) of F,(wj over 6, is a group of order 2 generated by the Frobenius automorphism p on F,(w) sending each element to its yth power. Since p permutes roots of the minimal polynomial of w we easily find w + w'i = -a and wqL1= h. We now define the norm map N: F,(w) + Fq given by N(a) = ap(a)= aL/+'. Since the norm map is multiplicative it turns out to be a group homomorphism when restricted to c,(w)x. Denoting thc Kernel of the norm map by Ker(N) we obtain the following: Theorem 1: (1) Ker(N) is a cyclic group of order q + 1; (2) If y is a gcnerator of 61(w)x. then y+ is a generator of Ker(N). P r w f uf Theorem 1: The first assertion follows at once from that the nonn map N: l$(o)x+ F," is a group homomorphism. The second is immediate from N ( v {) = 1, 0 For any a = x + yw E Ker(N), one can explicitly compute its norm and the following equation is easily derived - + yw) = ( x + yw)(z + yw") = 2 - a,zy + by2 = 1 N(J - IZQUIERDO. E.: 'High accuracy solution to the correspondence problem', Electron. Lett., 2000. 36, (II), pp. 948 -949 HARTLLY, R.I.: 'In defense of the eight-point algorithm', IEEE Truns. Pattern Anal. Much Intell., 1997, 19: pp. 580 ~ 5 9 3 Operation-eff icient subgroups of finite fields Sangtae Jeong, Young-Ho Park a n d Sangho Oh A specific norm-1 subgroup of thc whole multiplicativc group in a quadiatic extension field of a finite field is introduced and it is shown that like elliptic curves, the signed binary method is applicable for fact exponentiation in the proposed group. Introthclion; It was suggested by Elgamal [I] that linitr extension fields can bc considcrcd, instcdd of prime fields, Ior use in public key cryptosystems; howcvcr: no direct computational advantages were implied. As also suggcsted by experts [2 - 41, the discrete log problem on subgroups of prime order nearly equal to 216" in extension fields can be considered to be intractablc against wellknown attacks such as the Shanks and Pollard methods. Thc dominant cost operation in discrete-logarithm-basedschemes is 'exponentiation', namely, computing 2 wherc g is an element of the proposed group G for cryptosysteni and k is an integer less than 954 subgroup: Let 6, be a finite field of y elements where q is a power of a prime number p and let Fq(w) be a quadratic extension of F obtained by adjoining a root CO of an irreducible polynomial + a X + b over Fq. Every element of F,(w) can then be uniquely represented as an FJinear combination of a basis { 1, w), i.e. for any a E F,(w) Nor" From this one can deduce the inverse of a = x easily given by the formula a = (x ay) yw. References 1 the order of G. Vaiious methods for speeding up exponentiation such as the binary method, the signed binary method, windowing techniques, etc. have been devised [5]. The signcd binary method, howcvcr, is not applicable to the multiplicative groups of finite fields since computing an inverse requires much greater cost than does the usual multiplication in finite fields of characteristic > 2. In this Letter we introduce a specific subgroup of elements of norm 1 in a quadratic extension field of a finite field as an alternative to the classical public key cryptosystem based on the discrete logarithm problem on a prime finite field. The proposed group has two computational advantages: one is that we can select a nonconventional basis for efficient arithmetic in the base field; the other is that the inverse can be computed for free, so like elliptic curves the signed binary method is applicable for fast exponentiation in the group. Together. these two advantages lead to a running time improvement of up to 40% compared to ordinary exponentiation on a large prime field. + yw E Ker(N) is - Fast arithmetic in larger ,fields:We recall some notations introduced in the previous Section, retaining the rest of all notations there. Let Fq be a finite field of y elements where 4 = 2 mod(3) is a pth power, i.e. q = pm for some integer i n and let Fq(wj be a yuadratic extension of Fq oblained by adjoining a root w of an irreducible polynomial of the form x? + aX + b over e,.To speed up arithmetic in the larger field Fq(w),we take an all-one polynomial X + X + 1 over a finite field 6, as the minimal polynomial of w. The irreducibility of the polynomial is satisfied by q being congruent to 2 mod(3). In addition, we will make use of a non-conventional basis {w, d}of Fq(w) over F,, instead of a polynomial basis { I , w) to sccure efficient arithmetic in the larger field F,(w). In fact, from q 2 mod(3), the zeros 0, W of the polynomial X + X + 1 form an optimal normal basis of Fq(w) over ei. We also note that any element a E F&w) can be uniquely represented as an Fqlinear combination of {w: w?} since w* = w'.For any M = xw + yw?, we get a[{= (xw + yd)q = xw'i + y d q = yw + xd.This 4th power map yields the following: Lemma 2 If a = xw + yd is an element in Ker(N), then the invcrse of a is given by the formula U-l = + + ( m yw2) = ?/U :Ed* It follows by Lemma 2 that getting the inverse of an element in Kor(N) does not require arithmetic operations and can thus be considered to be for free. Moreover, efficient arithmetic operations for squaring and multiplications in Fq(w)is ensured by the following lemma [Lv]. ELECTRONICS LETTERS 19th July2007 Vol. 37 No. 75 Lenmu 3 A squaring and a multiplication in F,(w) can be achieved, respectively, hy two and three multiplications in I$ Cryptographic applications: We now proceed to propose a group which is suitable for cryptographic applications by using K e r ( w . We take two fields 6, and its quadratic extension F,(wj satisfying all conditions in the previous Section for fast arithmetic in F,(w). For now: we let J be a 160 bit prime number dividing q + 1, which is the order of' a subgroup of Ker(N) on which the discrete log problem is presumed to be equivalent to that of the whole group &l(wy.Taking y?a generator of' Fq(w)X, so that YJ-' is a generator of Ker(N) we set g = fj2-I)''. As a possible underlying group for a new public-key cryptosystem, we form the group G generated by the element g, which is a cyclic subgroup of Kcr(N) of order I. Since the chosen prime I does not &vide pd - 1 for any divisor d of Mz one can see that the cyclic group G is not embedded explicitly into any true subfield of This implies that the security of G does depend on the F,(w) but not on 6,. It is also based on the mathematically unproven assumption pointed out by Schnorr [2] that there have been no known polynonlial-time algorithms for the DL problem on a cyclic subgroup of a large prime order dividing q + 1 in &(a)". cl. Table 1: Exponentiation in finite fields JXw) FP, I I Exponentiation by 160 bit exponenl 49 ms 82 ins Signed binary method and conclusion: We deal with fast exponentiation on the proposed group G of order Z generated by g. Since Z is of size 2'" one needs to efficiently perform g" for a given integer k of size nearly equal to that of I. To use a signed binary method which mainly applies to elliptic scalar multiplication, we note by Lemma 2 that the inverse of any element a = xu + y d in G is easily determined by swapping the components x and 4'.This observation enables us to use a signed binary expansion for an integral exponent k to yield a running time improvcment of up to 15% compared with h e ordinary binary method. Together with a conventional basis, exponentiation on G can be carried out efficiently by as much as 40% as the usual exponentiation is performed in the large prime field, as shown in Table I , where we compare 160 bit exponentiations of each elenient in F,,(w) and Fp2 where p 1 and p2 are a 51 2 hit prime and a 1024 hit prune, respectively, and w is a root of a quadratic irreducible polynomial X + X + I over Fp,. The implementation of arithmetic operations in the above two fields was carried out using NTL 4.0 [6]. Our program was compiled with Visual C 5.0 and the running time was checked on a Pentium I11 650 MHz. LEXSIKA, A.K., and VEKHEUL. E.K.: 'The XTR public key system'. Crypto 2000, 2000, pp. 1-19 BLAKE, I., S ~ K O U S S I , e, and SMART, N.: 'Elliptic curves in cryptography' (London Mathematical Society, Lecture Note Series 265) SHOUP, v.: 'NTL www.shoup.net 4.0' for number theory, available at 7.35 GHz PLL frequency synthesiser in 0.8pm silicon bipolar production technology G. Ritzberger, J. Bock, H. Knapp, M. Rest, L. Treitinger and A.L. Scholtz A 7.35 GHr phase-lockcd loop frequency syiithcsiser in a low-cost 0.8 pm/25 GHz silicon bipolar production technology (B6HF) is prcsented. The synthesiser oflers a tuning range from 7.23 Lo 7.3SGHz at the supply voltage of 3V, and phase-noise perfomiance of -100.7dBciHz at 100kHz offset from the cai~iei-. hirodtiction: The demand for low-cost wireless applications will increase rapidly within the next few years. High volume products, e.g. applicalioiis for wireless local loops (WLLs) at 3.5 GHz, wireless local arca networks (WLANs) such as HIPERLAN at 5.2 GHz, U-NTT applications at 5.8 GHz, and satellite coinmunications at 8 and l0GHz are strongly dcpcndent on thc availability of low-cost integrated circuits. Integrated frequency synlhesisers in phase-locked loop (PLLj architecture are key components in all wireless systems. During recent years highly-integrated PLL-synthesisers with output frequencies up to 5.2GHz have been published in CMOS [l], Si bipolar [2, 31, Si BiCMOS [4], and SiGe BiCMOS [5] technologies. This Letter presents a highly-integrated 7.35 GHz frequency synthesiser in PLL architecturc, fabricated in a low-cost 0.8 pi Si bipolar production technology. To our knowlcdge, thc output frequency of 7.35 GHz is the highest reported for highly-integrated silicon-based frequency synthcsisers with on-chip voltage-controlled oscillators. Seiniconductor technology: The frequency synthesiser was fabricated in Infineons BbHF Si bipolar production technology [6]. This 0.8 pn double-polysilicon technology uses simple LOCOS isolation, and features npn transistors with IT = 25 GHz, latcral pnp transistors, three types of poly-Si resistors, linear MOS capacitors, ESD structures, and three metallisation layers. ,- - -----. __--___-_-_-. Acknowlr&nzent: This work is supported in part by the Ministry of Information and Communication of Korea ('Support Project of University Information Technology Research Center' supervised by IITAj and the Brain Korea 21 Project. 0 IEE 2001 Electronics Lettevs Online No: 20010654 D o l : 10.1049/r.I:2OO10654 Sangtae Jeoiig (Depurtment uf 27 Decemhrv 21100 Mutlremutics, Seoul Nuliouul C'niver.Pily, Seoul, Koreu) E-mail: stj@math.snu.ac.kr Young-Ho Park and Sangho Oh (Cenlrr for InJurination Security Ter:biiologies, Korea L'nive,:sity, B- 136, Gvuduure School Riotechnolog~:Blrig., 5Ga, Auam, Sunghuk, Seoul, 136-701, Korcw) oj' References ELGAMAL, T.: 'A public key cryptosystcm and a signature scheme based on discrete logarithms', IEEE Tvuns. I f : T/icory, 1985, 31. (4), pp. 469-472 2 SCHNURK, c.P.: 'Efficient signature generation by sinart cards', .I. Crjprol., 1991, 4,pp. 161-174 . 'Using cyclotomic polynomials to construct efficient 3 L ~ N S T K AA.K.: discrete logarithm cryptosystenis over finite Gelds'. Proc. ACISP97, LNCS 1270, Springer-Verlag, 1997, pp. 127-138 1 ELECTRONICS LETTERS 19th J u l y 2001 Circuit de3ip7: The PLL consists of a voltage-controlled oscillator (VCO). a divide-by-32 circuit, and an EXOR phase detector (PDj. There is only onc external block, the loop filter. Thus single-loop (see Fig. I ) and multiloop concepts can easily hc realiscd [2, 71. All building blocks were designed in fully differential logic. The voltage-controlled oscillator consists of a cross-coupled differential amplifier with a resonant LC circuit acting as load. Emitter followers in the feedback path help to reduce the loading of the resonant circuits by the input of the differential amplifier and help to achicve a high-loaded Q of the rcsonator. On-chip spiral inductors with inductances of 1.2nH and varactors build the resonant cir- Vol. 37 No. 15 955

1/--страниц