This paper presents a new sliding window algorithm that is well-suited to an elliptic curve defined over an extension field for which the Frobenius map can be computed quickly, e.g., optimal extension field. The algorithm reduces elliptic curve group operations by approximately 15% for scalar multiplications for a practically used curve in comparison with Lim-Hwang's results presented at PKC2000, the fastest previously reported. The algorithm was implemented on computers. As a result, scalar multiplication can be accomplished in 573μs, 595μs, and 254μs on Pentium II (450 MHz), 21164A (500 MHz), and 21264 (500 MHz) computers, respectively.