[was@laptop was]$ [was@laptop was]$
Magma V2.9-11     Fri Sep 27 2002 11:20:29 on laptop   [Seed = 2818695934]
Type ? for help.  Type <Ctrl>-D to quit.

Loading startup file "/home/was/magma/local/emacs.m"

Loading "/home/was/magma/local/init.m"
> 
> 
> CRT;
Intrinsic 'CRT'

Signatures:

(<SeqEnum[RngIntElt]> X, <SeqEnum[RngIntElt]> M) -> RngIntElt

A solution x of the system of simultaneous linear congruences defined by the integer sequences X and M so that x = X[i] mod M[i] for each i (error if no solution) [#X = #M, M[i] > 0 for all i, M[i] pairwise coprime]

(<RngOrdIdl> I1, <RngOrdIdl> I2, <RngOrdElt> e1, <RngOrdElt> e2) -> RngOrdElt

Finds e such that (e1 - e) is in I1 and (e2 - e) is in I2. I1, I2, e1 and e2 must all be over the same order

(<RngOrdIdl> I1, <SeqEnum> L1, <RngOrdElt> e1, <SeqEnum> L2) -> RngOrdElt

Finds e such that (e1 - e) is in I1 and e has the same sign as L2 for all places occuring in L1

(<SeqEnum[RngOrdElt]> X, <SeqEnum[RngOrdIdl]> M) -> RngOrdElt

The Chinese remainder lifting of the sequence of elements with respect to the sequence of moduli.

(<RngInt> I, <RngInt> J, <RngIntElt> a, <RngIntElt> b) -> RngIntElt

The Chinese remainder theorem formulated with ideals


> CRT([2,3,2],[3,5,7]);
23
> time CRT([393983,9829049,2984059,294894], [2,31,107,2^400-593]);
6953998921688044831943390330204110977569897700089098920052965647163964046091353337137634936383411180056887242122608998359513
Time: 0.000
> x := $1;
> x mod 2;
1
> x mod 31;
3
> 9829049 mod 31;
3
> x mod 107;
43
> 2984059 mod 107;
> 2984059 mod 107;
43
> x mod (2^400-593);
> x mod (2^400-593);
294894
> 175*1882 -353*933;
1
> 
> 
> XGCD;
Intrinsic 'XGCD'

Signatures:

(<RngIntElt> x, <RngIntElt> y) -> RngIntElt, RngIntElt, RngIntElt
(<RngValElt> x, <RngValElt> y) -> RngValElt, RngValElt, RngValElt
(<RngGalElt> x, <RngGalElt> y) -> RngGalElt, RngGalElt, RngGalElt
(<RngUPolElt> x, <RngUPolElt> y) -> RngUPolElt, RngUPolElt, RngUPolElt

Extended GCD: return the GCD g of x and y, together with the cofactors a and b such that g = a*x + b*y

(<SeqEnum[RngIntElt]> Q) -> RngIntElt, SeqEnum

Extended GCD: return the GCD of integers in Q, together with the sequence of cofactors


> XGCD(1882,933);
1 175 -353
> d, x, y := XGCD(1882,933); 
> d;
1
> x;
175
> y;
-353
> _, x, y := XGCD(1882,933); 
> x;
175
> y;
-353
> XGCD(17,1882);
1 775 -7
> 775*17 mod 1882;
1
> Zmodn := IntegerRing(1882);
> Zmodn;
Residue class ring of integers modulo 1882
> Set(Zmodn);
> 1+12;
> 13
> a := Zmodn ! 17;
> a;
17
> a in Zmodn;
true
> 1/5 in Zmodn;

>> 1/5 in Zmodn;
       ^
Runtime error in 'in': Bad argument types
> 5 in Zmodn;
true
> a;
17
> Parent(a);
Residue class ring of integers modulo 1882
> a^(-1);
775
> a;
17
> b := Zmodn!(-1);
> Sqrt(b);
1785
> Sqrt(a);

>> Sqrt(a);
       ^
Runtime error in 'Sqrt': Argument has no square root
> 31^(-1);
1/31
> Parent($1);
Rational Field
> 5^(-1);
1/5
> t := Zmodn!5;
> t;
5
> Parent(t);
Residue class ring of integers modulo 1882
> Parent(5);
Integer Ring
> t^(-1);
753
> a;
17
> a^080980980980980980787879769878798797987979;
537
>