Modular arithmetics I've been reading about some examples concerning DSS/DSA signature security and there is one part of an example that I do not understand the maths. Namely, how do you calculate this:
$w = (s^{-1}$ $mod$ $q)$ 
In this example let's say $q = 13$ and $s = 10$.
So we have
$w = (10^{-1}$ $mod$ $13) = 4$ 
How do we get 4 as a result? 

While with these small numbers it is possible to just guess-and-check an inverse, generally you use the Euclidean algorithm. It goes like this: since $10$ and $13$ are relatively prime, there is a way to find integers $a$ and $b$ so that $$10a+13b=1$$ If you do this, then reducing that equation modulo $13$, you have $$10a\equiv 1$$ and $a$ is the inverse of $10$ mod $13$. So your task is to find that $a$. The algorithm linked above lets you find an $a$ (and a $b$) after several iterations, essentially replacing the pair $(10,13)$ with smaller and smaller pairs until $a$ and $b$ are apparent.
