random - Quick idea for a shuffling algorithm - would this work? -

I was discussing with a speedy and dirty algorithm to manipulate a deck of cards with my brothers ( That is, an array in which every element is unique). Description of the algorithm:

The number of cards in the deck should be n . Take a number of x so that gcd (n, x) = 1 . Now, again select i = 1 for (x * i) mod n for card number i = n and put it in a new pile Enter the card ( without card can be removed from the original deck, i.e. copy the card) New result of card will be our result.

It is clear to me that performing only this algorithm will not result in such a time as "random enough" (in the sense that it will fail statistical tests to determine randomness) but if We alternatively do the algorithm, possibly for the new value of x that meets the gcd (n, x) = 1 ? If enough time to do this will give us a "random enough" result, then how many times can we expect to do this as a function of n

< P>

Due to the wonders of the modulo arithmetic it will be insufficient to do this several times. In fact, there are the most n permutations that you can get in this way, and it is fine when n is prime or 1.

Let's say that you get it twice more than x from prime to n for the first time and y Code> n second pawr.

In the first p position, an element has moved to p * x (mod n) . The second time it is moved to (p * x) * y (mod n) . Due to the associative nature of this modular arithmetic, it is similar to transferring to p * (x n) . But if x * y = v (mod n) then it is similar to going to p * v (mod n) - and as you know, there ' Code> n is more than the sampling classes.

Therefore, there are mostly n permutations which can be the result of n -lamban deck (No, this is not a rigid proof!)

Edit:

I claimed that if you instead use modular qualitative exponentation, it would be better. However, after the additional consideration, many trivial configurations will still be subject to modular arithmetic in the way of "most n settings".