ﻻ يوجد ملخص باللغة العربية
It is known that any $n$-variable function on a finite prime field of characteristic $p$ can be expressed as a polynomial over the same field with at most $p^n$ monomials. However, it is not obvious to determine the polynomial for a given concrete function. In this paper, we study the concrete polynomial expressions of the carries in addition and multiplication of $p$-ary integers. For the case of addition, our result gives a new family of symmetric polynomials, which generalizes the known result for the binary case $p = 2$ where the carries are given by elementary symmetric polynomials. On the other hand, for the case of multiplication of $n$ single-digit integers, we give a simple formula of the polynomial expression for the carry to the next digit using the Bernoulli numbers, and show that it has only $(n+1)(p-1)/2 + 1$ monomials, which is significantly fewer than the worst-case number $p^n$ of monomials for general functions. We also discuss applications of our results to cryptographic computation on encrypted data.
Let $mathbb{F}_p$ be the finite field of prime order $p$. For any function $f colon mathbb{F}_p{}^n to mathbb{F}_p$, there exists a unique polynomial over $mathbb{F}_p$ having degree at most $p-1$ with respect to each variable which coincides with $f
Let $mathcal{T}^{(p)}_n$ be the set of $p$-ary labeled trees on ${1,2,dots,n}$. A maximal decreasing subtree of an $p$-ary labeled tree is defined by the maximal $p$-ary subtree from the root with all edges being decreasing. In this paper, we study a
Let f be a function mapping an n dimensional vector space over GF(p) to GF(p). When p is 2, Bernasconi et al. have shown that there is a correspondence between certain properties of f (e.g., if it is bent) and properties of its associated Cayley grap
Outsourcing neural network inference tasks to an untrusted cloud raises data privacy and integrity concerns. To address these challenges, several privacy-preserving and verifiable inference techniques have been proposed based on replacing the non-pol
A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $min {{rm deg}_G(x), {rm deg}_G(y)}$ vertex(edge)-disjoint paths between $x$ and $y$. In this paper, we consider strong Menger (