Euclidean Type Algorithm for Multiplication Modulo PII

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 N_f-1, where N_f was its upper bound formerly. So, N_f turns out to be an accurate evaluation of the maximal step number. A new method is proposed, which uses the least absolute residues. lt improves the maximal step number from N_f-log P/log log P down to a new upper bound N_n-(2log2 P)^<1/(2)>. The decrease of step number is large for very large moduli P.