An Algorithm to Solve the Congruence Equation AX B (Mod M) Using Only Multiplications Mod M

Hatsukazu TANAKA  Seiko KANEKU  

IEICE TRANSACTIONS (1976-1990)   Vol.E60   No.10   pp.551-551
Publication Date: 1977/10/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Computers

Full Text: PDF(71.5KB)>>
Buy this Article

An algorithm is presented to solve the congruence equation of the type AX B (mod M) using Fermat's theorem, where M is any prime. It uses only integer multiplication mod M. If p is an integer such that 2p11M2p1, and M3 or p3, the number N of necessary multiplications mod M satisfies p1N2p2.