Is there a method to calculate large number modulo? 
Is there a (number theoretic or algebraic) trick to find a large
  nunber modulo some number?

Say I have the number $123456789123$ and I want to find its value modulo some other number, say, $17$.
It's not fast for me to find the prime factorisation first. It's also not fast to check how many multiples of $17$ I can "fit" into the large number. 
So I was wondering if there is any method out there to do this efficiently. 

I am looking for something like the other "magic trick" where you sum
  all the digits and take the result $\mod 9$. 

 A: $10^2\equiv-2\pmod{17}\implies10^4=(10^2)^2\equiv(-2)^2\equiv4;$
$\displaystyle\implies\sum_{r=0}^na_r10^r\equiv(4)^0(a_3a_2a_1a_0)+(4)^1(a_7a_6a_5a_4)++(4)^2(a_{11}a_{10}a_9a_8)+\cdots\pmod{17}$
Again, $10^8\equiv(-2)^4\equiv-1$
$\displaystyle\implies\sum_{r=0}^na_r10^r\equiv(-1)^0(a_7a_6a_5\cdots a_0)+(-1)^1(a_{15}\cdots a_8)+\cdots\pmod{17}$
A: Well, it is fast
to divide 17 into that number.
Where you can gain a lot
is when the number
you want to be divide
is a special form
such as $a^n$,
where $n$ is large.
There are ways
(usually involving the
Euler $\phi$ function)
for rapidly computing
$a^n \bmod{b}$
where $n$ is large.
A good start is to remember that
$a^n \bmod{b}
=(a\bmod{b})^n \bmod{b}
$.
A: Yes, use the universal divisibility test: $ $ repeatedly replace leading digit chunks by their remainder mod the divisor as below, using least magnitude remainders $\, -8\le r \le 9\,$ to simplify arithmetic $\!\bmod 17\ $  (so negative digits occur, denoted $-d,c := 10(-d)+c\equiv 7d+c,\,$ by $10\equiv -7)$
$$\begin{align}
 \!\bmod 17\!:\,\ 10\equiv -7\ \Rightarrow\quad\ \  &\ \color{#0A0}{1\ 2}\,\ 3\ 4\ 5\ 6\ \ \ {\rm by}\,\ \ \ \ \ \ \color{#0a0}{1\:\!2\equiv -5}\\[.1em]
\equiv\, &\ \color{#0A0}{{-5}},\color{#c00} 3\ 4\ 5\ 6\ \ \ {\rm by}\,\ \color{#0a0}{{-}5},\color{#c00}3\equiv\  (\,7\,)\,
 \color{#0a0}{5}+\color{#c00}3\,\equiv\,\color{#0af} 4\\[.1em]
\equiv\, &\ \ \ \ \ \ \ \ \color{#0af}4\ 4\ 5\ 6\ \ \ {\rm by}\,\ \ \ \ \ \ \color{#0af}4\:\!4\equiv (-7)4+4\,\equiv\color{#f60}{-7}\\[.1em]
\equiv\, &\ \ \ \ \ \ \ \  \color{#f60}{{-}\!7}, 5\ 6\ \ \ {\rm by}\,\  \color{#f60}{{-}7},5\equiv\,(\,7\,)\, \color{#f60}{7}+5\,\equiv\, 3\\[.2em]
\equiv\, &\ \ \ \ \ \ \ \ \ \ \ \ \ \ 3\ 6\ \ \ \:\!\:\!{\rm by}\ \  \ \ \ \ 3\:\! 6\equiv (-7)3+6\,\equiv\, 2\\
\equiv\, &\qquad\qquad\ 2;\ \ {\bf Quicker,}\,\ 2 \,\text{ digits at a time:}\\[.4em]
 \!\bmod 17\!:\,\ 10^2\equiv -2\ \Rightarrow\quad\ \  &\ \color{#0A0}{12\ 3 4}\ 56\ \ \ {\rm by}\,\  \color{#0A0}{12\ 3 4}\equiv\, (-2)\color{#0a0}{\,12+34\equiv 10}\\[.1em]
\equiv\, &\ \ \ \ \ \ \color{#0A0}{{10}}\ \color{#c00}{56}\ \ \ {\rm by}\,\ \color{#0a0}{10}\ \color{#c00}{56}\equiv\  (-2)\,
 \color{#0a0}{10}+\color{#c00}{56}\,\equiv\,\color{#0af}2\\[.2em]
\equiv\, &\qquad\quad\   \color{#0af}2
\end{align}\qquad\qquad$$
So $\rm\, 123456\equiv 2\pmod{\!17}.\,$ Indeed $\rm\, 123456 = 7262\cdot 17+2.\,$ Continuing this way we can do the entire number in a couple minutes of mental arithmetic. Unlike some other divisibility tests that compute only a binary truth value, this method has the advantage of computing the remainder. Further, it doesn't require remembering any special algorithm or parameters for each modulus.
Remark $ $ Lab & Steven's answers are a special case of above (but without mod arithmetic optimizations), i.e. they use chunk sizes of $\,2\,$ and $\,8,\,$ using $\bmod 17\!:\ 10^2\equiv -2,\ 10^8\equiv -1$.
A: No, there is not. The reason why "magic tricks" work when studying divisibility by $2,3,5,11$ is the fact that we usually write in base $10$. Change the base and they will stop working. In particular, the following trick would work in base $17$: if the last digit of your number is $0$ then the number is divisible by $17$. Of course, in order to check this you would need to write it in base $17$, which is a vicious circle...
