Search

The kernel polynomial method (KPM) is a powerful numerical method for approximating spectral densities. Typical implementations of the KPM require an a prior estimate for an interval containing the support of the target spectral density, and while such estimates can be obtained by classical techniques, this incurs addition computational costs. We propose a spectrum adaptive KPM based on the Lanczos algorithm without reorthogonalization, which allows the selection of KPM parameters to be deferred to after the expensive computation is finished. Theoretical results from numerical analysis are given to justify the suitability of the Lanczos algorithm for our approach, even in finite precision arithmetic. While conceptually simple, the paradigm of decoupling computation from approximation has a number of practical and pedagogical benefits, which we highlight with numerical examples. [ABSTRACT FROM AUTHOR]

For any positive integer n, let Mp contain the prime numbers less than n. Assuming Mp as the set of moduli, we draw a graph with the vertex set f1; 2; 3; ...; ng, and an edge will be built between the vertices p and q if and only if p ≡ (q mod m) for some m ∥ Mp: We call this graph a prime congruence simple graph and label this graph as G(n;Mp). The objective of this work is to characterize prime congruence simple graphs, and afterwards, by utilizing these graphs, solutions to the system of linear congruences are suggested and demonstrated by applying modular arithmetic. It is shown that this graph is always a connected graph. The generalized formulae for vertex degrees, size, chromatic number, domination number, clique number, and eccentricity of the prime congruence simple graphs are proposed and proved. Also, independence numbers as well as a covering number for the proposed graph through vertices and edges are evaluated. Lastly, as an application of prime congruence simple graphs, the solution of a system of linear congruences is discussed in terms of the degrees of the vertices. [ABSTRACT FROM AUTHOR]

Let Fk be a Fibonacci number and let Lk be a Lucas number. By applying Catalan's conjecture and the modular arithmetic method, we solve the exponential Diophantine equations of the form (22s-1)x + (2s+1)y = F2k and (22s - 1)x + (2s+1)y = L²k where x, y, k are non-negative integers and s is a positive integer. [ABSTRACT FROM AUTHOR]

Fully Homomorphic Encryption (FHE) enables computation directly on encrypted data. This property is desirable for outsourced computation of sensitive data as it relies solely on the underlying security of the cryptosystem and not in access control policies. Even though FHE is still significantly slower than unencrypted computation, practical times are possible for applications easily representable as low-order polynomials, since most FHE schemes support modular addition and multiplication over ciphertexts. If, however, an application cannot be expressed with low-order polynomials, then Boolean logic must be emulated. This bit-level arithmetic enables any computation to be performed homomorphically. Nevertheless, as it runs on top of the natively supported modular arithmetic, it has poor performance, which hinders its use in the majority of scenarios. In this work, we propose Bridging, a technique that allows conversion from bit-level to modular arithmetic and vice-versa. This enables the use of the comprehensive computation provided by bit-level arithmetic and the performance of modular arithmetic within the same application. Experimental results show that Bridging can lead to 1-2 orders of magnitude performance improvement for tested benchmarks and two real-world applications: URL denylisting and genotype imputation. Bridging performance comes from two factors: reduced number of operations and smaller multiplicative depth. [ABSTRACT FROM AUTHOR]

Let Fk be a Fibonacci number and let Lk be a Lucas number. By applying Catalan's conjecture and the modular arithmetic method, we solve the exponential Diophantine equations of the form (22s-1)x + (2s+1)y = F2k and (22s - 1)x + (2s+1)y = L²k where x, y, k are non-negative integers and s is a positive integer. [ABSTRACT FROM AUTHOR]

For any positive integer $ \mathrm{n} $, let $ \mathrm{M_{p}} $ contain the prime numbers less than $ \mathrm{n} $. Assuming $ \mathrm{M_{p}} $ as the set of moduli, we draw a graph with the vertex set $ \{1, 2, 3, \cdots, \mathrm{n}\} $, and an edge will be built between the vertices $ \mathrm{p} $ and $ \mathrm{q} $ if and only if $ \mathrm{p}\equiv (\mathrm{q}\; mod\; \mathrm{m}) $ for some $ \mathrm{m}\in $ $ \mathrm{M_{p}}. $ We call this graph a prime congruence simple graph and label this graph as $ \mathrm{G}(\mathrm{n}, \mathrm{M}_{p}) $. The objective of this work is to characterize prime congruence simple graphs, and afterwards, by utilizing these graphs, solutions to the system of linear congruences are suggested and demonstrated by applying modular arithmetic. It is shown that this graph is always a connected graph. The generalized formulae for vertex degrees, size, chromatic number, domination number, clique number, and eccentricity of the prime congruence simple graphs are proposed and proved. Also, independence numbers as well as a covering number for the proposed graph through vertices and edges are evaluated. Lastly, as an application of prime congruence simple graphs, the solution of a system of linear congruences is discussed in terms of the degrees of the vertices.

Let L be a lattice. We exhibit algorithms for calculating Tits buildings and orbits of vectors in L for certain subgroups of the orthogonal group O (L). We discuss how these algorithms can be applied to determine the configuration of boundary components in the Baily-Borel compactification of orthogonal modular varieties and to improve the performance of computer arithmetic of orthogonal modular forms. [ABSTRACT FROM AUTHOR]

This article by Felix Lev explores the idea that finite mathematics can serve as the foundation for classical mathematics and quantum theory. Lev argues that a specific choice of finite mathematics can provide a more general framework for physical theories, including quantum theory. The article focuses on chapter 6 of Lev's book, which discusses why finite mathematics is more general than infinitary mathematics and why the latter is a degenerate case of the former. The text explores the concept of finite rings or fields versus classical integer arithmetic, and argues that if the number of elements in the finite rings or fields tends to infinity, classical integer arithmetic can be considered a degenerate case. The article also discusses the notion of generality in classical mathematics and its relationship to finite mathematics, drawing parallels with physical notions such as Planck's constant and the velocity of light. It references the work of the Hungarian logic and relativity school and discusses the equivalence of theories and the concept of translation between theories. The text concludes by highlighting the diversity of views on the relationship between mathematics and the real world. [Extracted from the article]

Copyright of Arab Journal for Scientific Publishing is the property of Research & Development of Human Recourses Center (REMAH) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The technique of distinguishing one knot from another by coloring arcs and applying some basic modular arithmetic is part of most standard undergraduate knot theory classes. When we study n-colorability, we are usually only interested when n is a prime number. But what if n is composite? What can we say then? [ABSTRACT FROM AUTHOR]

Summary: We analyze the convergence of quasi‐Newton methods in exact and finite precision arithmetic using three different techniques. We derive an upper bound for the stagnation level and we show that any sufficiently exact quasi‐Newton method will converge quadratically until stagnation. In the absence of sufficient accuracy, we are likely to retain rapid linear convergence. We confirm our analysis by computing square roots and solving bond constraint equations in the context of molecular dynamics. In particular, we apply both a symmetric variant and Forsgren's variant of the simplified Newton method. This work has implications for the implementation of quasi‐Newton methods regardless of the scale of the calculation or the machine. [ABSTRACT FROM AUTHOR]

In this paper, we discuss two efficient three-term conjugate gradient methods (ECG) for impulse noise removal. The directions of ECG are first the direction of steepest descent and then spanned by the three terms: The steepest descent direction, the previous direction, and the gradient differences at the previous and current points. The second and third terms are scaled by two different step sizes called conjugate gradient parameters. Our goal is to generate and control these parameters such that they do not jointly dominate while preserving the effect of all terms, except near the optimizer where the first term dominates the other two terms. They are independent of the line search method and useful for finite precision arithmetic. The global convergence of ECG is proved. The efficiency (the lowest relative cost of function evaluations) and robustness (highest number of solved problems) of ECG compared to known conjugate gradient methods are shown in terms of PSNR (peak signal noise ratio) and time in seconds. [ABSTRACT FROM AUTHOR]

Random Linear Network Coding (RLNC) is well-known to provide high throughput and low latency for vast communication networks. However, RLNC often suffers from high coefficients overhead, specifically, when it's applied to limited resource or short-packet networks. Herein, the problem of RLNC coefficients vector overhead is revisited. A novel framework, based on modular arithmetic and prime numbers, and influenced by the Chinese remainder theorem (CRT), is proposed to reduce the coefficients overhead by augmenting only a tiny one item coefficient instead of the entire coefficients vector. The proposed method successfully addresses all the shortcomings of previous methods, including restrictions on generation size and packet density, recoding on intermediate nodes, and creating innovative coding vectors. Theoretical analysis and experimental demonstrate the superior performance of the proposed scheme in terms of coefficients overhead ratio, download time, throughput, and packet drop rate. This evaluation has considered two types of networks: wireless sensors network for Internet of things, and conventional wireline Ethernet. [ABSTRACT FROM AUTHOR]

The spectral decomposition of a real skew-symmetric matrix is shown to be equivalent to a specific structured singular value decomposition (SVD) of the matrix. Based on such equivalence, we propose a skew-symmetric Lanczos bidiagonalization (SSLBD) method to compute extremal singular values and the corresponding singular vectors of the matrix, from which its extremal conjugate eigenpairs are recovered pairwise in real arithmetic. A number of convergence results on the method are established, and accuracy estimates for approximate singular triplets are given. In finite precision arithmetic, it is proven that the semi-orthogonality of each set of the computed left and right Lanczos basis vectors and the semi-biorthogonality of two sets of basis vectors are needed to compute the singular values accurately and to make the method work as if it does in exact arithmetic. A commonly used efficient partial reorthogonalization strategy is adapted to maintain the desired semi-orthogonality and semi-biorthogonality. For practical purpose, an implicitly restarted SSLBD algorithm is developed with partial reorthogonalization. Numerical experiments illustrate the effectiveness and overall efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

We sometimes need to compute the most significant digits of the product of small integers with a multiplier requiring much storage, e.g. a large integer (e.g. |$5^{100}$|⁠) or an irrational number (⁠|$\pi $|⁠). We only need to access the most significant digits of the multiplier—as long as the integers are sufficiently small. We provide an efficient algorithm to compute the range of integers given a truncated multiplier and a desired number of digits. [ABSTRACT FROM AUTHOR]

In this study, we once again use a set of Fibonacci-like sequences to examine the symmetries within the genetic code. This time, our focus is on the physiological state of the amino acids, considering them as charged, in contrast to our previous work where they were seen as neutral. In a pH environment around 7.4, there are four charged amino acids. We utilize the properties of our sequences to accurately describe the symmetries in the genetic code table. These include Rumer's symmetry, the third-base symmetry and the "ideal" symmetry, along with the "supersymmetry" classification schemes. We also explore the special chemical structure of the amino acid proline, presenting two perspectives—shCherbak's view and the Downes–Richardson view—which are included in the description of the above-mentioned symmetries. Our investigation also employs elementary modular arithmetic to precisely describe the chemical structure of proline, connecting the two views seamlessly. Finally, our Fibonacci-like sequences prove instrumental in quickly establishing the multiplet structure of non-standard versions of the genetic code. We illustrate this with an example, showcasing the efficiency of our method in unraveling the complex relationships within the genetic code. [ABSTRACT FROM AUTHOR]

The notion of an Egyptian integral domain D (where every fraction can be written as a sum of unit fractions with denominators from D) is extended here to the notion that a ring R is W-Egyptian, with W a multiplicative set in R. The new notion allows denominators just from W. It is shown that several results about Egyptian domains can be extended to the W-Egyptian context, though some cannot, as shown in counterexamples. In particular, being a sum of unit fractions from W is not equivalent to being a distinct sum of unit fractions from W, so we need to add the notion of the strictly W-Egyptian ring. Connections are made with Jacobson radicals, power series, products of rings, factor rings, modular arithmetic, and monoid algebras. [ABSTRACT FROM AUTHOR]

Post-quantum cryptography is considered to provide security against both traditional and quantum computer attacks. Dilithium is a digital signature algorithm that derives its security from the challenge of finding short vectors in lattices. It has been selected as one of the standardizations in the NIST post-quantum cryptography project. Hardware-software co-design is a commonly adopted implementation strategy to address various implementation challenges, including limited resources, high performance, and flexibility requirements. In this study, we investigate using compact instruction set extensions (ISEs) for Dilithium, aiming to improve software efficiency with low hardware overheads. To begin with, we propose tightly coupled accelerators that are deeply integrated into the RISC-V processor. These accelerators target the most computationally demanding components in resource-constrained processors, such as polynomial generation, Number Theoretic Transform (NTT), and modular arithmetic. Next, we design a set of custom instructions that seamlessly integrate with the RISC-V base instruction formats, completing the accelerators in a compact manner. Subsequently, we implement our ISEs in a chip design for the Hummingbird E203 core and conduct performance benchmarks for Dilithium utilizing these ISEs. Additionally, we evaluate the resource consumption of the ISEs on FPGA and ASIC technologies. Compared to the reference software implementation on the RISC-V core, our co-design demonstrates a remarkable speedup factor ranging from 6.95 to 9.96. This significant improvement in performance is achieved by incorporating additional hardware resources, specifically, a 35% increase in LUTs, a 14% increase in FFs, 7 additional DSPs, and no additional RAM. Furthermore, compared to the state-of-the-art approach, our work achieves faster speed performance with a reduced circuit cost. Specifically, the usage of additional LUTs, FFs, and RAMs is reduced by 47.53%, 50.43%, and 100%, respectively. On ASIC technology, our approach demonstrates 12, 412 cell counts. Our co-design provides a better tradeoff implementation on speed performance and circuit overheads. [ABSTRACT FROM AUTHOR]

The authors consider a conjecture by Chebyshev in 1853 on the distribution of odd primes among those that are one more than a multiple of four and those three more than a multiple of four--and use technology to explore the cardinality of these subsets. Generalizations are presented for student exploration along with several sources for more in-depth research. [ABSTRACT FROM AUTHOR]

Math manipulatives and physical math activities offer numerous benefits in the learning process in all educational levels: they provide concrete representations of abstract concepts, thus helping more students to understand them, and they are an opportunity for students to explore and test their understanding of mathematical concepts. Moreover, in active learning activities conducted with tangible objects, students are physically engaged in the lessons, and are given a fun way to practice their math skills, which contributes with retention and positive feeling. In this article, an active teaching activity aimed at first-year college students is presented, designed to deepen the understanding of finite fields through the construction of a slide rule. The tool presented is easy to make and can be used effectively in a short time. The activity described was carried out as part of a larger workshop on modular arithmetic and the basics of cryptography offered to first-year engineering students at Politecnico di Torino. [ABSTRACT FROM AUTHOR]

An involution refers to a function that acts as its own inverse. In this paper, our focus lies on exploring two-dimensional involutive maps defined by rational functions. These functions have denominators represented by polynomials of degree one and numerators by polynomials of a degree of, at most, two, depending on parameters. We identify the sets in the parameter space of the maps that correspond to involutions. The investigation relies on leveraging algorithms from computational commutative algebra based on the Groebner basis theory. To expedite the computations, we employ modular arithmetic. Furthermore, we showcase how involution can serve as a valuable tool for identifying reversible and integrable systems within families of planar polynomial ordinary differential equations. [ABSTRACT FROM AUTHOR]

We study the stability of the Lanczos algorithm run on problems whose eigenvector empirical spectral distribution is near to a reference measure with well-behaved orthogonal polynomials. We give a backwards stability result which can be upgraded to a forward stability result when the reference measure has a density supported on a single interval with square root behavior at the endpoints. Our analysis implies the Lanczos algorithm run on many large random matrix models is in fact forward stable, and hence nearly deterministic, even when computations are carried out in finite precision arithmetic. Since the Lanczos algorithm is not forward stable in general, this provides yet another example of the fact that random matrices are far from "any old matrix", and care must be taken when using them to test numerical algorithms. [ABSTRACT FROM AUTHOR]

Elliptic curve scalar multiplication (ECSM) is the primitive operation that is also the main computational hurdle in almost all protocols based on elliptic curve cryptography (ECC). This work proposes a novel ECSM hardware architecture by adopting several optimization strategies at circuit and system levels. On the circuit level, it is based on an efficient finite field multiplier that takes fewer clock cycles, produces low latency, and consumes fewer hardware resources. On the system level, Jacobian coordinates with the Montgomery laddering algorithm and a fast scheduling mechanism to execute group operations are adopted. The proposed ECSM design is synthesized and implemented targeting different FPGAs using Xilinx ISE Design Suite. It takes 1.01 ms on the Virtex-7 FPGA to compute a single ECSM operation, occupies 7.1K slices, and achieves 187 MHz frequency. This provides a 30% improvement in computational time with a significantly lower area-time product with better efficiency. Therefore, the proposed ECSM design is better optimized in terms of speed, area-time product, and throughput per slice and hence is suitable for many ECC applications. [ABSTRACT FROM AUTHOR]

We describe Shamir's secret sharing scheme and explain how it can be used for secure and redundant cryptocurrency storage. We include samples of individual and group assignments that can be used in an upper-division cryptology class for students who are familiar with modular arithmetic. It takes about one class to cover Shamir's secret sharing, but additional time can be spent on the described coding project about splitting mnemonic Bitcoin seeds into shares. We also provide references for topics of further study that can you use for student research projects. [ABSTRACT FROM AUTHOR]

The aim of the paper is to re-visit the 1990 Khamsi-Kozlowski-Reich Fixed Point Theorem, which initiated a flourishing field of fixed point theory in modular function spaces. Our result generalises this theorem as well as other classical fixed point theorems, including celebrated 1965 result of Kirk. As the common setting for our investigation, we choose the modulated LTI-spaces defined as modular spaces equipped with a sequential convergence structure, which allows also to use convergence types not associated with any topology (like convergence almost everywhere). [ABSTRACT FROM AUTHOR]

Copyright of Gaceta de la Real Sociedad Matematica Espanola is the property of Real Sociedad Matematica Espanola and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Consideration of a set of examples of practical application of the procedure for identifying overflow of the bit grid of a computer system operating in a non-positional number system in residual classes. The object of the study is the process of processing data represented in the residual class system. Objective. The goal of the work is to consider and analyze examples of the bit grid overflow definition of a computer system when implementing the operation of adding two numbers in a system of residual classes based on the application of a method for determining the bit grid overflow, based on the use of the concept of number rank. Method. The specificity of the functioning of a computer system in a system of residual classes requires the implementation of not only modular operations, but also requires the implementation of additional, so-called non-modular operations. Non-modular operations include the operation of determining the overflow of the bit grid of a computer system in the system of residual classes. In a non-positional number system in residual classes, implementing the process of detecting overflow of the bit grid of a computer system is a difficult task to implement. The method considered in the work for determining the overflow of the bit grid is based on the use of positional features of a non-positional code of numbers in the system of residual classes, namely the true and calculated ranks of a number. The process of determining the overflow of the result of the operation of adding two numbers in the system of residual classes has been studied, since this arithmetic operation is the main, basic operation performed by a computer system. Results. The developed methods are justified theoretically and studied when performing arithmetic modular operations of addition, subtraction and multiplication using tabular procedures. Conclusions. The main advantage of the presented method is that the process of determining the overflow of the bit grid can be carried out in the dynamics of the computing process of the computer system, i.e. without stopping the solution of the problem. This circumstance makes it possible to reduce the unproductive expenditure of the computer system in the system of residual classes. In addition, this method can be used to control the operation of adding two numbers in the residual class system. This increases the reliability of obtaining the true result of the operation of adding two numbers in the system of residual classes. [ABSTRACT FROM AUTHOR]

Finite Markov chains, memoryless random walks on complex networks, appear commonly as models for stochastic dynamics in condensed matter physics, biophysics, ecology, epidemiology, economics, and elsewhere. Here, we review exact numerical methods for the analysis of arbitrary discrete- and continuous-time Markovian networks. We focus on numerically stable methods that are required to treat nearly reducible Markov chains, which exhibit a separation of characteristic timescales and are therefore ill-conditioned. In this metastable regime, dense linear algebra methods are afflicted by propagation of error in the finite precision arithmetic, and the kinetic Monte Carlo algorithm to simulate paths is unfeasibly inefficient. Furthermore, iterative eigendecomposition methods fail to converge without the use of nontrivial and system-specific preconditioning techniques. An alternative approach is provided by state reduction procedures, which do not require additional a priori knowledge of the Markov chain. Macroscopic dynamical quantities, such as moments of the first passage time distribution for a transition to an absorbing state, and microscopic properties, such as the stationary, committor, and visitation probabilities for nodes, can be computed robustly using state reduction algorithms. The related kinetic path sampling algorithm allows for efficient sampling of trajectories on a nearly reducible Markov chain. Thus, all of the information required to determine the kinetically relevant transition mechanisms, and to identify the states that have a dominant effect on the global dynamics, can be computed reliably even for computationally challenging models. Rare events are a ubiquitous feature of realistic dynamical systems, and so the methods described herein are valuable in many practical applications. [ABSTRACT FROM AUTHOR]

Summary: In this article, we explore the usage of scalable vector extension (SVE) to vectorize number‐theoretic transforms (NTTs). In particular, we show that 64‐bit modular arithmetic operations, including modular multiplication, can be efficiently implemented with SVE instructions. The vectorization of NTT loops and kernels involving 64‐bit modular operations was not possible in previous Arm‐based single instruction multiple data architectures since these architectures lacked crucial instructions to efficiently implement modular multiplication. We test and evaluate our SVE implementation on the A64FX processor in an HPE Apollo 80 system. Furthermore, we implement a distributed NTT for the computation of large‐scale exact integer convolutions. We evaluate this transform on HPE Apollo 70, Cray XC50, HPE Apollo 80, and HPE Cray EX systems, where we demonstrate good scalability to thousands of cores. Finally, we describe how these methods can be utilized to count the number of Goldbach partitions of all even numbers to large limits. We present some preliminary results concerning this problem, in particular a histogram of the number of Goldbach partitions of the even numbers up to 240. [ABSTRACT FROM AUTHOR]

Data and information secrecy during storage or transmission has been preserved through the use of cryptography. Consequently, cryptography studies have also progressed from traditional Caesar cipher to the existing cryptographic protocols depending on quantum computing, starting with the latest modular arithmetic-based cryptosystems. The strength of modular arithmetic ciphers lies in the fact that they are computationally difficult to break, but with the advent of quantum computing, even these issues can be cracked with in polynomial time. Research on post-quantum cryptography began in response to this danger, with the goal of creating post-quantum algorithms that are immune to quantum computing. However, cryptographic methods confront a number of other problems, including, but not limited to, availability, integrity, and vulnerability. Despite the researchers' successes, security is still a major issue for Quantum Computing. Because of its many advantages, cyberspace has quickly become the most common medium for disseminating information. Because of the exponential growth of science and technology, notably quantum computers, cyber security is now the top priority for the Internet and other wireless systems. The fundamental goal of this work is to create a Hybrid Quantum Cryptosystem that can be implemented in Wireless Body Sensor Networks. Using a series of comparisons with existing algorithms, we will determine how well our suggested hybrid algorithm operates in terms of key length, key generation time, decryption and encryption timings, and overall speed. The proposed approach attains 10.3 minimal rate of error, which outperforms the existing state-of-art techniques. [ABSTRACT FROM AUTHOR]

In this paper, we introduce secure groups as a cryptographic scheme representing finite groups together with a range of operations, including the group operation, inversion, random sampling, and encoding/decoding maps. We construct secure groups from oblivious group representations combined with cryptographic protocols, implementing the operations securely. We present both generic and specific constructions, in the latter case specifically for number-theoretic groups commonly used in cryptography. These include Schnorr groups (with quadratic residues as a special case), Weierstrass and Edwards elliptic curve groups, and class groups of imaginary quadratic number fields. For concreteness, we develop our protocols in the setting of secure multiparty computation based on Shamir secret sharing over a finite field, abstracted away by formulating our solutions in terms of an arithmetic black box for secure finite field arithmetic or for secure integer arithmetic. Secure finite field arithmetic suffices for many groups, including Schnorr groups and elliptic curve groups. For class groups, we need secure integer arithmetic to implement Shanks' classical algorithms for the composition of binary quadratic forms, which we will combine with our adaptation of a particular form reduction algorithm due to Agarwal and Frandsen. As a main result of independent interest, we also present an efficient protocol for the secure computation of the extended greatest common divisor. The protocol is based on Bernstein and Yang's constant-time 2-adic algorithm, which we adapt to work purely over the integers. This yields a much better approach for multiparty computation but raises a new concern about the growth of the Bézout coefficients. By a careful analysis, we are able to prove that the Bézout coefficients in our protocol will never exceed 3 max (a , b) in absolute value for inputs a and b. We have integrated secure groups in the Python package MPyC and have implemented threshold ElGamal and threshold DSA in terms of secure groups. We also mention how our results support verifiable multiparty computation, allowing parties to jointly create a publicly verifiable proof of correctness for the results accompanying the results of a secure computation. [ABSTRACT FROM AUTHOR]

The Number Theoretic Transform (NTT) has been widely used to speed up polynomial multiplication in lattice-based post-quantum algorithms. All NTT operands use modular arithmetic, especially modular multiplication, which significantly influences NTT hardware implementation efficiency. Until now, most hardware implementations used Digital Signal Processing (DSP) to multiply two integers and optimally perform modulo computations from the multiplication product. This paper presents a customized Lattice-DSP (L-DSP) for modular multiplication based on the Karatsuba algorithm, Vedic multiplier, and modular reduction methods. The proposed L-DSP performs both integer multiplication and modular reduction simultaneously for lattice-based cryptography. As a result, the speed and area efficiency of the L-DSPs are 283 MHz for 77 SLICEs, 272 MHz for 87 SLICEs, and 256 MHz for 101 SLICEs with the parameters q of 3329, 7681, and 12,289, respectively. In addition, the N − 1 multiplier in the Inverse-NTT (INTT) calculation is also eliminated, reducing the size of the Butterfly Unit (BU) in CRYSTAL-Kyber to about 104 SLICEs, equivalent to a conventional multiplication in the other studies. Based on the proposed DSP, a Point-Wise Matrix Multiplication (PWMM) architecture for CRYSTAL-Kyber is designed on a hardware footprint equivalent to 386 SLICEs. Furthermore, this research is the first DSP designed for lattice-based Post-quantum Cryptography (PQC) modular multiplication. [ABSTRACT FROM AUTHOR]

We exhibit a randomized algorithm which, given a square matrix A ∈ C n × n with ‖ A ‖ ≤ 1 and δ > 0 , computes with high probability an invertible V and diagonal D such that ‖ A - V D V - 1 ‖ ≤ δ using O (T MM (n) log 2 (n / δ)) arithmetic operations, in finite arithmetic with O (log 4 (n / δ) log n) bits of precision. The computed similarity V additionally satisfies ‖ V ‖ ‖ V - 1 ‖ ≤ O (n 2.5 / δ) . Here T MM (n) is the number of arithmetic operations required to multiply two n × n complex matrices numerically stably, known to satisfy T MM (n) = O (n ω + η) for every η > 0 where ω is the exponent of matrix multiplication (Demmel et al. in Numer Math 108(1):59–91, 2007). The algorithm is a variant of the spectral bisection algorithm in numerical linear algebra (Beavers Jr. and Denman in Numer Math 21(1-2):143–169, 1974) with a crucial Gaussian perturbation preprocessing step. Our result significantly improves the previously best-known provable running times of O (n 10 / δ 2) arithmetic operations for diagonalization of general matrices (Armentano et al. in J Eur Math Soc 20(6):1375–1437, 2018) and (with regard to the dependence on n) O (n 3) arithmetic operations for Hermitian matrices (Dekker and Traub in Linear Algebra Appl 4:137–154, 1971). It is the first algorithm to achieve nearly matrix multiplication time for diagonalization in any model of computation (real arithmetic, rational arithmetic, or finite arithmetic), thereby matching the complexity of other dense linear algebra operations such as inversion and QR factorization up to polylogarithmic factors. The proof rests on two new ingredients. (1) We show that adding a small complex Gaussian perturbation to any matrix splits its pseudospectrum into n small well-separated components. In particular, this implies that the eigenvalues of the perturbed matrix have a large minimum gap, a property of independent interest in random matrix theory. (2) We give a rigorous analysis of Roberts' Newton iteration method (Roberts in Int J Control 32(4):677–687, 1980) for computing the sign function of a matrix in finite arithmetic, itself an open problem in numerical analysis since at least 1986. [ABSTRACT FROM AUTHOR]

Elliptic curve point multiplication is the main primitive required in almost all security schemes using elliptic curve cryptography (ECC). It is the leading computationally intensive operation that sets the overall performance of the associated cryptosystem. This work presents a highly novel area–time efficient elliptic curve point multiplier over a general prime field GF(p). It is based on an efficient radix‐23 parallel GF(p) multiplier, which performs a k‐bit GF(p) multiplication in (k3) clock cycles. On the system level, the twisted Edwards curves with unified point addition using projective coordinates are adopted, where an efficient scheduling technique is presented to schedule several GF(p) operations on deployed modular arithmetic units. Due to the introduced optimization at different stages of the design, latency, hardware resource requirement, and total clock cycle count are reduced significantly. Synthesis, and implementation of the proposed design over different Xilinx FPGA platforms are completed using the Xilinx ISE Design Suite tool for key sizes of 192, 224, and 256 bits. The 256‐bit Xilinx Virtex‐7 FPGA implementation reveals that it completes a single point multiplication operation in 0.8 ms and occupies 6.7K FPGA slices in a clock cycle count of 132.2K. It produces significantly better area–time product and throughput per slice than the contemporary designs. The proposed design also has the potential to counter simple power analysis and timing attacks. Thus, it is an elegant solution to develop ECC‐based cryptosystems for applications, where both speed and hardware resource consumption are important. [ABSTRACT FROM AUTHOR]

The Euclidean Discus Toss is an active and tactile learning activity that models the extended Euclidean algorithm with a frisbee relay. The extended Euclidean algorithm involves both iterative and recursive programming and is regularly taught throughout the mathematics and computer science curricula. The Euclidean Discus Toss invites students to toss and catch frisbees in a collaborative and hands-on effort designed to sharpen modular arithmetic skills, enhance familiarity with iterative and recursive algorithms, and strengthen classroom community. The activity is fun, low-stakes, and can be customized to meet a variety of pedagogical objectives. [ABSTRACT FROM AUTHOR]

Let (F n) n ≥ 1 be the sequence of Fibonacci numbers. For all integers a and b ≥ 1 with gcd (a , b) = 1 , let [ a - 1 mod b ] be the multiplicative inverse of a modulo b, which we pick in the usual set of representatives { 0 , 1 , ⋯ , b - 1 } . Put also [ a - 1 mod b ] : = ∞ when gcd (a , b) > 1 . We determine all positive integers m and n such that [ F m - 1 mod F n ] is a Fibonacci number. This extends a previous result of Prempreesuk, Noppakaew, and Pongsriiam, who considered the special case m ∈ { 3 , n - 3 , n - 2 , n - 1 } and n ≥ 7 . Let (L n) n ≥ 1 be the sequence of Lucas numbers. We also determine all positive integers m and n such that [ L m - 1 mod L n ] is a Lucas number. [ABSTRACT FROM AUTHOR]

LSQR represents a standard Krylov projection method for the solution of systems of linear algebraic equations, linear approximation problems or regularization of discrete inverse problem. Its convergence properties (residual norms, error norms, influence of finite precision arithmetic etc.) have been widely studied. It has been observed that the components of the solution of the projected bidiagonal problem typically increase and their sign alternates. This behavior is the core of approximation properties of LSQR and is observed also for hybrid LSQR with inner Tikhonov regularization. Here we provide rigorous analysis of sign changes and monotonicity of individual components of projected solutions and projected residuals in LSQR. The results hold also for Hybrid LSQR with a fixed inner regularization parameter. The derivations do not rely on maintaining orthogonality in Krylov bases determined by the bidiagonalization process. Numerical illustration is included. [ABSTRACT FROM AUTHOR]

In public-key cryptography, the RSA algorithm is an inevitable part of hardware security because of the ease of implementation and security. RSA Cryptographic algorithm uses many modular arithmetic operations that decide the overall performance of the architecture. This paper proposes VLSI architecture to implement an RSA public-key cryptosystem driven by the Residue Number System (RNS). Modular exponentiation in the RSA algorithm is executed by dividing the entire process into modular squaring and multiplication operations. Based on the RNS employment in modulo-exponential operation, two RSA architectures are proposed. A Verilog HDL code is used to model the entire RSA architecture and ported in Zynq FPGA (XC7Z020CLG484-1) for Proof of Concept (PoC). The Cadence Genus Synthesizer tool characterizes a system's performance for TSMCs standard Cell library. Partial RNS (Proposed-I)- and Fully RNS (Proposed-II)-based RSA architectures increase the operation speed by 13% and 35%, respectively, compared with the existing RSA. Even though there is an increase in parameters like area, power and PDP for a smaller key size, the improvement in area utilization and encryption/ decryption speed of RSA for a larger key size is evident from the analysis. [ABSTRACT FROM AUTHOR]

The modular adder, a critical arithmetic component for residue calculations, is explored in this study through its implementation on a field programmable gate array (FPGA), specifically targeting the Xilinx Zynq-7000 family device. Recent literature reveals an innovative combination of parallel prefix addition and flagged prefix addition techniques for the design of the modular adder. The parallel prefix addition, an evolution of the carry look-ahead addition, utilizes the prefix operation, whereas the flagged prefix addition generates a novel set of intermediate outputs, namely flag bits, to execute the increment operation. This paper extends this innovative combination by demonstrating the FPGA implementation of the existing design via two distinct strategies. The first strategy employs a register-transfer level (RTL) description of the design using the very high-speed integrated circuit hardware description language (VHDL), while the second strategy deploys user-defined intellectual property (IP) blocks for the design implementation. FPGA area and power reports are subsequently generated using VIVADO IDE. The RTL approach illustrates an average savings of 14.30% in slice look-up tables (LUTs) utilization and 1.91% in slice flip-flops (FFs) utilization, suggesting its superiority for applications that prioritize area-efficiency. However, the IP modeling approach emerges as crucial for managing the perpetually increasing complexity of system-on-chip (SoC) designs. [ABSTRACT FROM AUTHOR]

The use of resource-constrained devices is rising nowadays, and these devices mostly operate with sensitive data. Consequently, security is a key issue for these devices. In this paper, we propose a compact ECC (elliptic curve cryptography) architecture for resource-constrained devices based on López–Dahab (LD) projective point arithmetic operations on GF(2m). To achieve an efficient area-power hardware ECC implementation, an efficient digit-serial multiplier is developed. The proposed multiplier is built on a Bivariate Polynomial Basis representation and a modified Radix-n Interleaved Multiplication (mRnIM) method (for area and power complexities reduction). Furthermore, the LD-Montgomery point multiplication algorithm is adjusted for accurate scheduling in the compact ECC architecture to eliminate data reliance and improve signal management. Meanwhile, the area complexity is reduced by reuse of resources, and clock gating and asynchronous counter are exploited to reduce the power consumption. Finally, the proposed compact ECC architecture is implemented over GF(2m) (m = 163, 233, 283, 409, and 571) on Xilinx FPGAs' (Field-Programmable Gate Array) Virtex 5, Virtex 6, and Virtex 7, showing that the efficiency of this design outperforms to date when compared to reported works individually. It utilizes less area and consumes low power. The FPGA results clearly demonstrate that the proposed ECC architecture is appropriate for constraint-resources devices. [ABSTRACT FROM AUTHOR]