Euclidean Type Algorithm for Multiplication Modulo P II

• Kenmei, Kukihara

抄録

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.

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.

収録刊行物

• Journal of Information Processing

  Journal of Information Processing 12 (2), 147-153, 1989-08-25

  一般社団法人情報処理学会

詳細情報

• CRID: 1050001337893322752
• NII論文ID: 110002673488
• NII書誌ID: AA00700121
• ISSN: 18826652
• Web Site: http://id.nii.ac.jp/1001/00059781/
• 本文言語コード: en
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles