对于矩阵 \( A \)、\( b \) 和整数解 \( x \) 都为整数的积分线性系统 \( Ax = b \)，可通过计算 \( A \) 的不变因子（即其Smith标准型）进行求解。本文探讨了一种在实际应用中出现的新问题，即在给定 \( A, b \in \zz_n \) 的情况下，研究如何在 \( x \in \zz_n \) 中求解模线性系统 \( Ax = b \rem n \) 并附加约束条件：线性函数 \( \phi(x) = \langle w, x \rangle \) 的值与 \( n \) 互质。本文提出将系统分解为互素模数 \( p^{r(p)} \)（这些模数是 \( n \) 的因子），并展示这种分解如何简化Smith标准型的计算。这种方法将著名的指数演算法推广到模数因子为素数幂 \( p^{r(p)} \) 的情况，而指数演算法原本假设模数为素数（用于求解素域上的简化系统）。本文还展示了如何利用增广矩阵 \( [A, -p^{r(p)}I] \) 的不变因子和Smith标准型以及 \( w \) 模 \( p \) 的条件高效地解决该问题，其中 \( p^{r(p)} \) 取遍 \( n \) 的所有素数因子的幂。

Integral linear systems $Ax=b$ with matrices $A$, $b$ and solutions $x$ are also required to be in integers, can be solved using invariant factors of $A$ (by computing the Smith Canonical Form of $A$). This paper explores a new problem which arises in applications, that of obtaining conditions for solving the Modular Linear System $Ax=b\rem n$ given $A,b$ in $\zz_n$ for $x$ in $\zz_n$ along with the constraint that the value of the linear function $\phi(x)=\la w,x\ra$ is coprime to $n$ for some solution $x$. In this paper we develop decomposition of the system to coprime moduli $p^{r(p)}$ which are divisors of $n$ and show how such a decomposition simplifies the computation of Smith form. This extends the well known index calculus method of computing the discrete logarithm where the moduli over which the linear system is reduced were assumed to be prime (to solve the reduced systems over prime fields) to the case when the factors of the modulus are prime powers $p^{r(p)}$. It is shown how this problem can be addressed effciently using the invariant factors and Smith form of the augmented matrix $[A,-p^{r(p)}I]$ and conditions modulo $p$ satisfied by $w$, where $p^{r(p)}$ vary over all divisors of $n$ with $p$ prime.