NMark , rand() использует генератор псевдослучайных чисел, зашитый в библиотеку libc. Какой именно это будет генератор, PHP знать не знает и знать не обязан -- разные версии libc для разных операционных систем могут иметь различные реализации генератора псевдослучайных чисел.
mt_rand() использует генератор псевдослучайных чисел, зашитый в ядро PHP. Этот генератор работает по алгоритму Mersenne twister (отсюда mt вназвании функции), который разработали японские математики Макото Мацумото и Такудзи Hисимура в 1997 году (M. Matsumoto & T. Nishimura, "Mersenne twister: a 623-dimensionally equidistributed uniform pseudorandom number generator", ACM Trans. Model. Comput. Simul. 8, 3 (1998)).
Качество генератора псевдослучайных чисел определяется минимальной длиной сгенерированной им последовательности, зная которую, можно точно предсказать, что генератор выдаст после нее. Чтобы предсказать генерацию псевдослучайных чисел 32-битной версией Mersenne twister, надо иметь последовательность из 624 или более чисел.
Есть алгоритмы, которые вообще не поддаются предсказанию (например, алгоритм Блюма-Блюма-Шаба), но они медленные и потому используются только в криптографии.