Timeline for Does there exist a polynomial that extracts the highest digit of an integer in base p?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27 at 20:51 | history | edited | Michael Hardy | CC BY-SA 4.0 |
edited title
|
| Jun 27 at 7:59 | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
fix misleading formatting
|
| Jun 27 at 4:56 | answer | added | Fedor Petrov | timeline score: 1 | |
| Jun 27 at 4:44 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Minor Math Jaxing and formatting
|
| Jun 27 at 3:42 | comment | added | fofo | @Mark Schultz-Wu Thanks for your explanation. The $f(x)$ in the link is indeed constructed for the bootstrapping in BGV (specifically for the digit removal). By extending the proof offered by Michael Griffin in that post, if we want to extract the highest digit by removing the lowest $n-1$ digits, the degree of polynomial will be rather high and the coefficient will not strictly be integers. I am not sure if there are other ways to construct an integer-polynomial that maps $(x_{n-1},x_{n-2},...,x_1,x_0)$ to $(x_{n-1},0,...,0,0)$ or $(0,x_{n-2},...,x_1,x_0)$ or just simply $x_{n-1}$. | |
| Jun 27 at 3:40 | comment | added | Kimball | @HughThomas Ah right, I wasn't restricting to polynomials/$\mathbb Z$. | |
| S Jun 27 at 3:18 | history | suggested | Mark Schultz-Wu | CC BY-SA 4.0 |
small formatting changes
|
| Jun 27 at 3:15 | review | Suggested edits | |||
| S Jun 27 at 3:18 | |||||
| Jun 27 at 2:56 | comment | added | Mark Schultz-Wu | @Kimball See for example Kempner's Polynomials and their Residue Systems for some (admittedly more mathematically precise than the current question) exposition on this. | |
| Jun 27 at 2:52 | comment | added | Mark Schultz-Wu | @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. | |
| Jun 27 at 2:24 | comment | added | fofo | @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. | |
| Jun 27 at 2:16 | comment | added | Hugh Thomas | @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. | |
| Jun 27 at 0:57 | comment | added | fofo | 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$. | |
| Jun 27 at 0:52 | comment | added | Gerry Myerson | 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$. | |
| S Jun 26 at 23:18 | review | First questions | |||
| Jun 27 at 4:44 | |||||
| S Jun 26 at 23:18 | history | asked | fofo | CC BY-SA 4.0 |