In this paper we extend previously known results on the complexities of normal elements. Using algorithms that exhaustively test field elements, we are able to provide the distribution of the complexity of normal elements for binary fields with degree extensions up to 39. We also provide current results on the smallest known complexity for the remaining degree extensions up to 330 by using a combination of constructive theorems and known exact values. We give an algorithm to exhaustively search field elements by using Gray codes that allows us to reuse previous computations, and compare this with the traditional method. We describe and analyze these algorithms and show both experimentally and asymptotically that the Gray code optimization gives substantial savings. The total computation of the distribution of the complexity of normal elements for degrees up to 39 in our experiments allows us to draw several conjectures. In particular, our data provides remarkable evidence for the conjecture that the complexity of normal elements follows a normal distribution. Finally, we propose that there is no linear bound on the minimum complexity with respect to the degree of the extension.
展开▼
