¿Cómo generar un número aleatorio “grande” en Python?
random biginteger (1)
¿Cómo puedo generar un entero aleatorio grande (más de 64 bits) en Python?
Puedes usar random.getrandbits() :
>>> random.getrandbits(128)
117169677822943856980673695456521126221L
Como se indica en la documentación vinculada, random.randrange() también hará el truco si random.getrandbits() está disponible.