| 80 | |
| 81 | # Discrete fourier transform of A and B |
| 82 | def __dft(self, which): |
| 83 | dft = [[x] for x in self.polyA] if which == "A" else [[x] for x in self.polyB] |
| 84 | # Corner case |
| 85 | if len(dft) <= 1: |
| 86 | return dft[0] |
| 87 | next_ncol = self.c_max_length // 2 |
| 88 | while next_ncol > 0: |
| 89 | new_dft = [[] for i in range(next_ncol)] |
| 90 | root = self.root**next_ncol |
| 91 | |
| 92 | # First half of next step |
| 93 | current_root = 1 |
| 94 | for j in range(self.c_max_length // (next_ncol * 2)): |
| 95 | for i in range(next_ncol): |
| 96 | new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]) |
| 97 | current_root *= root |
| 98 | # Second half of next step |
| 99 | current_root = 1 |
| 100 | for j in range(self.c_max_length // (next_ncol * 2)): |
| 101 | for i in range(next_ncol): |
| 102 | new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]) |
| 103 | current_root *= root |
| 104 | # Update |
| 105 | dft = new_dft |
| 106 | next_ncol = next_ncol // 2 |
| 107 | return dft[0] |
| 108 | |
| 109 | # multiply the DFTs of A and B and find A*B |
| 110 | def __multiply(self): |