Store Random ID for MySql Table

I have a large (1.5M-2M) record MySql table which I am indexing into Sphinx.

I need the IDs to be random/non-sequential due to the fact I am doing a two-level order (order by FieldA DESC,FieldB DESC) which then by default orders by ID. This gives me undesirable results since I store my data by Vendor and I'd like more random vendors once the FieldA and FieldB Order is implemented.

Since I could not figure out how to do this on the fly I tried the following which I tested on small tables to generate random unique integers:

Update IGNORE Table Set ID=FLOOR(RAND() * 2000000)

But after an hour or so gave up on that approach :|

Is there some efficient way to generate random IDs?