Timeline for Polynomials for the indicator function
Current License: CC BY-SA 4.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2021 at 6:57 | comment | added | Huy Le | Thank you very much for your all discussions! They are very helpful to me! | |
| Mar 3, 2021 at 14:28 | comment | added | Emil Jeřábek | Oh, I missed that the question asks about the multivariate case. But it works pretty much the same as univariate (for prime $q$): every function $(\mathbb Z/q\mathbb Z)^d\to(\mathbb Z/q\mathbb Z)$ is represented by a unique polynomial $f\in(\mathbb Z/q\mathbb Z)[t_1,\dots,t_d]$ such that $\deg_{t_i}(f)<q$ for each $i$. All other polynomials representing the same function are of the form $f+\sum_i(t_i^q-t_i)h_i(\vec t)$. For the case of $f_{t^*}$, the unique representation with $\forall i\,\deg_{t_i}<q$ is $1-\prod_i(t_i-t^*)^{q-1}$. | |
| Mar 3, 2021 at 13:57 | comment | added | reuns | @EmilJeřábek Yes obviously, thank you, the CRT only gives a polynomial function which is a unit iff $x=1$. | |
| Mar 3, 2021 at 13:53 | comment | added | Emil Jeřábek | @reuns Actually, it exists only if $q$ is prime or $1$: if $p\mid q$ is prime, then $f_0(0)\equiv1\pmod p$, hence $f_0(p)\equiv1\pmod p$. If $p<q$, then $f_0(p)\equiv0\pmod p$, a contradiction. Thus, $q=p$. | |
| Mar 3, 2021 at 11:57 | comment | added | Emil Jeřábek | Since the polynomial has $q-1$ roots, it must have degree at least $q-1$ if $q$ is prime. Moreover, there is a unique polynomial of degree $q-1$ with this property, as two polynomials represent the same function on $\mathbb Z/q\mathbb Z$ iff their difference is divisible by $x^q-x$. (Thus, the Lagrange interpolation polynomial is exactly the same as what you get from Fermat’s little theorem, only written in a more complicated way.) | |
| Mar 3, 2021 at 10:51 | comment | added | reuns | Not research level. And such a polynomial exists iff $q$ is squarefree. | |
| Mar 3, 2021 at 7:27 | history | edited | gmvh | CC BY-SA 4.0 |
Minor copyediting for language, added "polynomials" tag
|
| Mar 3, 2021 at 1:31 | comment | added | Huy Le | Thank you @DavidRoberts. | |
| Mar 3, 2021 at 1:30 | comment | added | Huy Le | Thank you @AlexM. I have just updated the question again to be clearer. | |
| Mar 3, 2021 at 1:28 | history | edited | Huy Le | CC BY-SA 4.0 |
updated the question
|
| Mar 2, 2021 at 22:19 | history | reopened |
David Roberts♦ Michael Albanese Tyrone David C Yemon Choi |
||
| Mar 2, 2021 at 8:50 | comment | added | Alex M. | In the polynomial function constructed with Lagrange's interpolation formula, you want to make sure that the denominator does not vanish, therefore $q$ should be required to be a prime. On the other hand, even the edited version of the question could be found off-topic, because it asks about "simpler" functions without defining what "simple" means, therefore leaving it as a matter of subjective opinion. | |
| Mar 2, 2021 at 8:22 | comment | added | David Roberts♦ | I see the edits, it looks like a reasonable question to me. I've voted to reopen | |
| Mar 2, 2021 at 6:23 | comment | added | Huy Le | Hope you can see my comments because my question was closed due to it seemed to be off-topic. | |
| Mar 2, 2021 at 6:21 | comment | added | Huy Le | The question is that is there any more polynomials that are simpler than those above. This question raised when I was trying to apply the idea at Section 4.2-4.3 of paper: iacr.org/archive/eurocrypt2014/84410298/84410298.pdf to the indicator function. | |
| Mar 2, 2021 at 6:21 | comment | added | Huy Le | - Using Fermat's Little Theorem: The Fermat's Little Theorem states that if $q$ is a prime number, then for any integer $a$ not divisible by $q$, the number $a^{q-1}=1 ~(\bmod q)$. Then we can construct $f_{t^*}(t)=1-(t-t^*)^{q-1}~ (\bmod q)$, if $q$ is prime. This polynomial looks simpler but may still be not helpful in case $q$ is a very big integer. | |
| Mar 2, 2021 at 6:21 | comment | added | Huy Le | - Using Lagrange Interpolation: As $t, t^* \in \mathbb{Z}_q=\{0,1, \cdots, q-1 \}$ then such a polynomial should go through the points $(0,0), (1,0), $ $\cdots, $ $(t^*-1,0), (t^*, 1), $ $(t^*+1, 0),$ $ \cdots,$ $ (q-1,0)$. We can construct $f_{t^*}(t)=\frac{t(t-1)\cdots (t-t^*+1)(t-t^*-1)\cdots (t-q+1)}{t^*(t^*-1)\cdots (t^*-t^*+1)(t^*-t^*-1)\cdots (t^*-q+1)} (\bmod q)$ via the Lagrange Interpolation method. However, the polynomial has degree of $q-1$ and looks complicated to analyze. | |
| Mar 2, 2021 at 6:20 | comment | added | Huy Le | The (one-variable) indicator function (or characteristic function) is defined as $f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisying that $f_{t^*}(t)=1$ if $t=t^*$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.) More generally, in the case of multi-variable, we define $f_{t^*}:\mathbb{Z}_q^d\to \mathbb{Z}_q$, $f_{t^*}(t_1, \cdots, t_d)=1$ if $\exists t_i$ such that $t_i=t^*$ and $f_{t^*}(t_1, \cdots, t_d)=0$, otherwise. I am finding polynomials that can be used to represent these functions. So far, I have found some for the one-variable case: | |
| Mar 2, 2021 at 6:19 | comment | added | Huy Le | @DavidRoberts, please see the updated question! Thank you very much! In case you cannot see the updated question, please see the following comments: | |
| Mar 2, 2021 at 6:19 | review | Reopen votes | |||
| Mar 2, 2021 at 22:19 | |||||
| Mar 2, 2021 at 5:59 | history | edited | Huy Le | CC BY-SA 4.0 |
I modified the question to be more mathematical and clearer.
|
| Mar 1, 2021 at 15:51 | history | closed |
Anthony Quas abx Tom De Medts Emil Jeřábek David Handelman |
Not suitable for this site | |
| Mar 1, 2021 at 7:09 | history | edited | gmvh | CC BY-SA 4.0 |
Fixed spelling in body, fixed grammar in title
|
| Mar 1, 2021 at 3:57 | comment | added | David Roberts♦ | Can you give us a bit of background on how this question arose? What sort of things do you know about it already? | |
| Mar 1, 2021 at 2:41 | review | Close votes | |||
| Mar 1, 2021 at 15:51 | |||||
| Mar 1, 2021 at 2:19 | review | First posts | |||
| Mar 1, 2021 at 7:40 | |||||
| Mar 1, 2021 at 2:11 | history | asked | Huy Le | CC BY-SA 4.0 |