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
1986
0 references
algorithm
0 references
modular arithmetic
0 references
multiplication
0 references
An Algorithm for Multiplication in Modular Arithmetic (English)
0 references
0.8070654273033142
0 references
0.7498441934585571
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