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/