Securing Higher Grades Costing Your Pocket? Book Your Assignment at The Lowest Price Now!

Get assignment help service to meet the high expectations of your professors


Number theory problem set 3

  1. Suppose that plaintext message units are digraphs in the ordinary 26-letteralphabet, where (as usual) A-Z corresponds to 0-25. We represent each digraph ij as an integer in the following way:

(26 · i) + j.

For example, the digraph “IN” is represented as 26 · 8 + 13 = 221.

You receive the sequence of ciphertext message units,


which were encrypted using a Merkle-Hellman knapsack system. (Each unit is the encryption of a digraph, and hence represents two plaintext letters.) The private key for the system is

(M = 2629,W = 1036,{3,5,10,19,41,79,161,320,641,1311}).

Your job is to decipher the message.

  1. Use the repeated squaring method (Algorithm 3.3 in the number theory notes) to calculate 652848 mod 4847.

In proving the following facts, you may use without proof any result stated in sections 1-3 of the Number Theory notes (except, of course, if the given result itself is what you’re being asked to prove. In that case, you may use without proof any result stated in sections 1-3 of the Number Theory notes up to the result I’m asking you to prove.) If you use some number theoretic result not stated in sections 1-3 of the notes, you should prove that result first (using, of course, the results in sections 1-3 of the notes).

  1. Complete the proof of the gcd recursion theorem (Theorem 1.6 in the number theory notes).
  2. Complete the proof of Theorem 1.13 in the notes: If there are integers x,y such that ax + by = 1, then gcd(a,b) = 1.
  3. Prove that if a m and b m, then ab m.

(This is part of Theorem 1.15 in the notes.)

  1. Prove that if a a b (mod m) and gcd(m,a) = 1, then b ≡ 1 (mod m).

(Note: This is a special case of the cancellation property described (but not proved) on p.10 of the Number Theory notes. The idea here is to prove this special case directly. In particular, you shouldn’t use the cancellation property, and you shouldn’t assume (without proof) the existence of an inverse for a)

  1. Consider the statement, “if a b (mod m) and a b (mod n), then a b (mod mn)”.
  2. Show by example that this statement is not true in general.
  3. Prove that the statement is true if m n.
  4. Prove that if x y (mod m), then gcd(x,m) = gcd(y,m).
Assignment Help Features
Assignment Help Services
  • Assignment Help
  • Homework Help
  • Writing Help
  • Academic Writing Assistance
  • Editing Services
  • Plagiarism Checker Online
  • Proofreading
  • Research Writing Help
QR Code Assignment Help