Sorry, an error occurred while loading the content.

## RE: [PrimeNumbers] Working in Z_p vs. Z_n

Expand Messages
• 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
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.