LinearAlgebra[Modular] - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Modular Subpackage : LinearAlgebra/Modular/ChineseRemainder

LinearAlgebra[Modular]

 ChineseRemainder
 apply Garner's algorithm to reconstruct from mod m Matrix or Vector images

 Calling Sequence ChineseRemainder(A, m, img, prm, sto)

Parameters

 A - current reconstruction m - assigned name for prime product for reconstruction img - new image, or list of new images, mod m Matrices or Vectors) prm - new prime or list of primes sto - (optional) temporary storage (efficiency)

Description

 • The ChineseRemainder function applies an incremental version of Garner's algorithm, updating the current image A and modulus m with the image or images specified by img and prm.
 Upon successful completion, the reconstructed image is returned, and m which must be a name, is updated.
 • The A and m parameters represent the current reconstruction, and name corresponding to the current prime product.
 If no reconstruction has been performed, that is, this is the first call to ChineseRemainder for this reconstruction, A and m have the values $A=0$ and $m='n'$, where n is assigned the value 1.
 If the current reconstruction is to be updated with new images, A should be the Matrix or Vector returned from the prior call to ChineseRemainder, and $m$ should be the name used in the prior call.
 In all cases the reconstruction is returned, even though for updates to the reconstruction ChineseRemainder works on A in-place.
 • The img and prm parameters represent the new images to be used to update the reconstruction, and the corresponding primes. For updating with a single image, these can be specified as the image and prime. For updating with multiple images, these are specified as a list of the images, and a list of the corresponding primes.
 • Regardless of the datatype of the image, the output is always datatype 'integer'.
 Note: The reconstructed image is not a mod m Matrix or Vector, as it stores the entries in the symmetric range, while the input images from img are mod m Matrices or Vectors with entries in the positive range.
 • The ChineseRemainder command requires additional storage when reconstructing a result with multiple images. The ability to pre-allocate this storage and utilize it in ChineseRemainder is made available by the optional fifth argument sto. If specified, sto must be a mod m Matrix or Vector with the same datatype and dimensions as the images from img.
 • This command is part of the LinearAlgebra[Modular] package, so it can be used in the form ChineseRemainder(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][ChineseRemainder](..).

Examples

Apply Chinese remainder algorithm to a Matrix, one step at a time.

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right):$
 > $A≔\mathrm{Matrix}\left(3,4,\left(i,j\right)↦\mathrm{rand}\left(\right)\right)$
 ${A}{≔}\left[\begin{array}{cccc}{395718860534}& {193139816415}& {22424170465}& {800187484459}\\ {427552056869}& {842622684442}& {412286285840}& {996417214180}\\ {386408307450}& {694607189265}& {773012980023}& {730616292946}\end{array}\right]$ (1)

Now reconstruct A from images.

 > $\mathrm{p1}≔\mathrm{ithprime}\left(4600\right)$
 ${\mathrm{p1}}{≔}{44201}$ (2)
 > $\mathrm{I1}≔\mathrm{Mod}\left(\mathrm{p1},A,\mathrm{integer}\left[\right]\right)$
 ${\mathrm{I1}}{≔}\left[\begin{array}{cccc}{37422}& {10835}& {30743}& {29280}\\ {27165}& {15012}& {43908}& {38315}\\ {27179}& {10726}& {34438}& {18340}\end{array}\right]$ (3)
 > $m≔1$
 ${m}{≔}{1}$ (4)
 > $\mathrm{A2}≔\mathrm{ChineseRemainder}\left(0,'m',\mathrm{I1},\mathrm{p1}\right)$
 ${\mathrm{A2}}{≔}\left[\begin{array}{cccc}{-6779}& {10835}& {-13458}& {-14921}\\ {-17036}& {15012}& {-293}& {-5886}\\ {-17022}& {10726}& {-9763}& {18340}\end{array}\right]$ (5)
 > $\mathrm{p2}≔\mathrm{prevprime}\left(\mathrm{p1}\right)$
 ${\mathrm{p2}}{≔}{44189}$ (6)
 > $\mathrm{I2}≔\mathrm{Mod}\left(\mathrm{p2},A,\mathrm{integer}\left[\right]\right)$
 ${\mathrm{I2}}{≔}\left[\begin{array}{cccc}{2318}& {37641}& {20525}& {36704}\\ {17510}& {9719}& {43555}& {27637}\\ {27345}& {33131}& {43897}& {6791}\end{array}\right]$ (7)
 > $\mathrm{ChineseRemainder}\left(\mathrm{A2},'m',\mathrm{I2},\mathrm{p2}\right)$
 $\left[\begin{array}{cccc}{-780331233}& {-226784496}& {938992586}& {-623691031}\\ {-198302722}& {794351183}& {161510161}& {286239790}\\ {-324894372}& {-731294819}& {-453423621}& {120245060}\end{array}\right]$ (8)
 > $\mathrm{p3}≔\mathrm{prevprime}\left(\mathrm{p2}\right)$
 ${\mathrm{p3}}{≔}{44179}$ (9)
 > $\mathrm{I3}≔\mathrm{Mod}\left(\mathrm{p3},A,\mathrm{integer}\left[\right]\right)$
 ${\mathrm{I3}}{≔}\left[\begin{array}{cccc}{2925}& {8091}& {14540}& {29933}\\ {20810}& {19225}& {38157}& {27891}\\ {41554}& {34309}& {28397}& {27923}\end{array}\right]$ (10)
 > $\mathrm{ChineseRemainder}\left(\mathrm{A2},'m',\mathrm{I3},\mathrm{p3}\right)$
 $\left[\begin{array}{cccc}{395718860534}& {193139816415}& {22424170465}& {800187484459}\\ {427552056869}& {842622684442}& {412286285840}& {996417214180}\\ {386408307450}& {694607189265}& {773012980023}& {730616292946}\end{array}\right]$ (11)
 > $\mathrm{A2}-A,m$
 $\left[\begin{array}{cccc}{0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\end{array}\right]{,}{86290333956031}$ (12)

You can do the reconstruction all at once.

 > $m≔1$
 ${m}{≔}{1}$ (13)
 > $\mathrm{A2}≔\mathrm{ChineseRemainder}\left(0,'m',\left[\mathrm{I1},\mathrm{I2},\mathrm{I3}\right],\left[\mathrm{p1},\mathrm{p2},\mathrm{p3}\right]\right)$
 ${\mathrm{A2}}{≔}\left[\begin{array}{cccc}{395718860534}& {193139816415}& {22424170465}& {800187484459}\\ {427552056869}& {842622684442}& {412286285840}& {996417214180}\\ {386408307450}& {694607189265}& {773012980023}& {730616292946}\end{array}\right]$ (14)
 > $\mathrm{A2}-A,m$
 $\left[\begin{array}{cccc}{0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\end{array}\right]{,}{86290333956031}$ (15)

Incremental reconstruction with storage (not required for first step).

 > $m≔1$
 ${m}{≔}{1}$ (16)
 > $\mathrm{p1}≔\mathrm{prevprime}\left({2}^{25}-1\right)$
 ${\mathrm{p1}}{≔}{33554393}$ (17)
 > $\mathrm{I1}≔\mathrm{Mod}\left(\mathrm{p1},A,\mathrm{float}\left[8\right]\right)$
 ${\mathrm{I1}}{≔}\left[\begin{array}{cccc}{1.1903885}{}{{10}}^{{7}}& {730307.}& {9.835941}{}{{10}}^{{6}}& {1.5874588}{}{{10}}^{{7}}\\ {1.981263}{}{{10}}^{{6}}& {4.767426}{}{{10}}^{{6}}& {3.459049}{}{{10}}^{{6}}& {1.9514045}{}{{10}}^{{7}}\\ {2.9472055}{}{{10}}^{{7}}& {3.1254165}{}{{10}}^{{7}}& {2.0428482}{}{{10}}^{{7}}& {2.939764}{}{{10}}^{{6}}\end{array}\right]$ (18)
 > $\mathrm{A2}≔\mathrm{ChineseRemainder}\left(0,'m',\mathrm{I1},\mathrm{p1}\right)$
 ${\mathrm{A2}}{≔}\left[\begin{array}{cccc}{11903885}& {730307}& {9835941}& {15874588}\\ {1981263}& {4767426}& {3459049}& {-14040348}\\ {-4082338}& {-2300228}& {-13125911}& {2939764}\end{array}\right]$ (19)

Now use I1 as temp storage.

 > $\mathrm{p2}≔\mathrm{prevprime}\left(\mathrm{p1}\right)$
 ${\mathrm{p2}}{≔}{33554383}$ (20)
 > $\mathrm{I2}≔\mathrm{Mod}\left(\mathrm{p2},A,\mathrm{float}\left[8\right]\right)$
 ${\mathrm{I2}}{≔}\left[\begin{array}{cccc}{1.2021815}{}{{10}}^{{7}}& {787867.}& {9.842621}{}{{10}}^{{6}}& {1.6113058}{}{{10}}^{{7}}\\ {2.108683}{}{{10}}^{{6}}& {5.018546}{}{{10}}^{{6}}& {3.581919}{}{{10}}^{{6}}& {1.9810995}{}{{10}}^{{7}}\\ {2.9587205}{}{{10}}^{{7}}& {3.1461165}{}{{10}}^{{7}}& {2.0658852}{}{{10}}^{{7}}& {3.157504}{}{{10}}^{{6}}\end{array}\right]$ (21)
 > $\mathrm{ChineseRemainder}\left(\mathrm{A2},'m',\mathrm{I2},\mathrm{p2},\mathrm{I1}\right)$
 $\left[\begin{array}{cccc}{395718860534}& {193139816415}& {22424170465}& {800187484459}\\ {427552056869}& {842622684442}& {412286285840}& {996417214180}\\ {386408307450}& {694607189265}& {773012980023}& {730616292946}\end{array}\right]$ (22)
 > $\mathrm{A2}-A,m$
 $\left[\begin{array}{cccc}{0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}\end{array}\right]{,}{1125896954054519}$ (23)