//File accompanying the presentation for Magma in Saldini and Bicocca

///////////////////
//Symmetric groups
///////////////////

n:=10^4;
G:=Sym(n);
G;
Order(G.1);
Order(G.2);
g:=Random(G);
time ord:=Order(g);
time gi:=Inverse(g);
time g2:=g^(ord-1);
gi eq g2;
1^g; //Exponential notation
h:=Random(G);
(1^g)^h;
(1^h)^g;
1^(g*h) eq (1^g)^h;//right action

//////////////////////
//Residue Class Rings
//////////////////////

n:=10^4;
R:=ResidueClassRing(n);
rr:=Random(R);
Order(rr);
uu:=random{r:r in R|IsUnit(r)};
Order(uu);
Exponent(UnitGroup(R));
CarmichaelLambda(n);

////////////////////////////////
//Permutation Difference problem
////////////////////////////////

n:=4;
G:=Sym(n);
R:=ResidueClassRing(n);
ss:=G.1;
{(i+1)^ss:i in R};
{(i+1)^ss:i in [1..n]};
ss:=G!(1,4,2,3);
#{(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]};
{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]};
exists{ss:ss in G|#{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]} eq n-1};
time exists{ss:ss in G|#{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]} eq n-1};
exists(tt){ss:ss in G|#{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]} eq n-1};

for n in [2..10 by 2] do
    G:=Sym(n);
    R:=ResidueClassRing(n);
    time exists(tt){ss:ss in G|#{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]} eq n-1};
    tt;
end for;


for n in [2..10] do
    G:=Sym(n);
    R:=ResidueClassRing(n);
    time ms:={*#{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]}:ss in G*};
    ms;
    MultisetToSet(ms);
end for;

PermDifferenceValues:=function(n)
    G:=Sym(n);
    R:=ResidueClassRing(n);
    return {*#{R|(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]}:ss in G*};
end function;

/*
n=2
Time: 0.000
{* 1^^2 *}
{ 1 }
n=3
Time: 0.000
{* 1^^6 *}
{ 1 }
n=4
Time: 0.000
{* 1^^8, 3^^16 *}
{ 1, 3 }
n=5
Time: 0.010
{* 1^^20, 3^^100 *}
{ 1, 3 }
n=6
Time: 0.030
{* 1^^12, 2^^60, 3^^288, 4^^288, 5^^72 *}
{ 1, 2, 3, 4, 5 }
n=7
Time: 0.210
{* 1^^42, 3^^1764, 4^^882, 5^^2352 *}
{ 1, 3, 4, 5 }
n=8
Time: 1.913
{* 1^^32, 2^^96, 3^^3584, 4^^10112, 5^^18816, 6^^6912, 7^^768 *}
{ 1, 2, 3, 4, 5, 6, 7 }
n=9
Time: 19.027
{* 1^^54, 2^^162, 3^^12744, 4^^39366, 5^^156978,
6^^105948, 7^^47628 *}
{ 1, 2, 3, 4, 5, 6, 7 }
n=10
Time: 211.724
{* 1^^40, 2^^760, 3^^18000, 4^^188400, 5^^826400,
6^^1420400, 7^^966000, 8^^194400, 9^^14400 *}
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }
*/

for n in [2..9] do
    G:=Sym(n);
    R:=ResidueClassRing(n);
    n;
    time ms:={*#{(i mod n +1)^ss-(i-1 mod n +1)^ss:i in [1..n]}:ss in G*};
    ms;
    MultisetToSet(ms);
end for;

/*
2
Time: 0.000
{* 2^^2 *}
{ 2 }
3
Time: 0.000
{* 2^^6 *}
{ 2 }
4
Time: 0.000
{* 2^^8, 3^^8, 4^^8 *}
{ 2, 3, 4 }
5
Time: 0.000
{* 2^^20, 3^^20, 4^^60, 5^^20 *}
{ 2, 3, 4, 5 }
6
Time: 0.020
{* 2^^12, 3^^84, 4^^336, 5^^168, 6^^120 *}
{ 2, 3, 4, 5, 6 }
7
Time: 0.200
{* 2^^42, 3^^112, 4^^1106, 5^^1932, 6^^1484, 7^^364 *}
{ 2, 3, 4, 5, 6, 7 }
8
Time: 1.803
{* 2^^32, 3^^224, 4^^3312, 5^^9648, 6^^16256, 7^^9216, 8^^1632 *}
{ 2, 3, 4, 5, 6, 7, 8 }
9
Time: 17.445
{* 2^^54, 3^^450, 4^^8298, 5^^39402, 6^^112752, 7^^129996, 8^^62568, 9^^9360 *}
{ 2, 3, 4, 5, 6, 7, 8, 9 }
10
Time: 197.855
{* 2^^40, 3^^700, 4^^18080, 5^^141760, 6^^603660, 7^^1203560, 8^^1139800, 9^^461360,
10^^59840 *}
{ 2, 3, 4, 5, 6, 7, 8, 9, 10 }
*/

BoundPerm:=function(int)
    if int mod 2 eq 0 then return int-1;
    else return int-2;
    end if;
end function;

cand:=[ss:ss in G|#{R!(((i+1) mod n +1)^ss-(i mod n +1)^ss):i in [1..n]} eq BoundPerm(n)];

//////////////////////////////
//Groebner Basis and syzygies
//////////////////////////////

RR:=RealField();
F27:=GF(27);
Q3:=pAdicField(3);
K7<z>:=CyclotomicField(7);
R<x>:=PolynomialRing(K7);
MinimalPolynomial(z);
Q:=Rationals();
P<x,y>:=PolynomialRing(Q,2);
f2:=x^2-y^2-1;
f1:=x^2+y^2-7;
I:=ideal<P|f1,f2>;
I;
Dimension(I);
VarietySizeOverAlgebraicClosure(I);
V:=Variety(I);
A:=AlgebraicClosure();
A;
VA:=Variety(I,A);

f:=x*y^2-x;
f1:=x*y+1;
f2:=y^2-1;
NormalForm(f,[f1,f2]);
NormalForm(f,[f2,f1]);
gb:=GroebnerBasis(I);

seq:=[x^2,x*y+y^2];
SyzygyMatrix(seq);
I:=ideal<P|seq>;
gb:=GroebnerBasis(I);
SyzygyMatrix(gb);


//////////////////
//Elliptic Curves
//////////////////

P2<X, Y, Z> := ProjectiveSpace(Rationals(), 2);
C := Curve(P2, X^3*Y^2 + X^3*Z^2 - Z^5);
Genus(C);

C:=Curve(P2,&+[P2.i^3:i in [1..3]]);
pt:=C![0,-1,1];
E,toE:=EllipticCurve(C,pt);
W:=WeierstrassModel(E);
MinimalModel(W);
M:=MinimalModel(E);
Discriminant(E);
Discriminant(W);
Discriminant(M);

O:=toE(pt);//punto all'infinito
P:=toE(C![1,-1,0]);
Order(P);
P@@toE;
(2*P)@@toE;
Q<x,b,a>:=PolynomialRing(Rationals(),3);
Discriminant(x^3+a*x+b,x);

//Un teorema di Eulero-Fermat dimostra che non esistono altri punti razionali.

////////////////////
//ECC Diffie-Hellman
////////////////////

p:=RandomPrime(100);
K:=GF(p);
a:=Random(K);
b:=Random(K);
0 ne -27*b^2 - 4*a^3;
E:=EllipticCurve([a,b]);
time #E;
Factorization($1);
P:=Random(E);
ord:=Order(P);
c:=Random(ord);
d:=Random(ord);
c*(d*P) eq d*(c*P);

//////////////
//Hasse bound
//////////////

disc:=func<a,b|-4*a^3 -27*b^2>;
pripow:=[q:q in [2..30]|IsPrimePower(q) and (q mod 2) ne 0];

for q in pripow do
    K:=GF(q);    
    nonsing:=[[a,b]:a,b in K|disc(a,b) ne 0];
    time card:=[#EllipticCurve(l):l in nonsing];
    setcard:=Set(card);
    liscard:=Sort([x:x in setcard]);
    cardms:=SequenceToMultiset(card);
    uu:=[Multiplicity(cardms,x):x in liscard];
    low:=Ceiling(q+1-2*Sqrt(q));
    upp:=Floor(q+1+2*Sqrt(q));
    q;
    cardms;
end for;

/*
Time: 0.000
3
{* 1, 4^^4, 7 *}
Time: 0.010
5
{* 2, 3^^2, 4^^3, 5^^2, 6^^4, 7^^2, 8^^3, 9^^2, 10 *}
Time: 0.010
7
{* 3, 4^^4, 5^^3, 6^^6, 7^^4, 8^^6, 9^^4, 10^^6, 11^^3, 12^^4, 13 *}
Time: 0.020
9
{* 4^^6, 7^^12, 10^^36, 13^^12, 16^^6 *}
Time: 0.020
11
{* 6^^5, 7^^5, 8^^10, 9^^10, 10^^10, 11^^5, 12^^20, 13^^5, 14^^10, 15^^10, 16^^10,
17^^5, 18^^5 *}
Time: 0.030
13
{* 7^^2, 8^^9, 9^^8, 10^^15, 11^^6, 12^^20, 13^^12, 14^^12, 15^^12, 16^^20, 17^^6,
18^^15, 19^^8, 20^^9, 21^^2 *}
Time: 0.050
17
{* 10^^4, 11^^8, 12^^24, 13^^8, 14^^16, 15^^24, 16^^28, 17^^8, 18^^32, 19^^8,
20^^28, 21^^24, 22^^16, 23^^8, 24^^24, 25^^8, 26^^4 *}
Time: 0.050
19
{* 12^^12, 13^^12, 14^^18, 15^^18, 16^^36, 17^^9, 18^^27, 19^^21, 20^^36, 21^^21,
22^^27, 23^^9, 24^^36, 25^^18, 26^^18, 27^^12, 28^^12 *}
Time: 0.080
23
{* 15^^11, 16^^22, 17^^11, 18^^44, 19^^11, 20^^44, 21^^33, 22^^22, 23^^22, 24^^66,
25^^22, 26^^22, 27^^33, 28^^44, 29^^11, 30^^44, 31^^11, 32^^22, 33^^11 *}
Time: 0.210
25
{* 16^^4, 17^^12, 18^^30, 19^^24, 20^^42, 21^^8, 22^^48, 23^^24, 24^^72, 25^^36,
27^^36, 28^^72, 29^^24, 30^^48, 31^^8, 32^^42, 33^^24, 34^^30, 35^^12, 36^^4 *}
Time: 0.250
27
{* 19^^117, 28^^468, 37^^117 *}
Time: 0.130
29
{* 20^^21, 21^^28, 22^^28, 23^^14, 24^^84, 25^^28, 26^^35, 27^^42, 28^^56, 29^^28,
30^^84, 31^^28, 32^^56, 33^^42, 34^^35, 35^^28, 36^^84, 37^^14, 38^^28, 39^^28,
40^^21 *}

*/