检索结果-内蒙古大学图书馆

Small quotients in euclidean algorithms

RAMANUJAN JOURNAL 2011年第2期24卷 183-218页

作者： Cesaratto, Eda Vallee, Brigitte Univ Gen Sarmiento CONICET RA-1613 Buenos Aires DF Argentina Univ Gen Sarmiento Inst Desarrollo Humano RA-1613 Buenos Aires DF Argentina Univ Caen CNRS UMR 6072 GREYC F-14032 Caen France

Numbers whose continued fraction expansion contains only small digits have been extensively studied. In the real case, the Hausdorff dimension sigma (M) of the reals with digits in their continued fraction expansion bounded by M was considered, and estimates of sigma (M) for M -> a were provided by Hensley (J. Number Theory 40:336-358, 1992). In the rational case, first studies by Cusick (Mathematika 24:166-172, 1997), Hensley (In: Proc. Int. Conference on Number Theory, Quebec, pp. 371-385, 1987) and Vall,e (J. Number Theory 72:183-235, 1998) considered the case of a fixed bound M when the denominator N tends to a. Later, Hensley (Pac. J. Math. 151(2):237-255, 1991) dealt with the case of a bound M which may depend on the denominator N, and obtained a precise estimate on the cardinality of rational numbers of denominator less than N whose digits (in the continued fraction expansion) are less than M(N), provided the bound M(N) is large enough with respect to N. This paper improves this last result of Hensley towards four directions. First, it considers various continued fraction expansions;second, it deals with various probability settings (and not only the uniform probability);third, it studies the case of all possible sequences M(N), with the only restriction that M(N) is at least equal to a given constant M (0);fourth, it refines the estimates due to Hensley, in the cases that are studied by Hensley. This paper also generalises previous estimates due to Hensley (J. Number Theory 40:336-358, 1992) about the Hausdorff dimension sigma (M) to the case of other continued fraction expansions. The method used in the paper combines techniques from analytic combinatorics and dynamical systems and it is an instance of the Dynamical Analysis paradigm introduced by Vall,e (J. Th,or. Nr. Bordx. 12:531-570, 2000), and refined by Baladi and Vall,e (J. Number Theory 110:331-386, 2005).

关键词： Continued fractions Hausdorff dimension Maps of the interval euclidean algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on "euclidean algorithms are Gaussian" by V. Baladi and B. Vallee

引用

JOURNAL OF NUMBER THEORY 2009年第10期129卷 2267-2273页

作者： Cesaratto, E. Univ Nac Gral Sarmiento Inst Desarrollo Humano RA-1613 Los Polvorines Pcia Buenos Air Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina

The paper "euclidean algorithms are Gaussian" [V. Baladi, B. Vallee, euclidean algorithm are Gaussian, J. Number Theory 110 (2005) 331-386], is devoted to the distributional analysis of three variants of euclidean algorithms. The Central Limit Theorem and the Local Limit Theorem obtained there are the first ones in the context of the "dynamical analysis" method. The techniques developed have been applied in further various works (e.g. [V. Baladi, A. Hachemi, A local limit theorem with speed of convergence for euclidean algorithms and Diophantine costs, Ann. Inst. H. Poincare Probab. Statist. 44 (2008) 749-770;E. Cesaratto, J. Clement, B. Daireaux, L Lhote, V. Maume, B. Vallee, Analysis of fast versions of the Euclid algorithm, in: Proceedings of Third Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08, SIAM, 2008;E. Cesaratto. A. Plagne, B. Vallee, On the non-randomness of modular arithmetic progressions, in: Fourth Colloquium on Mathematics and Computer Science. algorithms, Trees, Combinatorics and Probabilities, in: Discrete Math. Theor. Comput. Sci. Proc., vol. AG, 2006, pp. 271-288]). These theorems are proved first for an auxiliary probabilistic model, called "the smoothed model," and after, the estimates are transferred to the "true" probabilistic model. In this note, we remark that "the smoothed model" described in [V. Baladi, B. Vallee, euclidean algorithm are Gaussian, J. Number Theory 110 (2005) 331-386] is not adapted to this transfer and replaces it by an adapted one. However, the results remain unchanged. (c) 2009 Elsevier Inc. All rights reserved.

关键词： Distributional analysis euclidean algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamical analysis of a class of euclidean algorithms

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期297卷 447-486页

作者： Vallée, B Univ Caen GREYC F-14032 Caen France

We develop a general framework for the analysis of algorithms of a broad euclidean type. The average-case complexity of an algorithm is seen to be related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithm. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory. As a consequence, we obtain precise average-case analyses of algorithms for evaluating the Jacobi symbol of computational number theory fame, thereby solving conjectures of Bach and Shallit. These methods also provide a unifying framework for the analysis of an entire class of gcd-like algorithms together with new results regarding the probable behaviour of their cost functions. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： analysis of algorithms average-case complexity euclidean algorithms dynamical systems transfer operators functional analysis

来源：评论

学校读者我要写书评

暂无评论

Dynamical analysis of a class of euclidean algorithms

Dynamical analysis of a class of Euclidean algorithms

引用

4th Latin American Theoretical Informatics International Conference (LATIN 2000)

作者： Vallée, B Univ Caen GREYC F-14032 Caen France

关键词： analysis of algorithms average-case complexity euclidean algorithms dynamical systems transfer operators functional analysis

来源：评论

学校读者我要写书评

暂无评论

Asymptotic behaviour of the first moment of the number of steps in the by-excess and by-deficiency euclidean algorithms

引用

SBORNIK MATHEMATICS 2012年第2期203卷 288-305页

作者： Frolenkov, D. A. Moscow MV Lomonosov State Univ Moscow Russia

The first moments for the number of steps in different euclidean algorithms are considered. For these moments asymptotic formulae with new remainder terms are obtained using refined estimates for sums of fractional pa... 详细信息

关键词： euclidean algorithms continued fractions fractional parts prime number theorem

来源：评论

学校读者我要写书评

暂无评论

A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs

引用

ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES 2008年第4期44卷 749-770页

作者： Baladi, Viviane Hachemi, Aicha Inst Math Jussieu CNRS UMR 7586 Paris France

For large N, we consider the ordinary continued fraction of x = p/q with 1 infinity. If c is nonlattice and satisfies mild growth conditions, the local limit theorem was proved previously by the second named author. ... 详细信息

For large N, we consider the ordinary continued fraction of x = p/q with 1 <= p <= q <= N, or, equivalently, Euclid's gcd algorithm for two integers 1 <= p <= q <= N, putting the uniform distribution on the set of p and qs. We study the distribution of the total cost of execution of the algorithm for all additive cost function c oil the set Z(+)* of possible digits, asymptotically for N -> infinity. If c is nonlattice and satisfies mild growth conditions, the local limit theorem was proved previously by the second named author. Introducing diophantine conditions oil the cost, we are able to control the speed of convergence in the local limit theorem. We use previous estimates of the first author and Vallee, and we adapt to our setting bounds of Dolgopyat and Melbourne on transfer operators. Our diophantine condition is generic (with respect to Lebesgue measure). For smooth enough observables (depending on the diophantine condition) we attain the optimal speed.

关键词： euclidean algorithms local limit theorem diophantine condition speed of convergence transfer operator continued fraction

来源：评论

学校读者我要写书评

暂无评论

Computing in Cryptography 3

Computing in Cryptography

引用

3rd International Conference on Computing for Sustainable Global Development (INDIACom)

作者： Hassan, Shabbir Bokhari, Mohammad Ubaidullah Aligarh Muslim Univ Dept Comp Sci Aligarh UP India

ISBN: (纸本)9789380544199

Nowadays fast computing and lightweight cryptography play a crucial role in the field of cryptography. Whenever we concern about the cryptography, the aspect of discrete mathematics can't be omitted. Security in cryptography is completely depends upon the key and the computations. Generation of key is nothing but the implementation of graph theory, discrete logarithms,linear &abstract algebra etc. These branches of modern mathematics has been playing a great role for the implementation of algorithms such as elliptic curve cryptography, stream cipher, block cipher, wireless sensor network etc. This paper is written to literally represent the key concept of such branches of modern mathematics and their implementations in the field of cryptograph. This paper mainly deals the applications of Galois Field, primitive polynomials, primitive polynomials over Galois Field, Number theoretic functions, Congruence Calculus or modular arithmetic's, Residue Class Rings and Prime Fields. The paper focus on these key topics to developa mathematical tool, that are needed for the design and security analysis of a cryptosystems.

关键词： Galois Field Modular Arithmetic Discrete logarithm Euler Totient Function Primitive Polynomial Primitive roots euclidean algorithms Mobius Function

来源：评论

学校读者我要写书评

暂无评论

A VLSI implementation of a low complexity Reed-Solomon encoder and decoder for CDPD

A VLSI implementation of a low complexity Reed-Solomon encod...

引用

4th International Conference on ASIC

作者： Ge, Q Mao, JF Rong, MT Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200030 Peoples R China

ISBN: (纸本)0780366778

This paper presents VLSI implementation of an area efficient 8-error correcting (63,47) Reed-Solomon(RS) encoder and decoder for the CDPD (Cellular Digital Packet Data)communication systems[1]. We implement this RS decoder using euclidean algorithms which is regular, simple and naturally suitable for VLSI implementation. Constant multipliers based on certain composite field are deployed in the encoder, which significantly decreases the encoder's area. Multipliers over certain composite field GF((2(n))(2)) adopted in this paper lowers the complexity of the multiplication of the decoder. The RS encoder and decoder can independently operates at a clock frequency of 30 MHz. This chip was fabricated in 0.6mum CMOS 1P2M technology with a supply of voltage of 5v, with die area 4mm x 4mm. The chip has been fully tested and stratifies the demand of the CDPD communication systems.

关键词： VLSI Reed-Solomon codes decoding cellular radio digital radio packet radio networks CMOS digital integrated circuits codecs VLSI implementation low complexity Reed-Solomon encoder Reed-Solomon decoder cellular digital packet data communication euclidean algorithms constant multipliers composite field complexity clock frequency CMOS IP2M technology die area CDPD 30 MHz 0.6 micron 5 V

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：