Search

The Extended Hensel Construction (EHC) is a procedure which, for an input bivariate polynomial with complex coefficients, can serve the same purpose as the Newton-Puiseux algorithm, and, for the multivariate case, can be seen as an effective variant of Jung-Abhyankar Theorem. We show that the EHC requires only linear algebra and univariate polynomial arithmetic. We deduce complexity estimates and report on a software implementation together with experimental results. This work is motivated and illustrated by two applications. The first one is the computation of real branches of space curves. The second one is the computation of limits of real multivariate rational function. For the latter, we present an algorithm for determining the existence of the limit of a real multivariate rational function q at a given point p which is an isolated zero of the denominator of q. When the limit exists, the algorithm computes it, without making any assumption on the number of variables. A process, which extends the work of Cadavid, Molina and Velez, reduces the multivariate setting to computing limits of bivariate rational functions. By using regular chain theory and triangular decomposition of semi-algebraic systems, we avoid the computation of singular loci and the decomposition of algebraic sets into irreducible components.

This paper develops an approach for point addition and doubling on elliptic curves over finite fields using one variable polynomial arithmetic based on Euclidean division. This approach suc...

Nichtlineare Polynome ��ber endliche K��rper haben zahlreiche Anwendungen in der Kryptographie, da sie schwer zu l��sen sind. In dieser Arbeit befassen wir uns mit diesem Problem und pr��sentieren eine automatische Entscheidungsprozedur f��r die Erf��llbarkeit von Systemen nichtlinearer Polynome ��ber endliche K��rper. Unser Ansatz besteht aus einer Conflict-Driven Clause Learning (CDCL) Suchprozedur die bereits erfolgreich f��r Systeme nichtlinearer Polynome ��ber die reellen Zahlen verwendet wurde. Wir zeigen, dass eine solche Prozedur auch f��r Systeme von Polynomen ��ber endliche K��rper verwendet werden kann. Neben der Suchprozedur selbst pr��sentieren wir zwei verschiedene Ans��tze zum Verarbeiten der Polynome basierend auf der Eliminationstheorie und Gr��bnerbasen. Wir vergleichen unseren Ansatz mit aktuellen L��sungsverfahren und beurteilen unsere Ergebnisse., Non-linear polynomial systems over finite fields are widely found in cryptography, as they are known to be hard to solve. In this thesis, we address this challenge and propose an automated reasoning procedure for deciding the satisfiability of a system on non-linear equations over finite fields. Our approach performs a Conflict-Driven Clause Learning (CDCL) style search, which has been successfully applied to deciding satisfiability of non-linear arithmetic constraints in the past. We show that CDCL can be utilized for the problem of solving non-linear polynomial systems and present the search procedure as well as two different theory solving back-end approaches utilizing elimination theory as well as Gr��bner bases. In addition, we are comparing our approach to state-of-the-art procedures and give an evaluation of the results.

Lattice-based cryptography forms the mathematical basis for current homomorphic encryption schemes, which allows computation directly on encrypted data. Homomorphic encryption enables privacy-preserving applications such as secure cloud computing; yet, its practical applications suffer from the high computational complexity of homomorphic operations. Fast implementations of the homomorphic encryption schemes heavily depend on efficient polynomial arithmetic, multiplication of very large degree polynomials over polynomial rings, in particular. Number theoretic transform (NTT) accelerates large polynomial multiplication significantly, and therefore, it is the core arithmetic operation in the majority of homomorphic encryption scheme implementations. Therefore, practical homomorphic applications require efficient and fast implementations of NTT in different computing platforms. In this work, we present an efficient and fast implementation of NTT, inverse NTT and NTT-based polynomial multiplication operations for GPU platforms. To demonstrate that our GPU implementation can be utilized as an actual accelerator, we experimented with the key generation, the encryption and the decryption operations of the Brakerski/Fan–Vercauteren (BFV) homomorphic encryption scheme implemented in Microsoft’s SEAL homomorphic encryption library on GPU, all of which heavily depend on the NTT-based polynomial multiplication. Our GPU implementations improve the performance of these three BFV operations by up to 141.95 $$\times$$ , 105.17 $$\times$$ and 90.13 $$\times$$ , respectively, on Tesla v100 GPU compared to the highly optimized SEAL library running on an Intel i9-7900X CPU.

Limited precision floating point computer implementations of large polynomial arithmetic expressions are nonlinear and dissipative. They are not reversible (irreversible, lack conservation), lose information, and so are robust to perturbations (anti-fragile) and resilient to fluctuations. This gives a largely stable locally flat evolutionary neutral fitness search landscape. Thus even with a large number of test cases, both large and small changes deep within software typically have no effect and are invisible externally. Shallow mutations are easier to detect but their RMS error need not be simple.

International audience; Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp-Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence.Several algorithms solve this problem. The so-called Berlekamp-Massey-Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process.We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp-Massey-Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations.A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial.As an addition from the paper published at the ISSAC conferance, we give an adaptive variant of this algorithm taking into account the shape of the final Gröbner basis gradually as it is discovered. The main advantage of this algorithm is that its complexity in terms of operations and sequence queries only depends on the output Gröbner basis.All these algorithms have been implemented in Maple and we report on our comparisons.

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and expected to remain secure in the upcoming era of quantum computing. Furthermore, NTRUEncrypt offers some efficiency benefits over “pre-quantum” cryptosystems like RSA or ECC since the low-level arithmetic operations are less computation-intensive and, thus, more suitable for constrained devices. In this paper we present AVR N TRU, a highly-optimized implementation of NTRUEncrypt for 8-bit AVR microcontrollers that we developed from scratch to reach high performance and resistance to timing attacks. AVR N TRU complies with the EESS #1 v3.1 specification and supports product-form parameter sets such as ees443ep1, ees587ep1, and ees743ep1. An entire encryption (including mask generation and blinding-polynomial generation) using the ees443ep1 parameters requires 847973 clock cycles on an ATmega1281 microcontroller; the decryption is more costly and has an execution time of 1051871 cycles. We achieved these results with the help of a novel hybrid technique for multiplication in a truncated polynomial ring, whereby one of the operands is a sparse ternary polynomial in product form and the other an arbitrary element of the ring. A constant-time multiplication in the ring given by the ees443ep1 parameters takes only 192577 cycles, which sets a new speed record for the arithmetic part of a lattice-based cryptosystem on AVR.

The research work proposes a framework for checking the correctness of Galois field arithmetic operations in digital circuits. The authors propose to automatically generate the test cases from the user input, avoiding reliance upon predesigned test cases, comprising Galois field-width and respective choice of irreducible polynomial. We do this through the use of polynomial arithmetic to verify the circuits. To the best of author's knowledge, though extensive work has been carried out in optimising the performance of arithmetic operations in Galois field, there exist no testbench to evaluate the efficacy of hardware circuits incorporating this concept. By automating the process of generating test cases, the work can be scaled to test circuits of arbitrarily large field widths, thus providing a flexible architecture that guarantees correctness of the underlying design under test. We present simulation results for Galois field polynomials of width $\mathbf{GF}(2^{2})$ ), $\mathbf{GF}(2^{4})$ and $\mathbf{GF}(2^{8})$ . This work can be applied to test and prevent intentional tampering of data bit stream and safeguarding it against malicious activities, especially in applications such as cryptography that heavily relies on Galois field arithmetic.

We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal of the program's transition system followed by a constraint-based invariant synthesis with constraints coming from both the original and the reversed transition system. The latter task is performed by a simple call to an off-the-shelf SMT-solver, which allows us to leverage the latest advances in SMT-solving. Moreover, our method offers a combination of features not present (as a whole) in previous approaches: it handles programs with non-determinism, provides relative completeness guarantees and supports programs with polynomial arithmetic. The experiments performed with our prototype tool RevTerm show that our approach, despite its simplicity and stronger theoretical guarantees, is at least on par with the state-of-the-art tools, often achieving a non-trivial improvement under a proper configuration of its parameters.

Modern implementations of homomorphic encryption (HE) rely heavily on polynomial arithmetic over a finite field. This is particularly true of the CKKS, BFV, and BGV HE schemes. Two of the biggest performance bottlenecks in HE primitives and applications are polynomial modular multiplication and the forward and inverse number-theoretic transform (NTT). Here, we introduce Intel Homomorphic Encryption Acceleration Library (Intel HEXL), a C++ library which provides optimized implementations of polynomial arithmetic for Intel processors. Intel HEXL takes advantage of the recent Intel Advanced Vector Extensions 512 (Intel AVX512) instruction set to provide state-of-the-art implementations of the NTT and modular multiplication. On the forward and inverse NTT, Intel HEXL provides up to 7.2x and 6.7x speedup, respectively, over a native C++ implementation. Intel HEXL also provides up to 6.0x speedup on the element-wise vector-vector modular multiplication, and 1.7x speedup on the element-wise vector-scalar modular multiplication. Intel HEXL is available open-source at https://github.com/intel/hexl under the Apache 2.0 license and has been adopted by the Microsoft SEAL and PALISADE homomorphic encryption libraries.

Parsing large expressions, in particular large polynomial expressions, is an important task for computer algebra systems. Despite of the apparent simplicity of the problem, its efficient software implementation brings various challenges. Among them is the fact that this is a memory bound application for which a multi-threaded implementation is necessarily limited by the characteristics of the memory organization of supporting hardware. In this thesis, we design, implement and experiment with a multi-threaded parser for large polynomial expressions. We extract parallelism by splitting the input character string, into meaningful sub-strings that can be parsed concurrently before being merged into a single polynomial. Our implementation targeting multi-core processors is realized with the Basic Polynomial Algebra Subprograms (BPAS). Experimental results show that the approach is promising both in terms of speedup factors and memory consumption.

Polynomial arithmetic expressions are frequently used in encryption, decryption, digital signal processing and many other embedded applications. Compiler optimization for polynomial expressions can improve the performance of the embedded applications. This article presents an improved compiler optimization method for multiple arithmetic polynomial expressions. Considering the semantic and timing information of arithmetic instructions, the algorithm uses a canonical representation for all expressions, taking consideration of times of execution, architecture feature and control-flow information. It calculates sub-expressions’ weights based on the target architecture description and heuristically choose the sub-expressions. It achieves better instruction level parallelism from the consideration of sub-expressions’ weights, which contains architecture information. Experiment results show that compared to traditional optimization methods, this algorithm further improves the code density and the performance of the generated binary codes.

Source routing (SR) is a prominent alternative to table-based routing for reducing the number of network states. However, traditional SR approaches, based on Port Switching, still maintain a state in the packet by using a header rewrite operation. The residue number system (RNS) is a promising way of executing fully stateless SR, in which forwarding decisions at core nodes rely on a simple modulo operation over a route label. Nevertheless, such operation over integer arithmetic is not natively supported by commodity network hardware. Thus, we propose a novel RNS-based SR scheme, named PolKA, that explores binary polynomial arithmetic using Galois field (GF) of order 2. We evaluate PolKA in comparison to Port Switching by implementing emulated and hardware prototypes using P4 architecture. Results show that PolKA can achieve equivalent performance, while providing advanced routing features, such as fast failure reaction and agile path migration.

The problem of determining whether a polynomial defined over a finite field ring is smooth or not with respect to a given degree, is the most intensive arithmetic operation of the so-called descent phase of index-calculus algorithms. In this paper, we present an analysis and efficient implementation of Coppersmith’s smoothness test for polynomials defined over finite fields with characteristic three. As a case study, we review the best strategies for obtaining a fast field and polynomial arithmetic for polynomials defined over the ring $$F_q[X],$$ with $$q=3^6,$$ and report the timings achieved by our library when computing the smoothness test applied to polynomials of several degrees defined in that ring. This software library was recently used in Adj et al. (Cryptology 2016. http://eprint.iacr.org/2016/914 ), as a building block for achieving a record computation of discrete logarithms over the 4841-bit field $${{\mathbb {F}}}_{3^{6\cdot 509}}$$ .

Recent studies on the performance of private set operations have examined the use of homomorphic public-key encryption and the technique of representing sets as polynomials in a cryptographic model. These polynomial-based solutions require intensive polynomial arithmetic that exhibit quadratic computational complexity. In an effort to develop practical algorithms for private set operations, various well-known techniques such as Karatsuba’s algorithm or the fast Fourier transform (FFT) can be used to reduce the complexity of polynomial computations. The FFT appears to be the obvious best choice; however, the use of FFTs in the implementation of polynomial-based set operations may lead to certain subtle technical problems. These problems become particularly serious when the cardinality of the sets is dynamic. Furthermore, our experiment shows that Karatsuba’s algorithm delivers higher performance than the FFT in our application, provided that a reasonable response time is important. In addition, our experimental implementation demonstrates the heuristic bound on cardinality for which Karatsuba’s algorithm outperforms the FFT. This value can be used to determine the superior optimization techniques and settings in the deployment of private set operation schemes.

The paper studies the algorithmic complexity of subproblems for satisfiability in positive integers of simultaneous divisibility of linear polynomials with nonnegative coefficients. In the general case, it is not known whether this problem is in the class NP, but that it is in NEXPTIME is known. The NP-completeness of two series of restricted versions of this problem such that a divisor of a linear polynomial is a number in the first case, and a linear polynomial is a divisor of a number in the second case is proved in the paper. The parameters providing the NP-completeness of these problems have been established. Their membership in the class P has been proven for smaller values of these parameters. For the general problem SIMULTANEOUS DIVISIBILITY OF LINEAR POLYNOMIALS, NP-hardness has been proven for its particular case, when the coefficients of the polynomials are only from the set {1, 2} and constant terms are only from the set {1, 5}.

We present two new algorithms for the computation of the q-integer linear decomposition of a multivariate polynomial. Such a decomposition is essential for the treatment of q-hypergeometric symbolic summation via creative telescoping and for describing the q-counterpart of Ore-Sato theory. Both of our algorithms require only basic integer and polynomial arithmetic and work for any unique factorization domain containing the ring of integers. Complete complexity analyses are conducted for both our algorithms and two previous algorithms in the case of multivariate integer polynomials, showing that our algorithms have better theoretical performances. A Maple implementation is also included which suggests that our algorithms are much faster in practice than previous algorithms.

Ordinary arithmetic has the basic operations of addition, subtraction, multiplication, and division defined over the integers and the real numbers. Similar operations can be defined over other mathematical structures—certain subsets of integers, polynomials, matrices, and so forth. This chapter is a short discussion on such generalizations. The first section of the chapter is an introduction to two types of abstract mathematical structures that are especially important in cryptography: groups and fields. The second section consists of a review of ordinary polynomial arithmetic. The third section draws on the first two sections and covers polynomial arithmetic over certain types of fields. And the last section is on the construction of some fields that are especially important in cryptography.

In this chapter we analyze the \(\mathtt {LPR}\) ring-LWE public key encryption scheme of Sect. 2.4.1 and design a compact hardware architecture of the encryption processor. From Fig. 2.4 of Sect. 2.4.1, we see that the \(\mathtt {LPR}\) encryption scheme is composed of a discrete Gaussian sampler, a polynomial arithmetic (addition/multiplication) unit, a message encoder and a message decoder. In the last chapter we described how to design the discrete Gaussian sampler efficiently. In this chapter we first design a novel polynomial arithmetic unit and integrate it with the discrete Gaussian sampler to realize the ring-LWE public key encryption processor.

Recent works on reducing the size of Error Correcting Codes have investigated the usage of rank metric instead of Hamming metric. Numerous proposals for the NIST Post-Quantum Cryptography competition, including four second round candidates, rely on these codes. In this paper, we discuss several non-trivial issues when porting these schemes into real-world systems on different platforms, such as Intel x86, Armv6 and Armv8. We provide insights on how to implement the underlying finite field and polynomial arithmetic, or the generation of errors of a given rank in constant-time, and report execution time of several rank-based cryptosystems, showing that the achieved performance is similar to those of some of the most popular lattice-based cryptosystems.

We present a new algorithm for the computation of the integer-linear decomposition of a multivariate polynomial. Such a decomposition is used in Ore-Sato theory and discrete creative telescoping, for example to detect applicability of Zeilberger's algorithm to a hypergeometric term. Our algorithm is quite straightforward, requiring only basic polynomial arithmetic along with efficient rational root finding. We present complete complexity analyses for both our and previous algorithms in the case of bivariate integer polynomials, and show that our method has a better theoretical performance. We also provide a Maple implementation which shows that our method is faster in practice than previous algorithms.

We have implemented a high-performance C library for sparse polynomials, which is provided as an add-on module to the open-source computation library FLINT [7]. Our implementation incorporates a number of recent theoretical advances in supersparse polynomial arithmetic, most notably recent algorithms for sparse interpolation and multiplication. We provide a summary of the provided functionality, a selection of key implementation decisions, and some preliminary timing data.

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and a serious contender in NIST’s ongoing Post-Quantum Cryptography (PQC) standardization project. An important criterion for the assessment of candidates is their computational cost in various hardware and software environments. This paper contributes to the evaluation of NTRUEncrypt on the ATmega class of AVR microcontrollers, which belongs to the most popular 8-bit platforms in the embedded domain. More concretely, we present AvrNtru, a carefully-optimized implementation of NTRUEncrypt that we developed from scratch with the goal of achieving high performance and resistance to timing attacks. AvrNtru complies with version 3.3 of the EESS#1 specification and supports recent product-form parameter sets like ees443ep1, ees587ep1, and ees743ep1. A full encryption operation (including mask generation and blindingpolynomial generation) using the ees443ep1 parameters takes 834,272 clock cycles on an ATmega1281 microcontroller; the decryption is slightly more costly and has an execution time of 1,061,683 cycles. When choosing the ees743ep1 parameters to achieve a 256-bit security level, 1,539,829 clock cycles are cost for encryption and 2,103,228 clock cycles for decryption. We achieved these results thanks to a novel hybrid technique for multiplication in truncated polynomial rings where one of the operands is a sparse ternary polynomial in product form. Our hybrid technique is inspired by Gura et al’s hybrid method for multiple-precision integer multiplication (CHES 2004) and takes advantage of the large register file of the AVR architecture to minimize the number of load instructions. A constant-time multiplication in the ring specified by the ees443ep1 parameters requires only 210,827 cycles, which sets a new speed record for the arithmetic component of a lattice-based cryptosystem on an 8-bit microcontroller.

The multiplication of polynomials is a fundamental operation in complexity theory. Indeed, for many arithmetic problems, the complexity of algorithms is expressed in terms of the complexity of polynomial multiplication. For example, the complexity of euclidean division or of multi-point evaluation/interpolation (and others) is often expressed in terms of the complexity of polynomial multiplication. This shows that a better multiplication algorithm allows to perform the corresponding operations faster. A 2016 result gave an improved asymptotic complexity for the multiplication of polynomials over finite fields. This article is the starting point of the thesis; the present work aims to study the implications of the new complexity bound, from a theoretical and practical point of view.The first part focuses on the multiplication of univariate polynomials. This part presents two new algorithms that should make the computation faster in practice (rather than asymptotically speaking). While it is difficult in general to observe the predicted speed-up, some specific cases are particularly favorable. Actually, the second proposed algorithm, which is specific to finite fields, leads to a better implementation for the multiplication in F 2 [X], about twice as fast as state-of-the-art software.The second part deals with the arithmetic of multivariate polynomials modulo an ideal, as considered typically for polynomial system solving. This work assumes a simplified situation, with only two variables and under certain regularity assumptions. In this particular case, there are algorithms whose complexity is asymptotically optimal (up to logarithmic factors), with respect to input/output size. The implementation for this specific case is then significantly faster than general-purpose software, the speed-up becoming larger and larger when the input size increases., La multiplication de polynômes est une opération fondamentale en théorie de la complexité. En effet, pour de nombreux problèmes d’arithmétique, la complexité des algorithmes s’exprime habituellement en fonction de la complexité de la multiplication. Un meilleur algorithme de multiplication permet ainsi d’effectuer les opérations concernées plus rapidement. Un résultat de 2016 a établi une meilleure complexité asymptotique pour la multiplication de polynômes dans des corps finis. Cet article constitue le point de départ de la thèse ; l’objectif est d’étudier les conséquences à la fois théoriques et pratiques de la nouvelle borne de complexité.La première partie s’intéresse à la multiplication de polynômes à une variable. Cette partie présente deux nouveaux algorithmes censés accélérer le calcul en pratique (plutôt que d’un point de vue asymptotique). S’il est difficile dans le cas général d’observer l’amélioration prévue, certains cas précis sont particulièrement favorables. En l’occurrence, le second algorithme proposé, spécifique aux corps finis, conduit à une meilleure implémentation de la multiplication dans F_2[X], environ deux fois plus rapide que les logiciels précédents.La deuxième partie traite l’arithmétique des polynômes à plusieurs variables modulo un idéal, telle qu’utilisée par exemple pour la résolution de systèmespolynomiaux. Ce travail suppose une situation simplifiée, avec seulement deux variables et sous certaines hypothèses de régularité. Dans ce cas particulier, la deuxième partie de la thèse donne des algorithmes de complexité asymptotiquement optimale (à des facteurs logarithmiques près), par rapport à la taille des entrées/sorties. L’implémentation pour ce cas spécifique est alors nettement plus rapide que les logiciels généralistes, le gain étant de plus en plus marqué lorsque la taille de l’entrée augmente.

Rings is an open-source library, written in Java and Scala programming languages, which implements basic concepts and algorithms from computational commutative algebra. The goal of the Rings library is to provide a high-performance implementation packed into a lightweight library (not a full-featured CAS) with a clean application programming interface (API), which meets modern standards of software development. Polynomial arithmetic, GCDs, factorization, and Grobner bases are implemented with the use of modern fast algorithms. Rings provides a simple API with a fully typed hierarchy of algebraic structures and algorithms for commutative algebra. The use of the Scala language brings a quite novel powerful, strongly typed functional programming model allowing to write short, expressive, and fast code for applications.

Polynomials may be represented sparsely in an effort to conserve memory usage and provide a succinct and natural representation. Moreover, polynomials which are themselves sparse – have very few non-zero terms – will have wasted memory and computation time if represented, and operated on, densely. This waste is exacerbated as the number of variables increases. We provide practical implementations of sparse multivariate data structures focused on data locality and cache complexity. We look to develop high-performance algorithms and implementations of fundamental polynomial operations, using these sparse data structures, such as arithmetic (addition, subtraction, multiplication, and division) and interpolation. We revisit a sparse arithmetic scheme introduced by Johnson in 1974, adapting and optimizing these algorithms for modern computer architectures, with our implementations over the integers and rational numbers vastly outperforming the current wide-spread implementations. We develop a new algorithm for sparse pseudo-division based on the sparse polynomial division algorithm, with very encouraging results. Polynomial interpolation is explored through univariate, dense multivariate, and sparse multivariate methods. Arithmetic and interpolation together form a solid high-performance foundation from which many higher-level and more interesting algorithms can be built.

Sparse polynomial interpolation, sparse linear system solving or modular rational reconstruction are fundamental problems in Computer Algebra. They come down to computing linear recurrence relations of a sequence with the Berlekamp-Massey algorithm. Likewise, sparse multivariate polynomial interpolation and multidimensional cyclic code decoding require guessing linear recurrence relations of a multivariate sequence.Several algorithms solve this problem. The so-called Berlekamp-Massey-Sakata algorithm (1988) uses polynomial additions and shifts by a monomial. The Scalar-FGLM algorithm (2015) relies on linear algebra operations on a multi-Hankel matrix, a multivariate generalization of a Hankel matrix. The Artinian Gorenstein border basis algorithm (2017) uses a Gram-Schmidt process.We propose a new algorithm for computing the Gröbner basis of the ideal of relations of a sequence based solely on multivariate polynomial arithmetic. This algorithm allows us to both revisit the Berlekamp-Massey-Sakata algorithm through the use of polynomial divisions and to completely revise the Scalar-FGLM algorithm without linear algebra operations.A key observation in the design of this algorithm is to work on the mirror of the truncated generating series allowing us to use polynomial arithmetic modulo a monomial ideal. It appears to have some similarities with Padé approximants of this mirror polynomial.As an addition from the paper published at the ISSAC conferance, we give an adaptive variant of this algorithm taking into account the shape of the final Gröbner basis gradually as it is discovered. The main advantage of this algorithm is that its complexity in terms of operations and sequence queries only depends on the output Gröbner basis.All these algorithms have been implemented in Maple and we report on our comparisons.

Arithmetic operations are fundamental in computing models. Novel arithmetic P systems are constructed to perform four basic operations: addition, subtraction, multiplication, division. The digits of decimal integers are directly put into hierarchical membranes, one digit one membrane, thus, the number of membranes is reduced and complexity is lowered. Core evolution rules are designed for single digit operations according to the arithmetic formula tables widely used by humans. Some examples are given to illustrate how to compute decimal integers in these P systems and the results indicates that these P systems can efficiently carry out arithmetic computations of integers.

This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein’s 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein’s 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein’s algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.

Polynomial multiplication is a key algorithm underlying computer algebra systems (CAS) and its efficient implementation is crucial for the performance of CAS. In this context coefficients of polynomials come from domains such as the integers, rationals and finite fields where arithmetic is performed exactly without rounding error.

Program analysis requires the generation of program properties expressing conditions to hold at intermediate program locations. When it comes to programs with loops, these properties are typically expressed as loop invariants. In this paper we study a class of multi-path program loops with numeric variables, in particular nested loops with conditionals, where assignments to program variables are polynomial expressions over program variables. We call this class of loops extended P-solvable and introduce an algorithm for generating all polynomial invariants of such loops. By an iterative procedure employing Grobner basis computation, our approach computes the polynomial ideal of the polynomial invariants of each program path and combines these ideals sequentially until a fixed point is reached. This fixed point represents the polynomial ideal of all polynomial invariants of the given extended P-solvable loop. We prove termination of our method and show that the maximal number of iterations for reaching the fixed point depends linearly on the number of program variables and the number of inner loops. In particular, for a loop with m program variables and r conditional branches we prove an upper bound of \(m\cdot r\) iterations. We implemented our approach in the Aligator software package. Furthermore, we evaluated it on 18 programs with polynomial arithmetic and compared it to existing methods in invariant generation. The results show the efficiency of our approach.