Implementation of a Linear-Feedback Shift Register (LFSR) in PIL.
-
Generalize it to the setting where the taps are private inputs, so that you can generate a (zk-)STARK of a statement such as:
The output of my LFSR is X, given a (secret) configuration C and a (possibly public) inital state X_0.
-
Add a PIL constraint checking that the configuration is appropriate. That means that the period generated by the taps must be
$2^{10}-1$ . -
Generalize it to the setting were degree (number of bits) of the LFSR is chosen by the user.