(field, poly)
| 26 | |
| 27 | # Alternative simplified but less efficient FFT implementation |
| 28 | def p_mod_shift(field, poly): |
| 29 | shift_poly = shift_polys[log2(len(poly))] |
| 30 | half_height = len(poly)//2 |
| 31 | low = poly[::] |
| 32 | high = [] |
| 33 | while len(high) < half_height: |
| 34 | high.insert(0, field.div(low[-1], shift_poly[-1])) |
| 35 | for i, coeff in enumerate(shift_poly[:-1]): |
| 36 | low[-half_height-1+2**i] ^= field.mul(high[0], coeff) |
| 37 | low.pop() |
| 38 | return high, low |
| 39 | |
| 40 | def fft2(field, poly): |
| 41 | # if len(poly) == 1: |