Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ- φ2.Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that qs can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about rithm. In addition, an effective algorithm is provided for finding such integer s.