Let's say we are given a matrix $M$ with integer entries, i.e. $M\in \mathrm{Mat}_{n\times m}(\mathbb{Z})$. For some reason, we are interested in determining the rank of this matrix over arbitrary fields $K$, which quickly boils down to determining it over $K=\mathbb{Q}$ and $K=\mathbb{F}_p$ for $p$ a prime number.
What is the most computationally efficient way to do this? (Maybe one should look on some kind of "average complexity" instead of "worst case complexity".)
The naive approach would be to compute the prime factors of all minors of $M$. The rank over $\mathbb{F}_p$ is then given by the largest $r$ so that no $r$-minor is divisible by $p$. But since the number of minors of $M$ grows quickly with its size and prime factor decomposition is also computationally expensive, this algorithm promises to be very inefficient.
I suspect this algorithm could be dramatically improved in the following way: if we had an upper bound $b$ on the prime factors appearing above, we could instead use gaussian elimination over $\mathbb{Q}$ and $\mathbb{F}_p$ for $p\leq b$ to determine the rank of $M$. The point is that for $p>b$ we will have $\mathrm{rank}_{\mathbb{F}_p}(M)=\mathrm{rank}_{\mathbb{Q}}(M)$.
A side question: Is there any kind of theorem on the relation between the prime factors of the minors, or are there matrices with arbitrary prime factor sets for their $r$-minors?
We change perspective to maps of free Abelian groups. Consider the exact sequence $$0\to \mathbb{Z}^m \xrightarrow{A\cdot } \mathbb{Z}^n \to \text{coker}\; A \to 0.$$ Since tensor product is right exact we can get the exact sequence (all the tensor products in this answer are over $\mathbb{Z}$) $$K^m \xrightarrow{A\cdot } K^n \to \text{coker}\;A\otimes K \to 0,$$ and so the rank of $A$ over the field $K$ is $n-\dim_K(\text{coker}\;A\otimes K)$.
By the classification of finitly generated Abelian groups $\text{coker}\;A \cong \mathbb{Z}^k\oplus\mathbb{Z}_{q_1}\oplus\dots\oplus\mathbb{Z}_{q_r}$ where $q_1,\dots,q_r$ are prime powers (this is called the primary decompositoin of $\text{coker}\;A$). Now, $\text{coker}\;A\otimes \mathbb{Q}\cong\mathbb{Q}^k$ and $$ \text{coker}\;A\otimes\mathbb{F}_p \cong \mathbb{F}_p^{k+a} $$ where $a$ is the number of factors with $p|q_i$.
As for computation, the primary decomposition of $\text{coker}\;A$ can be computed with the Smith normal form of $A$ which, according to this answer: https://mathoverflow.net/a/208106/88239, is of complexity $O(\Vert A\Vert\log\Vert A\Vert N4\log N)$ (I guess $N=\max{m,n}$?)