[compalg] Les 2 (toepassingen hoofdstuk 1)

2728 days ago by J.Demeyer

Oefening 1
def multimodular_det(M): B = prod(RR(c.norm()) for c in M.columns()) primes = [] # p_i detmodp = [] # x mod p_i n = 0 while prod(primes) < 2*B + 1: n = n + 1 p = nth_prime(n) primes.append(p) d = M.change_ring(FiniteField(p)).det() detmodp.append(ZZ(d)) x = CRT_list(detmodp, primes) if x > B: x = x - prod(primes) return x 
       
M = random_matrix(ZZ, 100, 100) 
       
multimodular_det(M) 
        
208835842194095982603050550320176126805692462113786820598487732402355176\
134497640107044238227686804676699881424121251775258054222412879188663443\
5349961116717331590050201672240970695413115597025437463200
2088358421940959826030505503201761268056924621137868205984877324023551761344976401070442382276868046766998814241212517752580542224128791886634435349961116717331590050201672240970695413115597025437463200

Controle:
det(M) 
        
208835842194095982603050550320176126805692462113786820598487732402355176\
134497640107044238227686804676699881424121251775258054222412879188663443\
5349961116717331590050201672240970695413115597025437463200
2088358421940959826030505503201761268056924621137868205984877324023551761344976401070442382276868046766998814241212517752580542224128791886634435349961116717331590050201672240970695413115597025437463200

Oefening 2
def nulpunten(f): q = f.base_ring().cardinality() S = R.quotient(f) s = S(x)^q return gcd(f, s.lift() - x) 
       
k = GF(10^100 + 267) R.<x> = k[] 
       
pol = x^3 + x + 1 
       
zpol = nulpunten(pol) zpol 
        
x +
124201574703637139787165154788514525582945733999935694108263081896654334\
8795236187767538762080970548
x + 1242015747036371397871651547885145255829457339999356941082630818966543348795236187767538762080970548

Het unieke nulpunt is dus:
z = -zpol[0] z 
        
875798425296362860212834845211485474417054266000064305891736918103345665\
1204763812232461237919029719
8757984252963628602128348452114854744170542660000643058917369181033456651204763812232461237919029719

Controle:
pol(z) 
        
0
0

Oefening 3

1.

We zien $A = \begin{pmatrix} -1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$.
R = GF(139) A = Matrix(R, [[-1,1,0], [0,1,1], [0,1,0]]) v = vector(R, (0,1,0)) 
       
n = 5040302010 (A^n * v)[0] 
        
33
33

2.
R = GF(139) sqrt5 = sqrt(R(5)) 
       
phi = (1 + sqrt5)/2 
       
n = 5040302010 (phi^(n-1) - (-phi)^(1-n))/sqrt5 - (-1)^n 
        
33
33

3.

We werken in $\mathbb{F}_{p^2}$ in plaats van $\mathbb{F}_p$. Dit werkt want elk element van $\mathbb{F}_p$ wordt een kwadraat in $\mathbb{F}_{p^2}$. In Sage is dit volledig transparant, het veld wordt automatisch uitgebreid:
R = GF(157) sqrt5 = sqrt(R(5)) parent(sqrt5) 
        
Finite Field in sqrt5 of size 157^2
Finite Field in sqrt5 of size 157^2
phi = (1 + sqrt5)/2 
       
n = 5040302010 (phi^(n-1) - (-phi)^(1-n))/sqrt5 - (-1)^n 
        
78
78