An Algorithm for Multiplication in Modular Arithmetic (Q3739192)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3972940
Language Label Description Also known as
default for all languages
No label defined
    English
    An Algorithm for Multiplication in Modular Arithmetic
    scientific article; zbMATH DE number 3972940

      Statements

      0 references
      0 references
      0 references
      0 references
      1986
      0 references
      algorithm
      0 references
      modular arithmetic
      0 references
      multiplication
      0 references
      An Algorithm for Multiplication in Modular Arithmetic (English)
      0 references
      Let n and \(\ell\) be positive integers, with \(\ell <n\), \((\ell,n)=1\), and let k be the solution of \(k\ell \equiv -1\) (mod n) with \(1\leq k<n\). It is shown that if the residues modulo n are written out in sequence \((k\ell +1)/n\) times in a \(k\times \ell\) array, then a simple reordering of the array enables the residues of multiples of \(\ell modulo n\) to be read off. Some extensions of the method, including a way of finding residues on division by \(\ell\), are given. In view of the size of the array it is difficult to see any practical utility in the method.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references