And secondly you said that the time taken to generate keys is independent of the underlying processor. Well I am a bit concerned about it. To me, I think the time taken would have significant difference if comparison is done between an 8 and 32 bit processor because, one can operate on 8 bits and the other can handle 32 bits at a given time. how would you approach that.

Computational complexity is usually stated in terms of the input size as a bound on the number of operations.
When you have a O(n) operation, it is running in c1 * n + c2 time. Changing the bit size on your processor will change c1. That changes the ACTUAL time that your application takes, but it doesn't change the O-Notation time your application takes. Thats an important distinction because, lets say going from 8 bit to 32 bit is a 16x speed improvement. If your algorithm runs in O(n2) time, 16x gain only gets you 4x more items done in the same timespan. If your algorithm runs in O(2n) time, you get 4 more items done. Thats why the O-notation is so prevelant, as it ignore those constant speed up factors. Moving from a O(2n) algorithm to a O(n2) algorithm is going to gain you more than your constant speed up factor.

The computational complexity does not change.

Computation complexity is designed to eliminate these kinds of values, because you are only concerned with the "big picture" when you are using such analysis.

To find out how fast it will be on an 8 bit processor, find or write an implementation and measure. If the processor is simple enough that every instruction has a fixed execution time and there are no page faults to worry about, and if you can fit your working set in the processor cache, you might be able to derive execution time from doing some math on the instructions that would be executed.