Timeline for # roots of polynomials over GF(2)
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2014 at 23:37 | comment | added | Greg Martin | Note also that a random polynomial with coefficients in $GF(2)$ might act very differently, with respect to its number of roots in $GF(2^m)$, from a random polynomial with coefficients in $GF(2^m)$ itself. For example, Emil pointed out that every degree-$d$ polynomial with coefficients in $GF(2)$ has $d$ roots in $GF(2^{d!})$. But the average number of roots in $GF(2^{d!})$ of a degree-$d$ polynomial with coefficients in $GF(2^{d!})$ itself is exactly $1$, as you can see by varying only the constant coefficient for each input. | |
| Mar 17, 2014 at 22:54 | comment | added | Emil Jeřábek | Also, these polynomials do not at all behave like random functions on $\mathbb F_{2^m}$: they are uniquely determined by their values on any $(d+1)$-element subset of $\mathbb F_{2^m}$, and they commute with the Frobenius automorphism $x\mapsto x^2$. | |
| Mar 17, 2014 at 22:48 | history | edited | David Harris | CC BY-SA 3.0 |
Clarify size of $d$
|
| Mar 17, 2014 at 22:43 | comment | added | Emil Jeřábek | That is to say, the magnitude of $m$ by itself does not say much. If $m$ is divisible by $d!$, every such $p$ will split in $\mathbb F_{2^m}$, whereas if $m$ is a large prime, $p$ will have no more roots than it already had in $\mathbb F_2$. | |
| Mar 17, 2014 at 22:34 | comment | added | Emil Jeřábek | Write $p=\prod_{i<k}p_i$ where the $p_i$ are irreducible, of degrees $d_i=\deg(p_i)$. If $d_i\mid m$, then $p_i$ has $d_i$ roots in $\mathbb F_{2^m}$, otherwise it has no roots. | |
| Mar 17, 2014 at 22:29 | history | asked | David Harris | CC BY-SA 3.0 |