Question 346849 in PHP Question posted in
Official manual can be found here.

Php – Algorithm for Generating Unique Random Numbers within a Range without Using a List

I’m looking for an efficient algorithm in PHP to generate unique random numbers within a specified range (start = 0 to end = 0xFFFFFFFF) without using a list to store all possible numbers. I’ve explored various approaches, but each seems to require maintaining a list of all possible numbers, which isn’t feasible for large ranges due to memory constraints. When all possible numbers have been returned, then the entire number range can be used again.

Is there a way to accomplish this without storing all possible numbers in memory? I’ve considered using hash functions or permutation algorithms, but I’m unsure of the best approach or if there’s a more efficient solution available. Any insights or code examples would be greatly appreciated. Thank you!

Tags:

2

Answers


  1. 0

    A simple/naive solution that would survive scrutiny of the average person, but immediately fall apart under the scrutiny of any determined person, would be to simply scramble the bits according to a defined key.

    class ShuffleKey {
    
    private $key;
    
    public static function newKey(int $size=32) {
        $key = range(1,$size);
        shuffle($key);
        return new self($key);
    }
    
    public function __construct(array $key) {
        $this->key = $key;
    }
    
    public function getKey(bool $invert=false) {
        if( $invert ) {
            return array_flip($this->key);
        } else {
            return $this->key;
        }
    }
}

class IntegerShuffler {
    public function __construct(protected Shufflekey $key) {}
    
    public function shuffle($in) {
        return $this->_shuffle($in, $this->key->getKey());
    }
    
    public function unshuffle($in) {
        return $this->_shuffle($in, $this->key->getKey(true));
    }
    
    protected function _shuffle($in, $key) {
        $out = 0;
        foreach( $key as $offset => $transform ) {
            $out = $this->setBitAt($out, $transform, $this->getBitAt($in, $offset));
        }
        return $out;
    }
    
    protected function getBitAt(int $value, int $position) {
        return ( $value >> $position ) & 1;
    }
    
    protected function setBitAt(int $value, int $position, int $bit) {
        return $value | ( $bit << $position );
    }
}

// json_encode(ShuffleKey::newKey()->getKey())
$key = json_decode('[20,22,31,27,6,32,8,21,11,4,25,9,3,13,23,30,12,18,17,2,7,1,16,28,10,26,14,24,19,29,15,5]', true);

$shuf = new IntegerShuffler(new ShuffleKey($key));

var_dump(
    $t = $shuf->shuffle(1234567890),
    $shuf->unshuffle($t)
);

    Output:

    int(291931600)
int(1234567890)

    In this way you can just run through the range sequentially, scrambling as you go, as well as being able to "unshuffle" arbitrary numbers.

    If you need something that actually stands up to even the minimum amount of scrutiny, then you should be looking at something like a Linear Congruential Generator or Linear Feedback Shift Register as suggested by "President James K. Polk" in the comments. [Note: The commenter, not the 11th US President.]

    If you need "proper" security, then you must descend into the Math and/or InfoSec sections of StackExchange for suitably strong methods, as suggested by Barmar in the comments.

    Login or Signup to reply.
  2. 0

    0xFFFFFFFF is 32 bits. One solution would be to use a 32 bit encryption, and encrypt the numbers 0, 1, 2, 3, … with the same key. Encryption is guaranteed to be one-to-one so as long as the inputs are unique then the outputs will also be unique. All you need to record is the encryption key and where you are in the input sequence.

    For a different ordering of the numbers use a different key.

    For a 32 bit encryption either use Hasty Pudding cipher or write your own simple Feistel cipher. Obviously, you won’t need the decryption part.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search