The number of consecutive plaintext-ciphertext pairs $(x_i,y_i)$ of bits necessary is 256 if we know the LFSR taps (equivalently: the reduction polynomial) in advance, for the reason explained in the question. 512 is when we do not, because it creates more unknowns: the coefficients of the polynomial, in addition to the initial state.
If we know the LFSR taps, the initial state is all that's unknown, and is directly given by the vector of the first 256 values of $x_i\oplus y_i$ for an LFSR in Fibonacci form (within a reflection, depending on notation). In Galois form, one option to find the initial state is to solve a system of equations.
If the LFSR taps are unknown, a standard algorithm is Berlekamp-Massey, which reconstructs the shortest LFSR state and feedback polynomial matching a given sequence of $x_i\oplus y_i$ (without taking the degree as input).
PS: I found the solution floating online, and adapted my notation to that. It is assumed that the feedback polynomial is initially unknown (or equivalently part of the key), hence the 512 pairs. The resolution is not explicitly per Berlekamp-Massey. Rather
- With the LFSR in Fibonacci form, the first 256 $x_i\oplus y_i$ give the initial internal state. The only remaining unknowns are the 256 coefficients $p_i$ of the feedback polynomial.
- These 256 remaining unknowns are found by solving a system of 256 equations with 256 unknowns, built using the 512 $x_i\oplus y_i$. That system states that the internal state evolves from the first 256 $x_i\oplus y_i$ to the next 256 $x_i\oplus y_i$ after 256 steps with the reduction polynomial defined by the $p_i$.
