The process by which communication is established between the SmartDongle and the computer works like this: The SmartDongle has a free running counter. From the time power is supplied to the chip, the firmware on the dongle starts adding one to a counter. The chip runs at 4 MHz, so the counter changes rapidly. When the application program attempts to make contact with the SmartDongle, the number is quite large. Not only is it large, but it is unpredictable. When the application program signals that it wants to communicate with the dongle, the dongle takes that large, unpredictable number, which I call "L1," and finds the next value in its linear congruential sequence, which I call "L2." The value of L2 now is randomly and uniformly spread over the range from 0 to 264-1. The dongle sends L2 back to the PC and waits. The PC has the ability to generate the same linear congruential sequence. It finds the next value, which I call "L3", and sends it back to the dongle. The dongle compares the value it receives from the PC with the value it calculated. If they are identical, the communication is established. If they differ, the dongle requires that the process starts again.
Linear Congruential Sequences
The linear congruential sequence is a popular and useful method for generating pseudorandom numbers. Pseudorandom numbers are values generated by an algorithm that appear to be random, but can be recreated at will. The process was introduced by D.H. Lehmer (see "Mathematical Methods in Large-scale Computing Units," Proceedings of the Second Symposium on Large-Scale Digital Calculating Machinery, 1951) and enhanced by W.E. Thomson (see "A Modeled Congruence Method of Generating pseudorandom Numbers," Computer Journal, 1958). It is clearly taught in Donald Knuth's The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Second Edition (Addison-Wesley, 1981).
The algorithm works like this:
Ln+1 (a * Ln + c) modulo m
where "a" is the multiplier, c is the increment, and m is the modulus. The initial value (L0) is called the seed. Choosing the "right" values for a, c, and m are crucial. If the wrong values are chosen, then the sequence repeats quickly. To make life easy for everyone, it makes sense to use a modulus that works with the arithmetic instructions of the processor at hand. For the SmartDongle, we chose a modulus of 264. The little processor in our Cypress chip does its arithmetic 8 bits at a time. We use simple loops in the firmware to do the arithmetic on the unsigned 64-bit numbers.
The Linear Congruential Sequence
The values chosen for a and c can yield widely different results. We would like to have as many different numbers appear as possible. With a modulus of 264, there are 264 possible numbers that can occur in the sequence. Attempting to keep track of which numbers have occurred in the sequence sounds like a daunting task. If we were to attempt to create a bit array and keep track of which numbers appear in the sequence, it would take more RAM than exists in all computers that have ever been built on Earth (about 2-million terabytes). Fortunately, we have other options. The following algorithm stops the first time a number is repeated in a sequence. The function f can be any function:
count 0
X Y seed
do
{
count count + 1
X f(X)
Y f(f (Y))
} until X = Y
This algorithm certainly satisfies my idea of a robust algorithm. It is simple and yet effective. It uses only a trivial amount of memory, performs a modest number of calculations, and yet it works.
Choosing "Good" Values for a and c
Not all of the potential values for a and c yield sequences that are even close to being random. As a trivial example, if a is chosen to be zero, then the sequence quickly deteriorates. Regardless of the seed supplied, after the first value, all subsequent values have the value of c. This is not a very useful sequence. Similarly, if a is chosen to have a value of 1, the linear sequence is way too predictable. "Good" choices for a and c are prime numbers that are relatively prime to the modulus. Integers are stored on a PC as binary numbers. The modulus for binary numbers is a power of 2. To be relative prime to the modulus, the values of a and c must be odd. Some quick experimenting with values of a and c using the foregoing algorithm shows that whenever the numbers are prime, the period of the linear sequence is maximized. Stated another way, as long as a and c are relatively prime to the modulus, the values in the sequence L1, L2, L3, L4... do not repeat until all possible values have appeared exactly once.
These sequences work well in our SmartDongle application. In other applications, the sequences may fail miserably. For instance, using the sequences to simulate a coin toss could be done by testing to see if the numbers are even or odd. The problem is that since a and c are both odd, the values in the linear congruential sequence alternate between even and odd numbers. In this example, selecting a bit other than the low-order bit works much better.
Prime Numbers
There are lots of prime numbers that can be represented in 64 bits. We need to have a method for selecting from this rich set. This can be done without requiring a large amount of computation. For starters, we know that all of the values we want to use for a and c must be odd. I use t as the value to be tested to see if it is prime and d as the divisor. The variable q will be the quotient.
d 3
do
{
q t / d
if ((q * d) = t) then t is not prime
d d + 2
} until q < d
If the program drops out of the loop, it means that t is a prime number. We can get away with stopping when q is greater than d because multiplication is commutative. Remembering back to the days of algebra, we learned that q times d is the same as d times q. That means that the comparison to see if q*d is equal to t need only use the possible values for which q is less than or equal to the square root of t. Rather than use a separate calculation to find the square root of t, we can accomplish the same objective by just comparing the divisor and the quotient.
Finding Prime Numbers
The final step in finding values for a and c is pretty simple. We select an arbitrary odd number and test to see if it is prime. If it isn't, we add 2 and try again. It doesn't take many iterations before a prime is found:
t an odd number we pull out of the air
d 1
do
{
d d + 2
q t / d
if ((q * d) = t) then
{ t is not prime
t t + 2
d 1
}
} until q < d
When we exit the loop, t will be a prime number. We use this method to find a and c, we use 264 as our modulus, and we use the value in our free running counter as the seed value for the sequence. The result is a query that the SmartDongle puts to the PC that is difficult to answer without knowing the values of a and c.
