This is classic birthday problem.
With m=10^7
and n=10^20
(Since 2^64
~ 10^20
), and the collision probability is given by:
p = 1 - exp(-m^2/(2*n))
Gives a collision probability of 5e-07
I would say sampling without replacement is your best option.