Exercises

1. (For mathematicians only.)

   Let p be a (large) prime, and let a be a primitive root modulo p.

   Then if bᵢ is the residue of aᵢ modulo p (1 ≤ bᵢ ≤ p-1 ), the sequence:

   bᵢ-1
   p-1

   is a cyclical sequence of p-1 distinct numbers in the range 0 to 1 (excluding 1). By choosing a suitably, these can be made to look fairly random.

   65537 is a Fermat prime, 2¹⁶+1. Because the multiplicative group of non-zero residues modulo 65537 has a power of 2 as its order, a residue is a primitive root if and only if it is not a quadratic residue. Use Gauss' law of quadratic reciprocity to show that 75 is a primitive root modulo 65537 .

   The ZX Spectrum Next uses p=65537 and a=75, and stores some bᵢ-1 in memory. RND entails replacing bᵢ-1 in memory by bᵢ₊₁-1, and yielding the result (bᵢ₊₁-1) / (p-1).

   RANDOMIZE n (with 1 ≤ n ≤ 65535) makes bᵢ equal to n+1.

   RND is approximately uniformly distributed over the range 0 to 1.