3.14 Computer Problems – Introduction to Cryptography with Coding Theory, 3rd Edition

3.14 Computer Problems

  1. Evaluate gcd(8765, 23485).

    1. Find integers x and y with 65537x+3511y=1.

    2. Find integers x and y with 65537x+3511y=17.

  2. You are told that exactly one of the numbers

    21000+277, 21000+291, 21000+297

    is prime and you have one minute to figure out which one. They do not have any prime factors less than 109. You may use modular exponentiation, but you may not use commands of the form “IsPrime[n]” or “NextPrime[n].” (This makes explicit Exercise 30 above.)

  3. Find the last five digits of 31234567. (Note: Don’t ask the computer to print 31234567. It is too large!)

  4. Look at the decimal expansion of e=2.71828182845904523. Find the consecutive digits 71, the consecutive digits 271, and the consecutive digits 4523 form primes. Find the first set of five consecutive digits that form a prime (04523 does not count as a five-digit number).

  5. Solve 314x271(mod11111).

  6. Find all solutions to 216x66(mod606).

  7. Find an integer such that when it is divided by 101 the remainder is 17, when it is divided by 201 the remainder is 18, and when it is divided by 301 the remainder is 19.

  8. Let n=391=1723. Show that 2n11(modn). Find an exponent j>0 such that 2j1(modn).

  9. Let n=8404765497. Find x and y with x2y2(modn) but x±y(modn).

  10. Let M=1241525114196.

    1. Find the inverse of M(mod101).

    2. For which primes p does M not have an inverse mod p?

  11. Find the square roots of 26055 mod the prime 34807.

  12. Find all square roots of 1522756 mod 2325781.

  13. Try to find a square root of 48382 mod the prime 83987, using the method of Section 3.9. Square your answer to see if it is correct. What number did you find the square root of?