Search

The selection of special-form moduli and their corresponding primitive roots have been proposed, which provide for a simplified structure of arithmetic devices using number-theoretic transforms. A method for determining moduli has been developed that ensures a minimum number of arithmetic operations when performing the modulo addition and multiplication operations. The structures of special-form modulo adders have been developed and modeled, which make it possible to perform the addition operation as quickly as possible. The modulo adders for the Fermat, Mersenne, and Golomb numbers have been synthesized and tested, which could be used in the arithmetic units of high-speed correlators and filters. Real-time correlation and convolution calculation become a rather time-consuming task in the case of long input sequences. To solve this task, it is advisable to apply the so-called fast algorithms. However, this requires the high-performance calculators of convolution and correlation, which often exceed the capabilities of modern computer equipment, Therefore, the proposed procedure for determining the modulus, as well as the designed structural circuits for special-form modulo adders, make it possible to accelerate the computation of correlations and convolutions using number-theoretic transforms. Since the operation of modulo multiplication is performed using the addition and shift operations, the complexity of calculating the number-theoretic transformations largely depends on the number of unities in the binary representation of the degrees of the primitive root. The operation of multiplication is typically reduced to the multiple addition of numbers, which is why the complexity and speed performance of arithmetic devices for numeric-theoretic transformations is determined by the characteristics of the modulo adders. The proposed method for designing computing moduli for the digital devices that calculate correlation and convolution, based on rapid theoretical-numerical transformations, provides the simplified hardware and software implementation of these structures, resulting in high-speed processing of signals and images

Euler's identity and the Rogers-Ramanujan identities are perhaps the most famous results in the theory of partitions. According to them, 1-distinct and 2-distinct partitions of n are equinumerous with partitions of n into parts congruent to ±1 modulo 4 and partitions of n into parts congruent to ±1 modulo 5, respectively. Furthermore, their generating functions are modular functions up to multiplication by rational powers of q. For d ≥ 3, however, there is neither the same type of partition identity nor modularity for d-distinct partitions. Instead, there are partition inequalities and mock modularity related with d-distinct partitions. For example, the Alder-Andrews Theorem states that the number of d-distinct partitions of n is greater than or equal to the number of partitions of n into parts which are congruent to ±1 (mod d+3). In this note, we present the recent developments of generalizations and analogs of the Alder-Andrews Theorem and establish asymptotic lower and upper bounds for the d-distinct partitions. Using the asymptotic relations and data obtained from computation, we propose a conjecture on a partition inequality that gives an upper bound for d-distinct partitions. Specifically, for d ≥ 4, the number of d-distinct partitions of n is less than or equal to the number of partitions of n into parts congruent to ±1 (mod m), where m ≤ 2dπ^2 / [3 log^2 (d)+6 log d] .

Define $\|n\|$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\|n\|\ge 3\log_3 n$ for all $n$, leading this author and Zelinsky to define the defect of $n$, $\delta(n)$, to be the difference $\|n\|-3\log_3 n$. Meanwhile, in the study of addition chains, it is common to consider $s(n)$, the number of small steps of $n$, defined as $\ell(n)-\lfloor\log_2 n\rfloor$, an integer quantity. So here we analogously define $D(n)$, the integer defect of $n$, an integer version of $\delta(n)$ analogous to $s(n)$. Note that $D(n)$ is not the same as $\lceil \delta(n) \rceil$. We show that $D(n)$ has additional meaning in terms of the defect well-ordering considered in [3], in that $D(n)$ indicates which powers of $\omega$ the quantity $\delta(n)$ lies between when one restricts to $n$ with $\|n\|$ lying in a specified congruence class modulo $3$. We also determine all numbers $n$ with $D(n)\le 1$, and use this to generalize a result of Rawsthorne [18]., Comment: 25 pages, 6 tables

Satisfiability Modulo Theories (SMT) is the problem of deciding the satisfiability of a first-order formula with respect to some theory or combination of theories; Verification Modulo Theories (VMT) is the problem of analyzing the reachability for transition systems represented in terms of SMT formulae. In this article, we tackle the problems of SMT and VMT over the theories of nonlinear arithmetic over the reals (NRA) and of NRA augmented with transcendental (exponential and trigonometric) functions (NTA). We propose a new abstraction-refinement approach for SMT and VMT on NRA or NTA, called Incremental Linearization . The idea is to abstract nonlinear multiplication and transcendental functions as uninterpreted functions in an abstract space limited to linear arithmetic on the rationals with uninterpreted functions. The uninterpreted functions are incrementally axiomatized by means of upper- and lower-bounding piecewise-linear constraints. In the case of transcendental functions, particular care is required to ensure the soundness of the abstraction. The method has been implemented in the M ath SAT SMT solver and in the nu X mv model checker. An extensive experimental evaluation on a wide set of benchmarks from verification and mathematics demonstrates the generality and the effectiveness of our approach.

Let G be the reduced Gro bner basis of a zero-dimensional ideal I ⊆ K[X, Y] of bivariate polynomials over an effective field K. Modulo suitable regularity assumptions on G and suitable precomputations as a function of G , we prove the existence of a quasi-optimal algorithm for the reduction of polynomials in K [X, Y] with respect to G . Applications include fast algorithms for multiplication in the quotient algebra A=K[X, Y] / I and for conversions due to changes of the term ordering.

We show that if a set of players hold shares of a value $a \in \mathbb{F}_p $ for some prime p (where the set of shares is written [a]p), it is possible to compute, in constant rounds and with unconditional security, sharings of the bits of a, i.e., compute sharings [a0]p, ..., [al−−1]p such that l = ⌈ log2p ⌉, a0,...,al−1∈{0,1} and a = ∑i=0l−−1ai 2i. Our protocol is secure against active adversaries and works for any linear secret sharing scheme with a multiplication protocol. The complexity of our protocol is $\mathcal{O}(l {\rm log} l)$ invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in $\mathcal{O}(1)$ rounds. This result immediately implies solutions to other long-standing open problems such as constant-rounds and unconditionally secure protocols for deciding whether a shared number is zero, comparing shared numbers, raising a shared number to a shared exponent and reducing a shared number modulo a shared modulus.

In the recent past, subquadratic space complexity multipliers have been proposed for binary fields defined by irreducible trinomials and some specific pentanomials. For such multipliers, alternative irreducible polynomials can also be used, in particular, nearly all one polynomials (NAOPs) seem to be better than pentanomials. For improved efficiency, multiplication modulo an NAOP is performed via modulo a quadrinomial whose degree is one more than that of the original NAOP. In this paper, we present a Toeplitz matrix-vector product based approach for multiplication modulo a quadrinomial. We obtain a fully parallel multiplier with a subquadratic space complexity. The Toeplitz matrix-vector product-based approach is also interesting in the design of sequential multipliers. We present two such multipliers that process a two-bit digit every clock cycle. Field-programmable gate-array implementations of the proposed sequential as well as fully parallel multipliers for the field size of 163 are also presented.

This paper is devoted to the study of number representations and algorithms leading to efficient implementations of modular adders and multipliers on recent Field Programmable Arrays. Our hardware operators take advantage of the building blocks available in such devices: carry-propagate adders, memory blocks, and sometimes embedded multipliers. The first part of the paper describes three basic methodologies to carry out a modulo m addition and presents in more details the design of modulo (2^n\pm 1) adders. The major result is a new modulo (2n+1) addition algorithm leading to an area-time efficient implementation of this arithmetic operation on FPGAs. The second part describes a modulo m multiplication algorithm involving small multipliers and memory blocks, and modulo (2n+1) multipliers based on Ma's algorithm. We also suggest some improvements of this operator in order to perform a multiplication in the group (\mathbb{Z}^*_{2^n+1}, \cdot); Cet article est consacré à l'étude de systèmes de représentation des nombres et algorithmes conduisant à des implantations efficaces d’additionneurs et de multiplieurs modulo m sur les FPGA actuels. Nos opérateurs matériels tirent parti des briques de base disponibles dans de tels circuits : additionneurs à retenue propagée, blocs de mémoire et petits multiplieurs. La première partie de l’article décrit trois méthodes de conception d’additionneurs modulo m et présent plus particulièrement et additionneurs modulo (2n+1). Le principal résultat est un nouvel additionneur modulo ( 2n + 1) conduisant à un opérateur compact et rapide sur FPGA. La seconde partie propose un algorithme de multiplication modulo m requérant des petits multiplieurs et des blocs de mémoire. Nous présentons également un multiplieur modulo (2N + 1) basé sur l'algorithme de Ma et suggérions quelques modifications afin d 'effectuer la multiplication dans le groupe (Z*2n +1)

We investigate a variant of the so-called “binary” algorithm for finding the GCD (greatest common divisor) of two numbers which requires no comparisons. We show that when implemented with carry-save hardware, it can be used to find the modulo B inverse of an n-bit binary integer in a time proportional to n, using only registers of length proportional to n. Such a hardware implementation of this algorithm set up for finding inverses with respect to a 336 bit modulus B would have applications in the currently expanding field of secure data transmission and storage. In such an implementation, multiplication in linear time-both modulo B and ordinary—would come along as a by-product because multiplication can be achieved by a sequence of nine inversions, some additions and negations.