Homepage › Solution manuals › David S. Dummit › Abstract Algebra › Exercise 0.3.16 ($\mathbb{Z}/n\mathbb{Z}$ in Python)
Exercise 0.3.16 ($\mathbb{Z}/n\mathbb{Z}$ in Python)
Write a computer program to add and multiply mod , for any given as input. The output of these operations should be the least residues of the sums and products of two integers. Also include the feature that if , an integer between and such that may be printed on request. (Your program should not, of course, simply quote “mod” functions already build into many systems).
Answers
Proof. I give an homemade class in an Object Oriented Program in Python to represent elements of (in a file “Zn.py”).
import random
class Mod:
"class of integers modulo n"
def bezout(a,b):
"""input : integers (a,b)
output : (x,y,d),
(x,y) solution of ax+by =d, d = gcd(a,b)
"""
sgn_a = 1 if a >= 0 else -1
sgn_b = 1 if b >= 0 else -1
(r0, r1)=(abs(a), abs(b))
(u0, v0) = (1, 0)
(u1, v1) = (0, 1)
while r1 != 0:
q = r0 // r1
(r2, u2, v2) = (r0 - q * r1, u0 - q * u1, v0 - q * v1)
(r0, r1) = (r1, r2)
(u0, u1) = (u1, u2)
(v0, v1) = (v1, v2)
x , y, d = sgn_a * u0, sgn_b * v0, r0
if x <= 0: x, y = x + abs(b), y - sgn_b * a
return x, y, d
def least_residue(a,n):
r = a % n
if r > n//2:
r -= n
return r
def __init__(self, a, n):
self.residu = Mod.least_residue(a,n)
self.modulo = n
def lift(self):
return self.residu
def __str__(self):
return f"Mod({self.residu}, {self.modulo})"
def __repr__(self):
return f"{self.residu}"
def __eq__(self,other):
if isinstance(other,int):
return self.residu == other % self.modulo
return self.residu == other.residu and self.modulo == other.modulo
def __hash__(self):
return (11 * self.residu + self.modulo) // 16
def __add__(self,other):
if self.modulo == other.modulo:
return Mod(self.residu + other.residu, self.modulo)
def __sub__(self,other):
if self.modulo == other.modulo:
return Mod(self.residu - other.residu, self.modulo)
def __mul__(self,other):
if self.modulo == other.modulo:
return Mod(self.residu * other.residu, self.modulo)
def __rmul__(self, a):
return Mod(a*self.residu, self.modulo)
def __neg__(self):
return Mod(-self.residu, self.modulo)
def __pos__(self):
return self
def __pow__(self,n):
if n>=0:
resu = Mod(1,self.modulo)
a = self
while n!= 0:
if n % 2 != 0:
resu = resu * a
a = a * a
n = n // 2
return resu
else:
return (self ** -n).inverse()
def inverse(self):
inv,_,_ = Mod.bezout(self.residu, self.modulo)
return Mod(inv, self.modulo)
def _exporapide_(gamma,n,a,p):
""" returns gamma^n, where gamma = (x,y) element of F_p(x)/<x^2-a>"""
x,y = gamma[0],gamma[1]
# multiplication in F_p(x)/<x^2-a> :
mult = lambda l : ((l[0][0] * l[1][0] + a * l[0][1] * l[1][1]) % p,
(l[0][0] * l[1][1] + l[0][1] * l[1][0])%p)
(u,v) = (1,0)
(r,s) = (x,y)
n = (p-1)//2
while n != 0:
if n % 2 != 0:
(u,v) = mult(((r,s),(u,v)))
(r,s) = mult(((r,s),(r,s)))
n = n //2
return (u,v)
def sqrt(self):
""" returns a square root in F_p= Z/pZ
if the modulo p is an odd prime, and if a is a square in F_p"""
a = self.residu
p = self.modulo
if a == 0: return Mod(0,p)
if p % 4 == 3:
resultat = Mod(a,p)**((p+1)//4)
return Mod(abs(resultat.lift()),p)
pas_trouve = True
resultat = 0
while pas_trouve:
z = random.randint(1,p-1)
(u,v) = Mod._exporapide_((1,z),(p-1)//2,a,p)
if v!= 0:
pas_trouve = False
U, V = Mod(u,p), Mod(v,p)
un = Mod(1,p)
W1 = (un - U) * V.inverse()
W2 = (-un - U) * V.inverse()
W3 = - U * V.inverse()
if W1*W1 == a:
resultat = W1
elif W2 * W2 == a:
resultat = W2
elif W3 * W3 == a:
resultat = W3
return Mod(abs(resultat.lift()),p)
Example with Ipython:
In [1]: from Zn import Mod In [2]: a = Mod (11,17) In [3]: b = Mod(9, 17) In [4]: a * b Out[4]: -3 In [5]: a = Mod(11, 1234567891234567891234567891) In [6]: b = a.inverse(); b Out[6]: 336700333973063970336700334 In [7]: b ** -1 Out[7]: 11 In [8]: r = a.sqrt(); r Out[8]: 261925641728901579479400386 In [9]: r ** 2 Out[9]: 11
□
