// Example code from paper 12:
// _Computer aided discovery of a fast algorithm for testing conjugacy
//  in braid groups_, by Volker Gebhardt
//
print "Examples from: Computer aided discovery of a fast algorithm for testing conjugacy in braid groups";
Attach("Paper12.m");
ei := GetEchoInput();
SetEchoInput(true);
// Section 2: Background: braid groups and testing conjugacy
// Subsection 2.2: Permutation braids and normal form
B := BraidGroup(7);
delta := FundamentalElement(B);
delta eq LCM({ B.i : i in [1..6] });  // this had better be true
InducedPermutation(delta);


// Section 3: Coming across another class invariant
// Subsection 3.1: A small surprise
B := BraidGroup(7);
// The paper uses a random element as shown below; for ease of reproduction,
// this has been replaced by the following explicit element.
//x := RandomCFP(B, 0, 1, 5, 10);
x := B ! < "Artin", 1, [ Sym(7) | (1,7,3)(2,5,6,4), (1,7,5,2,3,6),
           (1,2,5,6)(3,4), (2,3)(5,6), (2,6,4,3)(5,7) ], 0 >;
#SuperSummitSet(x);
count1 := 0;
sum := 0;
for i := 1 to 1000 do
  _, c := MyIsConjugate(x, x^Random(B));
  if c eq 1 then
    count1 +:= 1;
  end if;
  sum +:= c;
end for;
count1;               // expectation: approx. 1.7
Round(sum/1000);      // expectation: approx. 290
Round((sum - count1)/(1000 - count1));

// Subsection 3.2: Identifying the smaller invariant
Sx := SuperSummitSet(x);
Ux := &join(Circuits(Sx));
#Sx;
#Ux;
countU := 0;
for i := 1 to 1000 do
  y := MySuperSummitRepresentative(x^Random(B));
  if y in Ux then
    countU +:= 1;
  end if;
end for;
countU;

// Subsection 3.3: Looking for a way of computing ultra summit sets
SatisfiesConvexity(Ux);
SatisfiesGCD(Ux);


// Section 4: On the way to a proof
// Subsection 4.1: Linking cycling and conjugation
B1 := BraidGroup(7);
// The paper uses a random element as shown below; for ease of reproduction,
// this has been replaced by the following explicit element.
//x := RandomCFP(B1, 0, 1, 5, 10);
x := B1 ! < "Artin", 1, [ Sym(7) | (1,7,3)(2,5,6,4), (1,7,5,2,3,6),
            (1,2,5,6)(3,4), (2,3)(5,6), (2,6,4,3)(5,7) ], 0 >;
Sx := SuperSummitSet(x);
#Sx;
Cx := Circuits(Sx);
[ #p : p in Cx ];
{@ z^FundamentalElement(B1) : z in Cx[1] @} eq Cx[2];

B2 := BraidGroup(8);
y := B2 ! < "Artin", 1, [ Sym(8) | (1,8)(3,5,7,6,4), (2,4)(3,6,7),
            (2,7,6,5,4,3) ], 0 >; // element found by systematic search
Sy := SuperSummitSet(y);
#Sy;
Cy := Circuits(Sy);
[ #p : p in Cy ];
{@ z^FundamentalElement(B2) : z in Cy[1] @} eq Cy[2];
{@ z^FundamentalElement(B2) : z in Cy[3] @} eq Cy[4];
{@ z^(B1.1) : z in Cx[1] @} in [ Cx[1], Cx[2] ];

[ #p : p in Cx ];
SimpleElementAdjacency(Cx);
[ #p : p in Cy ];
SimpleElementAdjacency(Cy);

s := B1 ! Sym(7) ! (1,4,7,3,5)(2,6);
IsSuperSummitRepresentative(Sx[1]^s);
CheckTransport(Sx[1], s);
IsSimple(s^-1*FundamentalElement(B1));
CheckTransport(Sx[1]^s, s^-1*FundamentalElement(B1));
IsSuperSummitRepresentative(Sy[1]^B2.1);
CheckTransport(Sy[1],B2.1);  // no uniqueness
time forall{ <z, s> : z in Sx, s in Sym(7) |
    not IsSuperSummitRepresentative(z^(B1!s))
    or CheckTransport(z, B1!s) eq 1 };  // note uniqueness!

time forall{ <z, s> : z in Sx, s in Sym(7) |
    not IsSuperSummitRepresentative(z^(B1!s))
    or IsSimple(MyTransport(z, B1!s)) };

// Subsection 4.3: Proving properties of the transport map
Sx := SuperSummitSet(RandomCFP(BraidGroup(6), 0, 1, 5, 10));
TestMovingFactors(Sx[1]);
#Sx;
time forall{ y : y in Sx | TestMovingFactors(y) };


// Section 6: An application: key recovery
// Subsection 6.1: Key exchange using braid groups
// public data: we use a product of 8 simple elements in
// a braid group on 9 strings
l := 5;
r := 4;
len := 8;
B_L := BraidGroup(l);
B_R := BraidGroup(r);
B := BraidGroup(l + r);
x := Random(B, 0, 0, len, len);
/* identify B_L and B_R with subgroups of B */
f := hom< B_L -> B | [ B_L.i -> B.i : i in [1..l-1] ] >;
g := hom< B_R -> B | [ B_R.i -> B.(l+i) : i in [1..r-1] ] >;
a := Random(B_L);  // Alice: keeps a secret, sends y1 to Bob
y1 := NormalForm(x^f(a));
b := Random(B_R);  // Bob: keeps b secret, sends y2 to Alice
y2 := NormalForm(x^g(b));
K_A := Eltseq(NormalForm(y2^f(a)));  // Alice extracts shared key
K_B := Eltseq(NormalForm(y1^g(b)));  // Bob extracts shared key
K_A eq K_B;

// Subsection 6.2: An attack using conjugacy search
// attack using super summit sets
time _, nr_s, c_s := MyIsConjugate(x, y1);
nr_s;
y2^c_s eq y2^f(a);
K_recover_s := Eltseq(NormalForm(y2^c_s));
K_recover_s eq K_A;

// attack using ultra summit sets
time _, _, c_u := MyIsConjugate_Ultra(x, y1);
y2^c_u eq y2^f(a);
K_recover_u := Eltseq(NormalForm(y2^c_u));
K_recover_u eq K_A;

#UltraSummitSet(x);
B := BraidGroup(100);
time #UltraSummitSet(Random(B, 0, 1, 1000, 2000));
time #UltraSummitSet(Random(B, 0, 1, 1000, 2000));
SetEchoInput(ei);