Practice question · Sort into groups
Sort each application by the number-theoretic idea it chiefly rests on.
Groups: Reduction modulo n · Primes and factoring · The gcd
- Computing an ISBN check digit
- Reducing a fraction to lowest terms
- Assigning a key to a hash table slot
- Generating an RSA key pair
Hints
- Two applications only need a remainder; two need the structure of prime factorizations.
- Invertibility mod n is decided by a single gcd computation.
Show the answer
Reduction modulo n: Assigning a key to a hash table slot, Computing an ISBN check digit
Primes and factoring: Generating an RSA key pair
The gcd: Reducing a fraction to lowest terms
Why
Hashing and check digits are pure remainder arithmetic. RSA lives on primes and the difficulty of factoring. Lowest terms and invertibility mod n are both gcd questions, a has an inverse exactly when gcd(a, n) = 1. Six different-looking tasks, three underlying ideas.
Practise Number Theory in Action
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Number Theory in Action
- The infinite geometric series 1 + 1/2 + 1/4 + 1/8 + … has infinitely many positive terms and sums to exactly…
- Order the stages of the RSA idea.
- An ISBN-10 has digits d1 through d10 and must satisfy: 1 x d1 + 2 x d2 + ... + 10 x d10 is congruent to 0 mod…
- A hash table has 13 slots and uses the hash function 'key mod 13'. Which slot does the key 1000 land in?
- Complete the source of RSA's security.
- Select every idea from this unit that RSA depends on.
- Zeno argued you can never cross a room: first half the distance, then half the rest, forever. Why does the…