A simple efficient method for computing modular multiplicative inverse is presented. This approach has the advantage that the backward substitutions commonly adopted for the Extended Euclidean ...Algorithm (EEA) can be avoided. The modular multiplicative inverse can be computed effectively by the successive quotients obtained in the Euclidean Algorithm (EA). Some illustrative examples are provided.
The rigidity degree of a generator-cogenerator determines the dominant dimension of its endomorphism algebra, and is closely related to a recently introduced homological dimension — rigidity ...dimension. In this paper, we give explicit formulae for the rigidity degrees of all indecomposable modules over representation-finite self-injective algebras by developing combinatorial methods from the Euclidean algorithm. As an application, the rigidity dimensions of some algebras of types A and E are given.
Cloud computing gives resource-constrained clients great conveniences to outsource exorbitant computations to a public cloud. The extended Euclidean algorithm with large-scale polynomials over finite ...fields is fundamental and widespread in computer science and cryptography, yet it is computationally overloaded for quantities of lightweight devices emerged with the dawn of internet of things (IoT). In this respect, we design an efficient outsourcing algorithm that enables a lightweight client to achieve this heavy computation with the assistance of a remote cloud server. By comprehensively employing the variable substitution, random polynomial-based blind technique and unimodular matrix transformation, our algorithm achieves the goals of cheating resistance, privacy preservation, and high efficiency. Concretely, our algorithm is based on single untrusted program model which avoids the too strong security assumption between multiple servers, and it enables the client to detect the cloud’s misbehaviors with (optimal) probability 1. Also, Thorough theoretical analysis indicates that the algorithm provides robust input/output privacy. Moreover, the algorithm only needs one round interaction between the client and the cloud. Strict theoretical analysis and extensive experimental evaluations demonstrate our algorithm’s practical efficiency and effectiveness. Finally, an important application of our algorithm on securely outsourcing the expensive key generation step of NTRU cryptosystem is given.
Borrowing inspiration from Marcone and Montálban's one-one correspondence between the class of signed trees and the equimorphism classes of indecomposable scattered linear orders, we find a subclass ...of signed trees which has an analogous correspondence with equimorphism classes of indecomposable finite rank discrete linear orders.
We also introduce the class of finitely presented linear orders–the smallest subclass of finite rank linear orders containing 1, ω and ω⁎ and closed under finite sums and lexicographic products. For this class we develop a generalization of the Euclidean algorithm where the width of a linear order plays the role of the Euclidean norm. Using this as a tool we classify the isomorphism classes of finitely presented linear orders in terms of an equivalence relation on their presentations using 3-signed trees.
Whilst Paul de Casteljau is now famous for his fundamental algorithm of curve and surface approximation, little is known about his other findings. This article offers an insight into his results in ...geometry, algebra and number theory.
Related to geometry, his classical algorithm is reviewed as an index reduction of a polar form. This idea is used to show de Casteljau's algebraic way of smoothing, which long went unnoticed. We will also see an analytic polar form and its use in finding the intersection of two curves. The article summarises unpublished material on metric geometry. It includes theoretical advances, e.g., the 14-point strophoid or a way to link Apollonian circles with confocal conics, and also practical applications such as a recurrence for conjugate mirrors in geometric optics. A view on regular polygons leads to an approximation of their diagonals by golden matrices, a generalisation of the golden ratio.
Relevant algebraic findings include matrix quaternions (and anti-quaternions) and their link with Lorentz' equations. De Casteljau generalised the Euclidean algorithm and developed an automated method for approximating the roots of a class of polynomial equations. His contributions to number theory not only include aspects on the sum of four squares as in quaternions, but also a view on a particular sum of three cubes. After a review of a complete quadrilateral in a heptagon and its angles, the paper concludes with a summary of de Casteljau's key achievements.
The article contains a comprehensive bibliography of de Casteljau's works, including previously unpublished material.
•Insight into de Casteljau's contributions to geometry, algebra, and number theory.•Algebraic smoothing with polar forms using Aitken, de Boor, de Casteljau.•Metric geometry advances: 14-point strophoid, geometric optics, regular polygon approximation.•Algebraic findings: matrix quaternions and a generalised Euclidean algorithm.•Summary of his mathematical œuvre, including a comprehensive bibliography.
A simple approach for solving the linear Diophantine equation via the Euclidean Algorithm (EA) is presented. Unlike the common approach for applying the Extended Euclidean Algorithm (EEA), we present ...a top-down approach for finding the unknowns by the sequence of quotients obtained by successive divisions. Some illustrative examples are provided.
We introduce a generalization of the Euclidean algorithm for rings equipped with an involution, and completely enumerate all isomorphism classes of orders over definite, rational quaternion algebras ...equipped with an orthogonal involution that admit such an algorithm. We give two applications: first, any order that admits such an algorithm has class number 1; second, we show how the existence of such an algorithm relates to the problem of constructing explicit Dirichlet domains for Kleinian subgroups of the isometry group of hyperbolic 4-space.
This paper introduces the partial-inverse problem for linearized polynomials and develops its application to decoding Gabidulin codes and lifted Gabidulin codes in linear random network coding. The ...proposed approach is a natural generalization of its counterpart for ordinary polynomials, thus providing a unified perspective on Reed-Solomon codes for the Hamming metric and for the rank metric. The basic algorithm for solving the partial-inverse problem is a common parent algorithm of a Berlekamp-Massey algorithm, a Euclidean algorithm, and yet another algorithm, all of which are obtained as easy variations of the basic algorithm. Decoding Gabidulin codes can be reduced to the partial-inverse problem via a key equation with a new converse. This paper also develops new algorithms for interpolating crisscross erasures and for joint decoding of errors, erasures, and deviations in random network coding.
"The book provides an introduction to modern abstract algebra and its applications. It covers all major topics of classical theory of numbers, groups, rings, fields and finite dimensional algebras. ...The book also provides interesting and important modern applications in such subjects as Cryptography, Coding Theory, Computer Science and Physics. In particular, it considers algorithm RSA, secret sharing algorithms, Diffie-Hellman Scheme and ElGamal cryptosystem based on discrete logarithm problem. It also presents Buchbergers algorithm which is one of the important algorithms for constructing Gröbner basis. Key Features: Covers all major topics of classical theory of modern abstract algebra such as groups, rings and fields and their applications. In addition it provides the introduction to the number theory, theory of finite fields, finite dimensional algebras and their applications. Provides interesting and important modern applications in such subjects as Cryptography, Coding Theory, Computer Science and Physics. Presents numerous examples illustrating the theory and applications. It is also filled with a number of exercises of various difficulty.
Describes in detail the construction of the Cayley-Dickson construction for finite dimensional algebras, in particular, algebras of quaternions and octonions and gives their applications in the number theory and computer graphics."
PDF
