This paper describes the designation and structure of S-boxes which are the fundament of the Rijndael algorithm and finds the optimization of them using four kinds of testing methods. Firstly, it constructs different S-boxes by Matlab using 30 irreducible polynomials the maximum power of which is eight in a finite field. Through taking their performance analysis, we find that they have the similar performances in differential testing and linear or correlation testing. But in avalanche testing and Boolean expressions testing, the S-boxes which are constructed by No. 9 and No. 18 irreducible polynomial are optimal structure respectively.