3
$\begingroup$

Given an odd prime $p$, a positive integer $1 \lt n$, and an integer $x \in \mathbb{Z}/p^n\mathbb{Z}$, does there exist an an integer-coefficient polynomial that extracts the highest digit of $x$?

The extracted digit can be either $\bmod p^n$ or $\bmod p$.

  1. For example, if the result is $\bmod p^n$, $$ f(x)=x-(x\bmod {p^{n-1}})\bmod p^n. $$ This $f(x)$ actually clears the lower digits of $x$. Suppose $x=\sum_{i=0}^{n-1}x_ip^i$ where $x_i \in \mathbb{Z}/p\mathbb{Z}$ is each digit of $x$, then $f(x)$ maps $x=(x_{n-1},x_{n-2},\ldots,x_1,x_0)$ to $(x_{n-1},0,\ldots,0,0)$.

  2. If the result is $\bmod p$, then $f(x)$ maps $x=(x_{n-1},x_{n-2},\ldots,x_1,x_0)$ to $x_{n-1}$.

Does either of these polynomials $f(x)$ exist? Thanks in advance.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ The elements of ${\bf Z}/p^n{\bf Z}$ are not integers; they are cosets of the subgroup $p^n{\bf Z}$ in the group \bf{Z}. Perhaps you mean $x$ is an integer, $0\le x<p^n$. $\endgroup$
    – Gerry Myerson
    Commented Jun 27 at 0:52
  • $\begingroup$ Yes, I think $0\leq x \lt p^n$ is what I meant. The $x$ is the same as in this question, mathoverflow.net/questions/269239/… , but I wonder if there exists such $f(x)$ that extracts (or removes) the highest digit of $x$. $\endgroup$
    – fofo
    Commented Jun 27 at 0:57
  • $\begingroup$ @Kimball I don't think you can actually get "whatever you want" with integer-coefficient polynomials. For example, you can't have f(0)=f(1)=0, f(2)=1. $\endgroup$
    – Hugh Thomas
    Commented Jun 27 at 2:16
  • $\begingroup$ @Kimball, thanks for your advice. But just like Hugh Thomas says, integer-coefficient polynomials are not expressive for arbitary functions. Also, I found one report claiming that it is impossible finding such $f(x)$ which removes the lower $r$ digits for some $1\lt r \lt n$, eprint.iacr.org/2019/677.pdf. $\endgroup$
    – fofo
    Commented Jun 27 at 2:24
  • 3
    $\begingroup$ @Kimball There are functions from the set $(\mathbb{Z}/p^e\mathbb{Z})\to (\mathbb{Z}/p^e\mathbb{Z})$ that are not expressible as polynomials $\bmod p^e$. This is precisely because $\mathbb{Z}/p^e\mathbb{Z}$ is not a field. This is relevant in lattice-based cryptography (specifically "Bootstrapping for BGV/BFV-type cryptosystems"), as shown in OP's link. $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 27 at 2:52

1 Answer 1

Reset to default
1
$\begingroup$

For a polynomial $f$ with integer coefficients, $a-b$ divides $f(b) - f(a) $. Consider $a=p^{n-1}, b=a-p$. Then highest digits of $b, a$ differ modulo $p$, a contradiction. But I admit that I misundetstood the question.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your nice answer! I see that finding a $f(x)$ that directly extracts the highest digit is not feasible in this setting. Is it safe to say that removing the highest digit is just as hard as extracting the highest digit? So that no $f(x)$ can map $x=\sum_{i=0}^{n-1}x_ip^i$ to $x=(0,x_{n-2},...,x_1,x_0)$ either? $\endgroup$
    – fofo
    Commented Jun 27 at 13:27
  • 1
    $\begingroup$ The highest digit of $a$ is $1$ and of $b$ is $p-1$, so they do differ. The contradiction is that $p$ doesn't divide into $p-2$. $\endgroup$
    – Peter Taylor
    Commented Jun 27 at 13:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .