El problema es que rand devuelve un entero con signo, que por lo general es de 32 bits.
El valor máximo de este tipo de datos es 2147483647, bastante menor que el que le estás pidiendo.
Quizás quieras ver la
extensión GMP para uso de enteros de precisión arbitraria.
Saludos.