Home

Table of Contents

• Integers Modulo n
  • Pseudorandom number generator
    • Notes
    • Linear Congruence Generator Exercises
  • [Number Theoretic Practicalities]

---

SSCrytography

Collection of exercises, files, and notes from SS Math Cryptography

Integers Modulo n

Pseudorandom number generator

Numbers used on the exercises as a: 123456789,

• Linear Congruence Generator (lcg).

  1. Does the LCG defined by the program above satisfy all three bulleted conditions so that its period is 2^64, the largest possible?
  2. If possible, compute the potency of the LCG above to see if it even has a chance of being sufficiently "random".
  3. Show the following (we used this above): if gcd(a, m) = d then, modulo m, for any integer x, we have that ax is always a multiple of d.
  4. In the previous discussion we used the fact that if a and m are relatively prime, then a has a multiplicative inverse modulo m; that is, there exists a^(-1)in{Z} such that a^(-1)*a=1.mod(m). Above we only needed its existence but what is a^(-1) if a=123456789 and m=2^(64)?
  • Exercise 1- 4

• Random analysis using Chi-squared distribution.

  • Chi-Square
  • Chi-Square on Chi-Square
  • Spectral test

These tests do not prove randomness, they only prove the lack of non-randomness

Number Theoretic Practicalities