Very often in the description and analysis of a cryptographic protocol there is a need for a an element $k$ that is sampled
uniformly AND at random.
Is there a redundancy in the definition with uniformity and randomness?
If no what is the rigorous difference of uniform and random? Does it mean that the numbers of the distribution are random (they came from PRG) and each of them are picked up uniformly--meaning with equally probability?
If you sample a random element, then you sample it according to some distribution.
Uniformly then means that you sample from the uniform distribution, i.e., you sample it from a set where drawing each element is equally probable. Let us assume you have a set of 4 elements, then sampling uniformly at random from this set, every element is drawn with probability 1/4.
However, you could also sample a random element according to some other distribution, e.g., say two elements have probability 1/3 to be drawn and the remaining elements have probability 1/6 each.
To choose an element $k$ "uniformly (and) at random" (where I'd say the "and" is simply superfluous, and strictly speaking ungrammatical) from a set $S$ simply means choosing it so that each element of $S$ has the same probability of being chosen — that is to say, so that the random variable $k$ is uniformly distributed over $S$.
The reason we should specify that is because it's quite possible for a random variable not to be uniformly distributed. As a simple example, if we toss two ordinary six-sided dice, and add their values together, the resulting number will be a random integer between 2 and 12 inclusive, but the distribution of the values will be decidedly non-uniform.
That said, there is a fairly common convention in cryptography that, if one is told to choose a value randomly from some set, the distribution to use is assumed to be uniform unless otherwise explicitly indicated. Thus, if you're used to reading literature written by cryptographers, you may be used to seeing just "at random" written, with no qualifiers, where someone coming from a more general math background might feel it necessary to spell out "uniformly at random".
(One justification for this convention — besides the simple fact that it makes crypto papers shorter, since cryptographers use uniformly distributed random variables all the time — is that the uniform distribution over a set is, in a sense, the most random possible distribution over that set. In particular, the uniform distribution over a set — if it exists — has the maximum possible entropy of all distributions over that set, whereas a purely deterministic choice (i.e. a single-point distribution) would have the minimum entropy.)
Say I am working with a set of the numbers $\{1,2,3,4,5\}$ a uniform sampling of the numbers could result in the sequence $1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,...$. Another uniform sampling could result in $1,3,5,2,4,1,3,5,2,4,1,3,5,2,4,...$. Neither of these are random because my process for choosing did not allow things like $2,1$ in either case. My process was the obvious one given the sequences.
Now, consider the following random sampling algorithm. Flip a coin. If it is heads, return $1$ and if it is tails, return $3$. A valid sequence of outputs might be $1,1,3,1,3,3,1,1,3,3,3,1,1,1,3,1,3,1,1,1,3,3,3$. For the set $\{1,2,3,4,5\}$ this is clearly not uniform.
So this would suggest that there is no redundancy in saying "uniform and at random".
I would say that "random" refers to the process by which they are drawn, "uniform" refers to the property of the results of the process that each outcome is equally likely (distribution).
