Modular System of Linear Equation Solver (MLE)

If \(a, b\), and \(n\) are integer vectors, this function tries to find, at each coordinate, the solution of the MLE \(a x = b \ mod \ n\). If the MLE \(a x = b \ mod \ n\) has no solution for some coordinate (see modlin), the value reported for that coordinate will be no.sol, and a corresponding translation vector will also be returned.

Usage

modlineq(a, b, n, no.sol = 0L)

Arguments

a

An integer or a vector of integers.

b

An integer or a vector of integers.

n

An integer or a vector of integers.

no.sol

Values to return when the equation is not solvable or yield the value 0. Default is 0.

Value

If the solution is exact, then a numerical vector will be returned, otherwise, if there is no exact solution for some coordinate, a list carrying the element on the diagonal matrix and a translation vector will be returned.

Details

For \(a, b\), and \(n\) integer scalars, it is just a wrapper function to call modlin.

Examples

## Set the vector x, y, and m.
x <- c(9,32,24,56,60,27,28,5)
y <-  c(8,1,0,56,60,0,28,2)
modulo <- c(64,125,64,64,64,64,64,64)

## Try to solve the modular equation a x = b mod n
m <- modlineq(a = x, b = y, n = modulo)
m
#> [1]  8 43  0  1  1  0  1 26

## Or in matrix form 
diag(m)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    8    0    0    0    0    0    0    0
#> [2,]    0   43    0    0    0    0    0    0
#> [3,]    0    0    0    0    0    0    0    0
#> [4,]    0    0    0    1    0    0    0    0
#> [5,]    0    0    0    0    1    0    0    0
#> [6,]    0    0    0    0    0    0    0    0
#> [7,]    0    0    0    0    0    0    1    0
#> [8,]    0    0    0    0    0    0    0   26

## The reverse mapping is an affine transformation
mt <- modlineq(a = y, b = x, n = modulo, no.sol = 1L)
mt
#> $diag
#> [1]  1 32  1  1  1  1  1  1
#> 
#> $translation
#> [1]  1  0 24  0  0 27  0  3
#> 

## That is, vector 'x' is recovered with the transformation
(y %*% diag(mt$diag) + mt$translation) %% modulo
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    9   32   24   56   60   27   28    5

# Or
cat("\n---- \n")
#> 
#> ---- 

(y %*% diag(mt$diag) + mt$translation) %% modulo == x
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE