Algorithm to generate random number of size X

Question

In my mobile application I have to provide the user with a random unique X alphanumeric code so that the user can reply with that alphanumeric code to perform some task.

The number of users going to use this application is around 1 million people and the message traffic is around 0.1 million messages/day.

I can use only 26 upper letters, 26 lower letters and 10 digits. If the random number size is 5 then I can generate 916132832 unique combinations. After the combinations get exhausted I want to recycle this number generation again.

I am looking for an algorithmic approach. Is there any algorithmic approach to solve this problem?

Answer 1

If you are looking for something very very simple try this:

Date date = new Date();
String random = String.valueOf(date.getTime()).substring(6);

The numbers will never repeat in your near future!

Answer 2

It sounds like you need a Linear Congruential Generator. An LCG is a simple recursive function of the form X(n+1) = (a*X(n)+c) mod m. LCG<124, 3, 916132832> does what you need and hits every value in the cycle. Each value in the cycle will map to a 5 digit code like you specified.

Fair warning, from your description I'm assuming you don't really need the randomness factor, just that each value is guaranteed unique for the cycle. This algorithm isn't the least bit secure. Anyone can break into the cycle from the last code you sent out. If you do need some randomness you're in a bit of trouble. To quote John von Neumann. "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."

Answer 3

The best way to do this is to use a cryptography trick called Format Preserving Encryption or FPE. Your problem is very similar to this application of FPE. Your case seems best solved by using the Feistel network method to generate your FPE. In your specific case, 916132832 is approximately 2^29.7, so you should using a 30-bit wide Feistel network along with cycle walking.

You pick a random key AES key K and and maintain this K as well as a counter C. C starts at 0, and increments by 1 every time you you hand out a code. The code is the FPE encryption of C. When C reaches 916132832 you have used up all the codes. You may now pick another AES key K', set C=0, and start over. You may need to save all unacknowledged (K, C) pairs depending on your application. You might want to have an expiration date on these unacknowledged pairs so your storage requirement is reduced.

Answer 4

The best solution that I can think of is to keep a daily updating private key. use the key in combination with the mobile number to generate a 5 digit code and store this code in a db. Invalidate the code and clear the database when updating the private key. In this way instead of you waiting for the combinations to finish, you decide when the existing codes become invalid. This approach give you the flexibility of increasing the code size from 5 to any other size and you only store the values which have already been used.

Answer 5

You have 62 characters (A-Z, a-z, 0-9). A 5 character code is effectively a 5 digit base 62 number. Generate a random number in the appropriate range and convert it to base 62.

To avoid repeats, take a large enough range of numbers and shuffle the range. All guaranteed unique and not in any particular order.

Answer 6

Your codes could be either unique or algorith-generated.

I understand you think of algorithm that would map ordinal numbers into codes in such way, that each number <= all possible codes count will map into predicable code. Than it will be however not random, but could only seem random to the user not knowing the algorithm.

Otherwise you would have to remember all using codes, which is technically not realizable.

Answer 7

If you don't need strong security about it then a simple approach is

1. Keep a counter x running from 0 to T-1 with T=62**n where n is the number of chars you want to use.
2. For each code you need just increment x and then use the encoding of (x * P) % T where P is a large number coprime with T and % is the modulo operator.

Being P coprime with T you are guaranteed that the mapping (x * P) % T is a bijection and so all codes will be used before the first one being reused.

For there is k so that k*P = 1 (mod T) and therefore for each y the number x = (k * y) % T is the inverse of y because x*P = (k*y) * P = y * (k*P) = y * 1 = y (mod T) so the transformation x -> (x * P) % T) is surjective and therefore also injective because this space is finite.

You may also try to use some more complex bijective function e.g. limiting T to a power of two and using bit shuffling but then probably if you really need security it would be better to just use a random code each time may be checking it has not been used too recently with a queue and a bit table or an hash table depending on which of the two would be smaller.

Answer 8

With 5 characters you would be safe for 900 days and then have to reset.

I wrote some code for another StackOverflow user a few weeks ago. It's a random generator, which only generates new numbers.

import java.util.BitSet;
import java.util.Random;

/**
 * Random number generator without repeat in the given range at construction time.
 * 
 * @author martijn
 */
public class NoRepeatRandom {

    private Random random;
    private BitSet used;
    private int max;

    /**
     * Creates new instance of NoRepeatRandom, with the range <code>[0-max[</code>.
     * @param max the maximum for the range
     * @param seed the seed for the underlying {@link java.util.Random}
     */
    public NoRepeatRandom(int max, long seed)
    {
        this.max = max;
        this.used = new BitSet(max);
        this.random = new Random(seed);
    }

    /**
     * Creates new instance of NoRepeatRandom, with the range <code>[0-max[</code>.<br />
     * <code>System.currentTimeMillis()</code> is used as seed for the underlying {@link java.util.Random}
     * @param max the maximum for the range
     */
    public NoRepeatRandom(int max)
    {
        this(max, System.currentTimeMillis());
    }

    /**
     * Gives the next random number
     * @return a new random number. When finished it returns -1.
     */
    public int next()
    {
        if (isFinished())
        {
            return -1;
        }
        while (true)
        {
            int r = random.nextInt(max);
            if (!used.get(r))
            {
                used.set(r);
                return r;
            }
        }
    }

    /**
     * Tells if the random generator has finished. Which means that all number in the range
     * [0-max[ are used.
     * @return true if all numbers are used, otherwise false.
     */
    public boolean isFinished()
    {
        return max == used.cardinality();
    }

    /**
     * Sets all the numbers in the range [0-max[ to unused. Which means that all the numbers
     * can be reused.
     */
    public void reset()
    {
        used.clear();
    }

    /**
     * 
     * @return the maximum.
     */
    public int getMax()
    {
        return max;
    }
}

Then create an instance of it:

NoRepeatRandom nrr = new NoRepeatRandom(916132832);

And to generate a new code, use:

int codeInt = nrr.next();
if (codeInt == -1)
{
    // All the codes are used, need to reset the random generator!
}
String code = toCode(codeInt);

The only remaining part is to design the toCode(int) method:

public static final String charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvw013456789";

public static String toCode(int i)
{
    String code = "";

    return code;
}

Answer 9

Is there really a possibility of all codes being exhausted? You say there will be only 1 million users. If I understand correctly this means you will only have to generate 1 million codes. If this is the case, then the number of possible (5-character, for example) codes is much larger than the number you will need, and the solution is simple: Just keep generating random codes for new users until you find one that isn't taken. You can store and look up used codes in a hash table.

Answer 10

If you accept to recycle the random numbers, why do you want to wait for the exhaustion of the combinations before recycling?

• This makes the numbers less and less random when going to the end of the combination set
• This forces you to maintain some database to know which numbers have already been used and which haven't.

I would just generate random numbers, without caring if they've been used already.

If you really really want to keep it like you asked, here's how you could do it:

• Generate all the combinations and put them into a database table
• Store the size of this table in some variable
• Generate a random number R between 1 and the size of the table
• Fetch the combination stored at the Rth row of the table
• Delete the Rth row from the table, and decrement the size variable
• when the table is empty (and the size variable is 0), start again

You could improve it by moving the used numbers from one table to another, and use the second table instead of the first one when the first table is empty.

You could also do that in memory, if you have enough of it.

Answer 11

First of all, why don't you use UUID?

But if you want to generate numbers yourself, try something like this:

Pregenerate 10-20 millions combinations and keep them in a set in the memory. When you want the next id, get a random combination from them and remove it from the set.

When the set becames empty, reset the set with the original combinations(you can keep a second copy of the original set for fast reset).