Polynomials

An efficient scalar multiplication algorithm is vital for elliptic curve cryptosystems. The first part of this dissertation focuses on a scalar multiplication algorithm based on scalar recodings resistant to timing attacks. The algorithm utilizes two recoding methods: Recode, which generalizes the non-zero signed all-bit set recoding, and Align, which generalizes the sign aligned columns recoding. For an ℓ-bit scalar split into d subscalars, our algorithm has a computational cost of ⌈⌈ℓ logk(2)⌉/d⌉ point additions and k-scalar multiplications and a storage cost of kd−1(k − 1) – 1 points on E. The “split and comb” method further optimizes computational and storage complexity. We find the best setting to be with a fixed base point on a Twisted Edwards curve using a mix of projective and extended coordinates, with k = 2 generally offering the best performance. However, k = 3 may be better in certain applications. The second part of this dissertation is dedicated to constant-time polynomial inversion algorithms in Post-Quantum Cryptography (PQC). The computation of the inverse of a polynomial over a quotient ring or finite field is crucial for key generation in post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. Efficient algorithms must run in constant time to prevent side-channel attacks. We examine constant-time algorithms based on Fermat’s Little Theorem and the Extended GCD Algorithm, providing detailed time complexity analysis. We find that the constant-time Extended GCD inversion algorithm is more efficient, performing fewer field multiplications. Additionally, we explore other exponentiation algorithms similar to the Itoh-Tsuji inversion method, which optimizes polynomial multiplications in the BIKE/LEDACrypt setup. Recent results on hardware implementations are also discussed.

The purpose of this thesis is to provide complete
proofs for several results on integral-valued polynomials,
which are used in Serre's proof of Hilbert's Theorem
found in the theory of characteristic polynomials. These
results, however elementary, are not found in the
literature.
The proof of Hilbert's Theorem is also given.

Two algorithms for greatest common factor (GCF) extraction
from two multivariable polynomials, based on
generalized Pade approximation, are presented. The reduced
transfer matrices for two-dimensional (20) systems are
derived from two 20 state-space models. Tests for product
and sum separabilities of multivariable functions are also
given.

We present several results involving three concepts: Prufer domains, the strong 2-generator property, and integer-valued polynomials. An integral domain D is called a Prufer domain if every nonzero finitely generated ideal of D is invertible. When each 2-generated ideal of D has the property that one of its generators can be any arbitrary selected nonzero element of the ideal, we say D has the strong 2-generator property . We note that, if D has the strong 2-generator property, then D is a Prufer domain. If Q is the field of fractions of D, and E is a finite nonempty subset of D; we define Int(E, D ) = {f(X) ∈ Q[ X] ∣ f(a) ∈ D for every a ∈ E} to be the ring of integer-valued polynomials on D with respect to the subset E. We show that D is a Prufer domain if and only if Int(E, D) is a Prufer domain. Our main theorem is that Int(E, D) has the strong 2-generator property if and only if D is a Bezout domain (that is, every finitely generated ideal of D is principal).

Let D be an integral domain with field of fractions K, and let E be a nonempty finite subset of D. For n > 2, we show that the n-generator property for D is equivalent to the n-generator property for Int(E, D), which is equivalent to strong (n + 1)-generator property for Int(E, D). We also give necessary and sufficient conditions that the pullback of a conductor square be a chain ring (that is, a ring whose ideals are totally ordered by inclusion), and we give necessary and sufficient conditions that the pullback of a conductor square be an arithmetical ring (that is, a ring which is locally a chain ring at every maximal ideal). We characterize all Prufer domains R between D[X] and K[X]such that the conductor C of K[X] into R is non-zero. As an application, we show that for n > 2, such a ring R has the n-generator property (every finitely generated ideal can be generated by n elements) if and only if R/C has the same property.

For D an integral domain with field of fractions K and E a subset of K, the ring Int (E,D) = {f e K[X]lf (E) C D} of integer-valued polynomials on E has been well studies. In particulare, when E is a finite subset of D, Chapman, Loper, and Smith, as well as Boynton and Klingler, obtained a bound on the number of elements needed to generate a finitely generated ideal of Ing (E, D) in terms of the corresponding bound for D. We obtain analogous results for Int (r) (E, D) - {f e K [X]lf(k) (E) c D for all 0 < k < r} , for finite E and fixed integer r > 1. These results rely on the work of Skolem [23] and Brizolis [7], who found ways to characterize ideals of Int (E, D) from the values of their polynomials at points in D. We obtain similar results for E = D in case D is local, Noetherian, one-dimensional, analytically irreducible, with finite residue field.

Let D be an integral domain and f a polynomial that is integer-valued on D. We prove that Int(f(D);D) has the Skolem Property and give a description of its spectrum. For certain discrete valuation domains we give a basis for the ring of integer-valued even polynomials. For these discrete valuation domains, we also give a series expansion of continuous integer-valued functions.