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

EXACT SOLUTION OF SYSTEMS OF LINEAR-EQUATIONS WITH ITERATIVE METHODS

SIAM JOURNAL ON algebraic AND DISCRETE METHODS 1983年第1期4卷 111-115页

作者： URSIC, S PATARRA, C UNIV SAO PAULO DEPT MATHSAO PAULOSPBRAZIL

An algorithm is presented to compute the exact solution of a system of linear equations with integer coefficients from any method capable of providing a sufficiently accurate approximate solution.

关键词： algebraic algorithms continued fractions rational rounding

来源：评论

学校读者我要写书评

暂无评论

Quasi-optimal multiplication of linear differential operators

Quasi-optimal multiplication of linear differential operator...

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Benoit, Alexandre Bostan, Alin van der Hoeven, Joris UPMC Paris France INRIA France Paris France CNRS Ecole Polytech Paris France

We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.

ISBN: (纸本)9781467343831

关键词： Linear differential operators multiplication algebraic algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

Separation results on the "One-More" computational problems 1

引用

Cryptographers Track held at the RSA Conference (CT-RSA)

作者： Bresson, Emmanuel Monnerat, Jean Vergnaud, Damien DCSSI Crypto Lab Paris France Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Ecole Normale Sup erieure CNRS INRIA Rue d'Ulm 75005 France

ISBN: (数字)9783540792635

ISBN: (纸本)9783540792628

In 2001, Bellare, Namprempre, Pointcheval and Semanko introduced the notion of "one-more" computational problems. Since their introduction, these problems have found numerous applications in cryptography. For instance, Bellare et al. showed how they lead to a proof of security for Chaum's RSA-based blind signature scheme in the random oracle model. In this paper, we provide separation results for the computational hierarchy of a large class of algebraic "one-more" computational problems (e.g. the one-more discrete logarithm problem, the one-more RSA problem and the one-more static Computational Diffie-Hellman problem in a bilinear setting). We also give some cryptographic implications of these results and, in particular, we prove that it is very unlikely, that one will ever be able to prove the unforgeability of Chaum's RSA-based blind signature scheme under the sole RSA assumption.

关键词： "one-more" problems black-box reductions random self-reducible problems algebraic algorithms

来源：评论

学校读者我要写书评

暂无评论

The algebraic Group Model and its Applications 38th

The Algebraic Group Model and its Applications

引用

38th Annual International Cryptology Conference (CRYPTO)

作者： Fuchsbauer, Georg Kiltz, Eike Loss, Julian ENS CNRS PSL INRIA Paris France Ruhr Univ Bochum Bochum Germany

ISBN: (纸本)9783319968810;9783319968803

One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group. To overcome this limitation, we propose the algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth's zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM. Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.

关键词： algebraic algorithms Generic group model Security reductions Cryptographic assumptions

来源：评论

学校读者我要写书评

暂无评论

Patching Colors with Tensors 27

Patching Colors with Tensors

引用

27th Annual European Symposium on algorithms (ESA)

作者： Brand, Cornelius Saarland Univ MMCI Saarland Informat Campus Saarbrucken Germany

ISBN: (纸本)9783959771245

We describe a generic way of exponentially speeding up algorithms which rely on Color-Coding by using the recently introduced technique of Extensor-Coding (Brand, Dell and Husfeldt, STOC 2018). To demonstrate the usefulness of this "patching" of Color-Coding algorithms, we apply it ad hoc to the exponential-space algorithms given in Gutin et al. (Journal Comp. Sys. Sci. 2018) and obtain the fastest known deterministic algorithms for, among others, the k-internal out-branching and k-internal spanning tree problems. To realize these technical advances, we make qualitative progress in a special case of the detection of multilinear monomials in multivariate polynomials: We give the first deterministic fixed-parameter tractable algorithm for the k-multilinear detection problem on a class of arithmetic circuits that may involve cancellations, as long as the computed polynomial is promised to satisfy a certain natural condition. Furthermore, we explore the limitations of using this very approach to speed up algorithms by determining exactly the dimension of a crucial subalgebra of extensors that arises naturally in the instantiation of the technique: It is equal to F2k+1, the kth odd term in the Fibonacci sequence. To determine this dimension, we use tools from the theory of Grobner bases, and the studied algebraic object may be of independent interest. We note that the asymptotic bound of F2k+1 approximate to phi(2k) = O(2.619(k)) curiously coincides with the running time bound on one of the fastest algorithms for the k-path problem based on representative sets due to Fomin et al. (JACM 2016). Here, phi is the golden ratio.

关键词： Color-Coding Extensor-Coding internal out-branching colorful problems algebraic algorithms multilinear detection deterministic algorithms exterior algebra

来源：评论

学校读者我要写书评

暂无评论

Power Series Composition in Near-Linear Time 65

Power Series Composition in Near-Linear Time

引用

65th Symposium on Foundations of Computer Science

作者： Kinoshita, Yasunori Li, Baitian Tokyo Inst Technol Tokyo Japan Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing Peoples R China

ISBN: (纸本)9798331516758;9798331516741

We present an algebraic algorithm that computes the composition of two power series in softly linear time complexity. The previous best algorithms are O(n(1+o(1))) non-algebraic algorithm by Kedlaya and Umans (FOCS 2008) and an O(n(1.43)) algebraic algorithm by Neiger, Salvy, Schost and Villard (JACM 2023). Our algorithm builds upon the recent Graeffe iteration approach to manipulate rational power series introduced by Bostan and Mori (SOSA 2021).

关键词： algebraic algorithms computations on polynomials

来源：评论

学校读者我要写书评

暂无评论

A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence 4

A Simple and Fast Algorithm for Computing the <i>N</i>-th Te...

引用

Symposium on Simplicity in algorithms (SOSA)

作者： Bostan, Alin Mori, Ryuhei INRIA Palaiseau France Tokyo Inst Technol Tokyo Japan

ISBN: (纸本)9781611976496

We present a simple and fast algorithm for computing the N-th term of a given linearly recurrent sequence. Our new algorithm uses O(M(d) logN) arithmetic operations, where d is the order of the recurrence, and M(d) denotes the number of arithmetic operations for computing the product of two polynomials of degree d. The state-of-the-art algorithm, due to Fiduccia (1985), has the same arithmetic complexity up to a constant factor. Our algorithm is simpler, faster and obtained by a totally different method. We also discuss several algorithmic applications, notably to polynomial modular exponentiation and powering of matrices.

关键词： algebraic algorithms Computational Complexity Linearly Recurrent Sequence Rational Power Series Fast Fourier Transform

来源：评论

学校读者我要写书评

暂无评论

Beating binary powering for polynomial matrices 23

Beating binary powering for polynomial matrices

引用

48th International Symposium on Symbolic and algebraic Computation (ISSAC)

作者： Bostan, Alin Neiger, Vincent Yurkevich, Sergey Inria Palaiseau France Sorbonne Univ CNRS LIP6 F-75005 Paris France Univ Vienna Vienna Austria Inria Saclay Palaiseau France

ISBN: (纸本)9798400700392

The Nth power of a polynomial matrix of fixed size and degree can be computed by binary powering as fast as multiplying two polynomials of linear degree in N. When Fast Fourier Transform (FFT) is available, the resulting complexity is softly linear in N, i.e. linear in N with extra logarithmic factors. We show that it is possible to beat binary powering, by an algorithm whose complexity is purely linear in N, even in absence of FFT. The key result making this improvement possible is that the entries of the.. th power of a polynomial matrix satisfy linear differential equations with polynomial coefficients whose orders and degrees are independent of N. Similar algorithms are proposed for two related problems: computing the N th term of a C-finite sequence of polynomials, and modular exponentiation to the power N for bivariate polynomials.

关键词： algebraic algorithms Computational Complexity FFT Binary Powering C-finite Sequence Rational Power Series Linear Differential Equations Creative Telescoping Polynomial Matrices

来源：评论

学校读者我要写书评

暂无评论

Enhancement of digital images for extracting geometrical features of material grains in nanoscale materials research

Enhancement of digital images for extracting geometrical fea...

引用

37th Southeastern Symposium on System Theory (SSST05)

作者： Sun, M Univ Alabama Dept Math Tuscaloosa AL 35487 USA

ISBN: (纸本)0780388089

This article addresses the issue of extracting geometrical features of material grains from raw digital images obtained by commercial microscopes used in nanoscale materials research. algebraic numerical procedures are developed to estimate geometrical quantities such as grain size distribution, shape orientation, and shape irregularity after a sequence of preprocessing steps applied to raw images. Testing results on a real image are presented following the description of the algorithms.

关键词： image processing geometrical features algebraic algorithms

来源：评论

学校读者我要写书评

暂无评论

Algoritmos algebricos para enumerar e isolar zeros polinomiais complexos

Algoritmos algebricos para enumerar e isolar zeros polinomia...

引用

作者： Camargo-Brunetto, Maria Angelica de Oliveira

In this thesis, the problem of isolating polynomial complex zeros is treated. There are many algorithms to calculate polynomial zeros, having previously isolated regions, each containning only one zero. Despite of this, the problem of obtainning such regions is still unsatisfactory. This problem, called root isolation, requires number of root in a given region of the complex plane. algorithms to enumerate and isolate complex polynomial roots are analised, developed and implemented. A modified Wilf method is given, in with Sturm Sequences and the principle of argument is used. An algebraic approach is given, with the aim to enumerate zeros inside a rectangle in an exact way. Several improvements are introduced, mainly to treat zeros on the boundary of the rectangle. The performance of this new algorithm is evaluated theoretical as well as practice point of view, by means experimental tests. The robustness of the algorithm is verified by means of tests with ill-conditioned polynomials. The algorithm proposed is compared with a recent paper, presenting the performance of both, according different polynomial classes. ...

关键词： Análise numérica Polynomial zeros Zeros : Polinomios Sturm sequences algebraic algorithms Algoritmos algebricos Sequencias : Sturm Tese

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：