Loading ...
Sorry, an error occurred while loading the content.

RE: [PrimeNumbers] Working in Z_p vs. Z_n

Expand Messages
  • Insall
    1. Solving systems of equations. For example, try finding all solutions of the following system of mod 4 equations,with no extraneous ones. Then just
    Message 1 of 5 , Jun 29, 2002
    • 0 Attachment
      1. Solving systems of equations. For example, try finding all solutions of
      the following system of mod 4 equations,with no extraneous ones. Then just
      imagine what happens if you want to solve the same equations modulo 5, 6, 7,
      8, ...

      3x + 2y + z + 3t = 1
      x + y + 2z + t = 1
      2x + 3y + z + 3t = 1
      2y + 3z + t = 2


      2. Polynomial interpolation. For example, suppose f is a functoin from the
      set {0,1,2,3} of integers modulo 4 (note: some computer programs and
      programming languages use {-3,-2,-1,0,1,2,3}, but this is redundant, since
      in modulo 4 arithmetic there are only four equivalence classes of integers
      modulo 4) back into {0,1,2,3}, and that we know that f(0)=1, f(1)=2,
      f(2)=2. Find all choices of coefficients a_0, a_1 and a_2 such that for any
      element t in {0,1,2,3},

      f(t)=(a_0)+(a_1)t+(a_2)t^2.

      Now, try the same thing in case we use arithmetic modulo 3 instead of
      arithmetic modulo 4, and then see what happens if the function values are
      arbitrary - try to find a formula for the coefficient vector (a_0,a_1,a_2)
      in terms of the vector of function values (p,q,r)=(f(0),f(1),f(2)).



      Maybe these are not so difficult as I think they are, but when the index of
      modularity is large, I think some trouble will be over the horizon.



      Matt

      -----Original Message-----
      From: dleclair55 [mailto:dleclair55@...]
      Sent: Friday, June 28, 2002 9:17 PM
      To: primenumbers@yahoogroups.com
      Subject: [PrimeNumbers] Working in Z_p vs. Z_n



      Hello,

      Some operations which are difficult modulo n are much easier when
      working modulo p.

      For example, there are no known fast methods for taking a square root
      modulo large n when the factorization of n is unknown. However very
      fast methods are known for taking square roots modulo a prime.

      Does anyone know of other examples of operations that are easy when
      working in Z_p but difficult when working in Z_n?

      Don Leclair





      Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
      The Prime Pages : http://www.primepages.org



      Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    Your message has been successfully submitted and would be delivered to recipients shortly.