вход по аккаунту



код для вставкиСкачать
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)
V. Cuerra (Group of Nunzericrrl Methods. Institute of Math,
Cj,hernetics and Physim, Havanu, Cuhu)
+ z/u
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)=
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,
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
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
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)
From this one can deduce the inverse of a = x
easily given by the formula a = (x ay) yw.
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
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
( 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].
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)".
Table 1: Exponentiation in finite fields
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
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
27 Decemhrv 21100
Mutlremutics, Seoul Nuliouul C'niver.Pily,
Seoul, Koreu)
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)
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
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
Без категории
Размер файла
279 Кб
Пожаловаться на содержимое документа