Dilip Sarwate
Reputation
1,464
Top tag
Next privilege 2,000 Rep.
 Apr 27 comment how to prove sequence y uphold golomb's third axiom You probably meant to say "for fixed integer $m$ in the range $[1,n]$". Mar 20 comment Using quadratic residue to learn the sign of a field element @fkraiem OK, in GF(7), which of the two elements $5$ and $2$ has a negative sign, and which has a positive sign? Mar 20 comment Using quadratic residue to learn the sign of a field element There are no signs in finite fields and so one cannot distinguish between $x$ and $-x$ without some context relating it some other field element. For example, $3$ is a primitive element (call it $\alpha$) in GF$(7)$ and so we can distinguish between $2 =\alpha^2$ and $-2 = 5 = \alpha^5$, but given just $\{2, 5\}$, we cannot say $x$ is $\alpha^2$ and $-x$ is $\alpha^5$ for some unspecified $\alpha$. After all, $\beta = 5$ is also a primitive element and the set $\{2,5\}$ could be $\{\beta,\beta^4\}$ instead. Mar 6 answered Non primitive lfsr sequence Feb 9 comment When all shares of a secret are given to adversary as a permuted matrix @mephisto Could you please move your discussions to chat? As the original writer of the answer, I get pinged every time one of you writes a response, and I have no interest in the issue that you are arguing about. Feb 9 comment When all shares of a secret are given to adversary as a permuted matrix @user153465 Could you please move your discussions to chat? As the original writer of the answer, I get pinged every time one of you writes a response, and I have no interest in the issue that you are arguing about. Feb 8 comment How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number? @poncho GF$(p)$ is a subfield of GF$(p^2)$ and a polynomial whose coefficients are in GF$(p)$ can be regarded as a polynomial whose coefficients are in GF$(p^2)$ if we choose to do so. No modification of any kind is needed; it is the same polynomial with same coefficients. GF$(p^2)$ also has characteristic $p$; the sum of $p$ copies of any element of GF$(p^2)$ equals $0$ (just as the sum of $p$ copies of any element of GF$(p)$ equals $0$). So, when the OP asks for solutions to $f(x) = 0\bmod p$, specifying an $x \in$ GF$(p^2)$ such that $f(x) = 0$ is a solution modulo $p$. Feb 8 comment How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number? @poncho Nobody is denying the fact that if $b^2-4ac$ does not have a square root in GF$(p)$, then the quadratic equation has no solutions in GF$(p)$; the solutions lie in GF$(p^2)$. But the standard formula does tell you what the roots are, whether in GF$(p)$ or in GF$(p^2)$, just as it does, for example, for the real polynomial $x^2+1$ whose roots are found as $$\frac{-b \pm \sqrt{b^2-4ac}}{2a} = \frac{-0 \pm \sqrt{0^2-4}}{2} = \frac{\pm 2\sqrt{-1}}{2} = \pm\sqrt{-1}.$$ In short, I don't understand the point you are trying to make, and why you think that anything I wrote above is incorrect. Feb 7 comment How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number? Yes, but the first paragraph of your answer claims that when $p$ is small, there is a root of $f(x)$ in the set $\{0,1,2, \ldots, p-1$. Or did you mean to say that $p = 3$ is far too large a value of $p$ for your method to be applicable? Feb 7 comment How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number? What if $p=3$? What is the root of $x^2+1$ that is in the set $\{0,1,2\}$? Feb 7 comment How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number? @poncho Errr no. In a finite field of characteristic $p > 2$, half the nonzero elements have square roots in the field, while the square roots of the other half lie in the extension field. For example, $1$ has square roots $\pm 1 = \{1,2\}$ in GF$(3)$ while the other nonzero element $-1 = 2$ does not have square roots in GF$(3)$, they lie in GF$(3^2)$. This is analogous to what Ricky Demer has said above; the coefficients of $x^2+1$ are in GF$(3)$ but the roots are in GF$(3^2)$ just as $x^2+1$ can be regarded as a polynomial with coefficients in $\mathbb R$ but roots in $\mathbb C$. Feb 7 comment How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number? Is there any difference between the quadratic equation mentioned in the title of your question and the equation of arbitrary degree $n$ in the text of the question? For quadratic polynomials and $p > 2$, the standard quadratic equation formula $$\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ works, but the roots might be in the extension field GF$(p^2)$. For the case $p = 2$, the standard quadratic formula cannot be used. Can you tell why? Feb 3 comment When all shares of a secret are given to adversary as a permuted matrix Even without Shamir secret sharing, permute the characters of Twitter messages "Attack at dawn" "Attack at noon" "Retreat at noon" etc and hand them over to the adversary. Jan 30 answered When all shares of a secret are given to adversary as a permuted matrix Jan 29 comment When all shares of a secret are given to adversary as a permuted matrix Does the adversary know the distribution of $\sigma$? Sep 22 awarded Yearling Sep 10 answered Reverse output of general Fibonacci LFSR Sep 7 comment How To prove Any Change to $v=a\cdot y+b$ maks $y=(a)^{−1}\cdot (v−b)$ Uni. random value Thank you for the serial down-votes on my answers on this site. Sep 7 comment How To prove Any Change to $v=a\cdot y+b$ maks $y=(a)^{−1}\cdot (v−b)$ Uni. random value This nonsensical question has been asked repeatedly in different guises on math.SE, and the OP (who apparently has several pseudonyms) insists that they are all different. In one case, in a now-deleted question on math.SE, the OP said "@DilipSarwate I posted that one too. But I was at home and I did not access to my original account . If you think I must remove it, please give me a short answer to the above question and then I will delete it. – user13676" Jun 23 awarded Caucus