evaluates pseudorandom function to find it's lfsr by use of cyclotomic polynomial Dreamed by BingAI
Sure, I will try to explain how the code works and the underlying math. The code is based on the concept of a linear-feedback shift register (LFSR), which is a type of shift register that uses a linear function of its previous state to generate a new bit and shift the register. The linear function is usually an exclusive-or (XOR) operation on some bits of the register, called taps. The taps are determined by a feedback polynomial, which is a polynomial with coefficients of 0 or 1 that represents the LFSR structure. For example, the feedback polynomial x^16 + x^14 + x^13 + x^11 + 1 means that the taps are at positions 16, 14, 13, and 11, and the new bit is the XOR of these bits. The feedback polynomial can also be written as a hexadecimal number by dropping the rightmost bit and converting the binary representation to hex. For example, x^16 + x^14 + x^13 + x^11 + 1 can be written as 0xB400.
The code defines a function called lfsr_step() that performs one step of the LFSR using the feedback polynomial 0xB400. It shifts the state of the register right by one bit, and stores the shifted-off bit as the new bit. Then, it checks if the new bit is 1, and if so, it XORs the state with the feedback polynomial. Finally, it returns the new bit.
The code also defines a function called cyclo_eval() that evaluates a cyclotomic polynomial at a given value. A cyclotomic polynomial is a polynomial that has as its roots the primitive n-th roots of unity, which are complex numbers that satisfy x^n = 1 and are not powers of any other root. For example, the cyclotomic polynomial for n = 16 is x^16 - 1, which has as its roots the 16th roots of unity: 1, -1, i, -i, sqrt(2)/2 + isqrt(2)/2, -sqrt(2)/2 - isqrt(2)/2, etc. The code uses the cyclotomic polynomial x^16 - 1, which can be written as 0x0001.
The cyclo_eval() function initializes the result as -1, and then loops over each bit of x. If the bit is 1, it adds it to the result. Then, it multiplies the result by x modulo CYCLO_POLY, which is equivalent to raising x to a power and subtracting multiples of x^16 - 1. This way, it evaluates the polynomial using Horner's method.
The code also defines a function called is_solution() that checks if a given value is a solution to the pseudorandom function. The pseudorandom function is defined as follows: given an input x, evaluate the cyclotomic polynomial at x and compare each bit of the result with a bit from the LFSR output stream. If all bits match, then x is a solution; otherwise, it is not.
The is_solution() function first evaluates the cyclotomic polynomial at x using cyclo_eval(). If the result is zero, it returns false, because zero cannot be matched with any LFSR output. Then, it loops over each bit of the result and compares it with a bit from lfsr_step(). If any bit does not match, it returns false; otherwise, it returns true.
The main loop of the code generates a random value between 0 and 65535 using random(). Then, it checks if it is a solution to the pseudorandom function using is_solution(). If so, it prints it to the serial monitor and stops the loop. Otherwise, it continues generating random values until it finds a solution or runs out of time.
The code uses some mathematical properties of LFSRs and cyclotomic polynomials to generate and check solutions. For example:
- An LFSR with an irreducible feedback polynomial will produce a maximal-length sequence of bits that cycles through all possible non-zero states before repeating. This means that for an n-bit LFSR with an irreducible feedback polynomial, there are 2^n - 1 possible outputs.
- A cyclotomic polynomial for n = 2^k will have degree 2^k and will have coefficients of only -1 and 1. This means that for n = 16, there are only two possible values for evaluating the cyclotomic polynomial: -1 or 15.
- The feedback polynomial and the cyclotomic polynomial are chosen to have certain properties that make the pseudorandom function interesting and challenging. For example, the feedback polynomial 0xB400 is irreducible, which means that it cannot be factored into smaller polynomials with integer coefficients. This ensures that the LFSR will produce a maximal-length sequence of bits that appears random and has a long period of 2^16 - 1 = 65535. The cyclotomic polynomial x^16 - 1 is also irreducible, and it has the property that its roots are the 16th roots of unity, which are complex numbers that lie on the unit circle in the complex plane. This means that evaluating the cyclotomic polynomial at a real number will always give either -1 or 15, depending on whether the number is a power of -1 or not.
- The pseudorandom function has at least one solution, because there are 2^16 possible inputs and 2^16 - 1 possible outputs from the LFSR. By the pigeonhole principle, there must be at least one input that matches one of the outputs. In fact, there may be more than one solution, depending on how many times the LFSR output repeats itself in the cycle. For example, if the LFSR output is 1010101010101010, then any even number will be a solution to the pseudorandom function. However, finding a solution may not be easy, because the LFSR output is not known in advance and may not have a simple pattern.
- There are other methods of generating pseudorandom functions, such as using hash functions, block ciphers, stream ciphers, or other mathematical functions. Each method has its own advantages and disadvantages in terms of security, efficiency, complexity, and randomness. For example, hash functions are widely used to generate pseudorandom functions that are hard to invert or predict, but they may require more computation and memory than LFSRs. Block ciphers and stream ciphers can also generate pseudorandom functions that are secure and fast, but they may require secret keys or initialization vectors that need to be shared or stored securely. Other mathematical functions may have simpler or more elegant properties than LFSRs or cyclotomic polynomials, but they may not produce sequences that are sufficiently random or long for some applications.
I hope this helps you understand how the code works and what it does. Do you have any more questions?😊 Source: Conversation with Bing, 4/14/2023(1) COS 126: Assignments (Spring 2019) - Linear-Feedback Shift Register. https://www.cs.princeton.edu/courses/archive/spr19/cos126/assignments/lfsr/index.html Accessed 4/14/2023. (2) Linear-feedback shift register - Wikipedia. https://en.wikipedia.org/wiki/Linear-feedback_shift_register Accessed 4/14/2023. (3) Tutorial: Linear Feedback Shift Registers (LFSRs) – Part 1 - EETimes. https://www.eetimes.com/tutorial-linear-feedback-shift-registers-lfsrs-part-1/ Accessed 4/14/2023. (4) What’s an LFSR? - Texas Instruments. https://www.ti.com/lit/an/scta036a/scta036a.pdf Accessed 4/14/2023. (5) COS 126: Assignments (Spring 2019) - Linear-Feedback Shift Register. https://www.cs.princeton.edu/courses/archive/spr19/cos126/assignments/lfsr/index.html Accessed 4/14/2023.