Search

A novel quantum-safe key encapsulation algorithm, called Multivariate Polynomial Public Key (MPPK), was recently proposed by Kuang, Perepechaenko, and Barbeau. Security of the MPPK key encapsulation mechanism does not rely on the prime factorization or discrete logarithm problems. It builds upon the NP-completeness of the modular Diophantine equation problem, for which there are no known efficient classical or quantum algorithms. Hence, it is resistant to known quantum computing attacks. The private key of MPPK comprises a pair of multivariate polynomials. In a companion paper, we analyzed the performance of MPPK when these polynomials are quadratic. The analysis highlighted the MPPK high decapsulation time. We found that, while maintaining the security strength, the polynomials can be linear. Considerable performance gains are obtained for the decapsulation process. In this article, we benchmark the linear case and compare the results with the previous quadratic case. [ABSTRACT FROM AUTHOR]

The binary signed-digit (BSD) representation of integers is used for efficient integer computation in various settings. The Stern polynomial is a polynomial extension of the well-studied Stern diatomic sequence. In this paper, we show previously unknown connections between BSD integer representations and the Stern polynomial. We then exploit these connections to devise a fast algorithm to count optimal BSD representations on a range of integers and calculate their weights. [ABSTRACT FROM AUTHOR]

In this paper, we develop the theoretical provisions of symmetric cryptographic algorithms based on the polynomial residue number system for the first time. The main feature of the proposed approach is that when reconstructing the polynomial based on the method of undetermined coefficients, multiplication is performed not on the found base numbers but on arbitrarily selected polynomials. The latter, together with pairwise coprime residues of the residue class system, serve as the keys of the cryptographic algorithm. Schemes and examples of the implementation of the developed polynomial symmetric encryption algorithm are presented. The analytical expressions of the cryptographic strength estimation are constructed, and their graphical dependence on the number of modules and polynomial powers is presented. Our studies show that the cryptanalysis of the proposed algorithm requires combinatorial complexity, which leads to an NP-complete problem. [ABSTRACT FROM AUTHOR]

This paper presents the generalized Pell p-numbers and provides some related results. A new sequence is defined using the characteristic polynomial of the Pell p-numbers and generalized Mersenne numbers. Two algorithms for Diffie-Hellman key exchange are given as an application of these sequences. They are illustrated via numerical examples and shown to be secure against attacks. Thus, these new sequences are practical for encryption and constructing private keys. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

Detecting the cosmic 21 cm signal from epoch of reionization has always been a difficult task. Although the Galactic foreground can be regarded as a smooth power-law spectrum, due to the chromaticity of the antenna, additional structure will be introduced into the global spectrum, making the polynomial fitting algorithm perform poorly. In this paper, we introduce an improved polynomial fitting algorithm – the Vari-Zeroth-Order Polynomial (VZOP) fitting and use it to fit the simulation data. This algorithm is developed for the upcoming low-frequency anechoic chamber experiment, yet it is a general method suitable for application in any single antenna-based global 21 cm signal experiment. VZOP defines a 24-h averaged beam model that brings information about the antenna beam into the polynomial model. Assuming that the beam can be measured, VZOP can successfully recover the 21 cm absorption feature, even if the beam is extremely frequency-dependent. In real observations, due to various systematics, the corrected measured beam contains residual errors that are not completely random. Assuming the errors are frequency-dependent, VZOP is capable of recovering the 21 cm absorption feature even when the error reaches 10 per cent. Even in the most extreme scenario where the errors are completely random, VZOP can at least give a fitting result that is not worse than the common polynomial fitting. In conclusion, the fitting effect of VZOP depends on the structure of the error and the accuracy of the beam measurement. [ABSTRACT FROM AUTHOR]

Discrete orthogonal polynomials (DOPs) have gained significant research attention owing to their crucial role in digital signal processing applications such as computer vision, pattern recognition, and compression. However, the computation of DOP coefficients often incurs a substantial computational burden, exacerbating for higher-degree moments along with the resulting numerical errors. To address this challenge, this paper exploits the inherent parallelism in Charlier polynomial coefficient calculations to achieve enhanced polynomial performance. Independent calculations are distributed among threads, making efficient use of the available processing resources. Two algorithms are presented, the first algorithm evenly distributes the rows in a sequential manner (straightforward). Additionally, to achieve a more equitable distribution of coefficient calculations, this paper proposes alternative distribution approaches, aimed at balancing processing load among threads. Through extensive comparative experiments, we have confirmed that the proposed approaches achieved high performance across different degrees (1540 to 7370) and at different numbers of threads (2 to 256). The results show processing time in the multithreaded case is improved by up to 9.1 times with respect to the unthreaded case. Furthermore, by increasing the number of threads from 2 to 256, the trend indicates that the most significant improvement occurs in the range of 32 to 128 threads, confirming the robustness of the proposed algorithm. These findings signify the importance of this paper. [ABSTRACT FROM AUTHOR]

We develop the first algorithm for computing rational solutions of scalar integro-differential equations with polynomial coefficients. It starts by finding the possible poles of a rational solution. Then, bounding the order of each pole and solving an algebraic linear system, we compute the singular part of rational solutions at each possible pole. Finally, using partial fraction decomposition, the polynomial part of rational solutions is obtained by computing polynomial solutions of a non-homogeneous scalar integro-differential equation with a polynomial right-hand side. The paper is illustrated by examples where the computations are done with our Maple implementation. [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

In recent years, various smart devices based on IoT technology, such as smart homes, healthcare, detection, and logistics systems, have emerged. However, as the number of IoT-connected devices increases, securing the IoT is becoming increasingly challenging. To tackle the increasing security challenges caused by the proliferation of IoT devices, this research proposes an innovative method for IoT identity authentication. The method is based on an improved ring-learning with errors (R-LWE) algorithm, which encrypts and decrypts communication between devices and servers effectively using polynomial modular multiplication and modular addition operations. The main innovation of this study is the improvement of the traditional R-LWE algorithm, enhancing its efficiency and security. Experimental results demonstrated that, when compared to number theory-based algorithms and elliptic curve cryptography algorithms at a 256-bit security level, the enhanced algorithm achieves significant advantages. The improved algorithm encrypted 20 data points with an average runtime of only 3.6 ms, compared to 7.3 ms and 7.7 ms for the other algorithms. Similarly, decrypting the same amount of data had an average runtime of 2.9 ms, as opposed to 7.3 ms and 8 ms for the other algorithms. Additionally, the improved R-LWE algorithm had significant advantages in terms of communication and storage costs. Compared to the number theory-based algorithm, the R-LWE algorithm reduced communication and storage costs by 3 °C each, and compared to elliptic curve cryptography, it reduced them by 4 °C each. This achievement not only enhances the efficiency of encryption and decryption but also lowers the overall operational costs of the algorithm. The research has made significant strides in improving the security and efficiency of IoT device identity authentication by enhancing the R-LWE algorithm. This study provides theoretical and practical foundations for the development and application of related technologies, as well as new solutions for IoT security. [ABSTRACT FROM AUTHOR]

Since Coppersmith proposed the use of the LLL algorithm to solve univariate modular polynomial equations at EUROCRYPT'96, it has sparked a fervent research interest in lattice analysis among cryptographers. Despite its polynomial-time nature, the LLL algorithm exhibits a high-order polynomial upper bound in terms of theoretical complexity, particularly with longer computation times when applied to high-dimensional lattices. In addressing this issue, we propose an improved algorithm based on block preprocessing, building on the original Coppersmith algorithm and thus providing proof of correctness for this algorithm. This approach effectively reduces the solution time of the algorithm, offering a maximum improvement of 8.1% compared to the original Coppersmith algorithm. Additionally, we demonstrate the compatibility of our algorithm with the rounding algorithm proposed at PKC 2014. The combined utilization of these approaches further enhances the efficiency of our algorithm. The experimental results show that the combined algorithm achieves a maximum improvement of 22.4% in solution time compared to the original Coppersmith algorithm. It also outperforms the standalone rounding algorithm with a maximum improvement of 12.1%. When compared to the improved Coppersmith algorithm based on row common factor extraction, our proposed algorithm demonstrates comparable or even superior performance in certain dimensions. The block preprocessing algorithm in our approach enables independent execution without data exchange, making it suitable for leveraging multi-processing advantages in scenarios involving higher degrees of modular polynomial equations. This offers a new perspective for achieving the parallel computation of the Coppersmith algorithm, facilitating parallel execution and providing valuable insights. [ABSTRACT FROM AUTHOR]

A spectral collocation-based approximate algorithm is adapted for the numerical evaluation of a class of fractional-order delay differential equations. The involved fractional operators are defined as the Caputo-Fabrizio and Liouville-Caputo derivatives. A novel family of polynomials called Narayana polynomials and their generalization forms are utilized in our collocation procedure. We study the convergent analysis of the Narayana polynomials in a weighted L2 norm and obtain an upper bound for their series expansion form. The performance of the present matrix collocation is justified by solving three test examples using both fractional operators and various fractional orders. The outcomes are compared with two existing numerical approaches, i.e., the modified operational matrix method (MOMM) and the operational matrix of integration relied on Taylor bases (OMTB). A comparison study reveals that our results are more accurate than these two methods and thus the presented matrix algorithm is superior in terms of efficacy and applicability. [ABSTRACT FROM AUTHOR]