Euclidean type algorithm for the multiplication modulo P is much improved. The lower bound of the maximal step number in the former method is estimated to be Nf-1, where Nf was its upper bound formerly. So, Nf turns out to be an accurate evaluation of the maximal step number. A new method is proposed, which uses the least absolute residues. It improves the maximal step number from Nf∼logP/loglogP down to a new upper bound Nn∼(2log2P)1’/2. The decrease of step number is large for very large moduli P.
