In this paper, we propose a new pseudo random binary sequence generated from a primitive polynomial over an extension field. The sequence has maximum period and high linear complexity suitable for security applications. While generation, a new mapping function is proposed which is faster than conventional trace map and translates extension field elements to prime field elements. The output of mapping function is a p-ary sequence with elements 0~ (p-1) that is balanced in pattern distribution and has ideal autocorrelation. Then, a binarization method is utilized to derive binary sequence from p-ary sequence. Period, autocorrelation, linear complexity and computation time of the proposed sequence are studied and experimental results are presented. Finally, the efficiency of the proposal is verified by comparing with existing sequences in terms of period, linear complexity and generation time for sequences of different length.