Logged In: YES 
user_id=31435

The cause is that randint takes a pseudo-random float (C 
double in [0, 1),), multiplies it by (hi-lo+1), then truncates 
and adds that to lo.  Since a double on your box almost 
certainly has only 53 bits of precision, and your multiplier 
effectively moves the radix point 64 bits "to the right", I 
expect the last 11 bits you see will always be 0.

Under Python 2.3, which uses the Mersenne Twister to 
generate random doubles, this does appear to be the case:

>>> from random import randint
>>> def f():
...     return randint(2**64, 2**65-1)
...
>>> hex(f())
'0x11EDD95B72CEF4000L'
>>> hex(f())
'0x1DD69BF4B39C65000L'
>>> hex(f())
'0x13328DC9C1C733800L'
>>> hex(f())
'0x1E65B47170C057800L'
>>>

Under earlier versions of Python, it may be even worse than 
that.

It takes a fundamentally different kind of algorithm to 
generate arbitrarily long random ints.  Here's a link to one 
such for Python:

http://www.faqts.com/knowledge_base/view.phtml/aid/4406

I doubt the implementation of randint() will change, since 
most people want fast-as-possible generation of mountains of 
small integers, and there's a tradeoff between catering to 
that and catering to extreme inputs.  The randint docs should 
change, though (I think randint() used to raise an exception 
when fed arguments as large as the ones you're using; I 
suspect, but don't know, that we lost the helpful exception 
as an unintended consequence of the long-term effort to 
eradicate the user-visible distinction between Python ints 
(machine C longs) and Python longs (unbounded integers)).

BTW, given what you're doing, you may want to install one of 
the Python wrappers for GNU GMP.  Python's unbounded-int 
arithmetic implementation is extremely portable and reliable, 
but buys those in part by not caring much about speed.