1#############################################################################
2##
3##  blackbox.gi
4##                                recog package
5##                                                        Max Neunhoeffer
6##                                                            Ákos Seress
7##
8##  Copyright 2005-2008 by the authors.
9##  This file is free software, see license information at the end.
10##
11##  A collection of find homomorphism methods for black box groups.
12##
13#############################################################################
14
15BBStdGenFinder := rec();
16BBStdGenFinder.HS :=
17# Created by bbtogap.py from HSG1-find1 from the ATLAS page
18function(arg)
19    local vars,els,G;
20    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
21    els := ShallowCopy(arg);
22    vars := rec();
23    G := Group(arg);
24
25    # Black box algorithm to find standard generators of HS
26
27    vars.V := 0;
28    repeat    # label SEMISTD
29        els[1] := PseudoRandom(G);
30        vars.A := RECOG.ProjectiveOrder(els[1]);
31        vars.V := vars.V + 1;
32        if vars.V > 1000 then
33            return fail;  # a timeout
34        fi;
35        if not(vars.A in [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 15, 20]) then
36            return fail;
37        fi;
38    until vars.A = 20;
39
40    els[2] := els[1]^10;
41    els[3] := els[1]^4;
42
43    vars.X := 0;
44    repeat    # label CONJUGATE
45        vars.X := vars.X + 1;
46        if vars.X > 1000 then
47            return fail;  # a timeout
48        fi;
49        els[4] := PseudoRandom(G);
50        els[3] := els[3]^els[4];
51        els[5] := els[2]*els[3];
52        vars.D := RECOG.ProjectiveOrder(els[5]);
53        if not(vars.D in [5, 6, 8, 10, 11, 15, 20]) then
54            return fail;
55        fi;
56    until vars.D = 11;
57    return els{[2, 3]};
58end;
59
60# Created by bbtogap.py from M11G1-find1 from the Atlas page
61BBStdGenFinder.M11 :=
62function(arg)
63    local vars,els,G;
64    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
65    els := ShallowCopy(arg);
66    vars := rec();
67    G := Group(arg);
68    # Black box algorithm to find standard generators of M11
69
70    vars.V := 0;
71
72    repeat    # label START
73        els[1] := PseudoRandom(G);
74        vars.A := RECOG.ProjectiveOrder(els[1]);
75        vars.V := vars.V + 1;
76        if vars.V > 1000 then
77            return fail;  # a timeout
78        fi;
79        if not(vars.A in [1, 2, 3, 4, 5, 6, 8, 11]) then
80            return fail;
81        fi;
82    until vars.A in [4, 8];
83
84    vars.B := QuoInt(vars.A,2);
85    els[2] := els[1]^vars.B;
86
87    vars.C := QuoInt(vars.A,4);
88    els[3] := els[1]^vars.C;
89
90    # The elements 2 and 3 are now in the correct conjugacy classes.
91
92    vars.X := 0;
93
94    repeat    # label CONJ
95        vars.X := vars.X + 1;
96        if vars.X > 1000 then
97            return fail;  # a timeout
98        fi;
99        els[4] := PseudoRandom(G);
100        els[3] := els[3]^els[4];
101        els[5] := els[2]*els[3];
102        vars.D := RECOG.ProjectiveOrder(els[5]);
103
104        if not(vars.D in [2, 3, 4, 5, 6, 8, 11]) then
105            return fail;
106        fi;
107    until vars.D = 11;
108
109    els[6] := els[5]*els[3];
110    els[7] := els[6]*els[3];
111    els[8] := els[5]*els[6];
112    els[9] := els[8]*els[7];
113
114    vars.E := RECOG.ProjectiveOrder(els[9]);
115
116    if vars.E = 3 then
117        els[10] := els[3]^-1;
118        els[3] := els[10];
119    fi;
120
121    return els{[2, 3]};
122end;
123
124# Created by bbtogap.py from M12G1-find1 from the Atlas web page
125BBStdGenFinder.M12 :=
126function(arg)
127    local vars,els,G;
128    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
129    els := ShallowCopy(arg);
130    vars := rec();
131    G := Group(arg);
132
133    # Black box algorithm to find standard generators of M12
134    # (Second listed algorithm)
135
136    vars.F := 0;
137    vars.G := 0;
138    vars.V := 0;
139    repeat    # label SEMISTD
140        els[1] := PseudoRandom(G);
141        vars.A := RECOG.ProjectiveOrder(els[1]);
142        vars.V := vars.V + 1;
143        if vars.V > 1000 then
144            return fail;  # a timeout
145        fi;
146        if not(vars.A in [1, 2, 3, 4, 5, 6, 8, 10, 11]) then
147            return fail;
148        fi;
149        if vars.F = 0 then
150            if vars.A in [4, 8] then
151                vars.B := QuoInt(vars.A,2);
152                els[2] := els[1]^vars.B;
153                vars.F := 1;
154            fi;
155        fi;
156        if vars.G = 0 then
157            if vars.A = 10 then
158                els[3] := els[1]^5;
159                vars.G := 1;
160            fi;
161        fi;
162    until vars.F <> 0 and vars.G <> 0;
163    vars.X := 0;
164    repeat    # label ELTORDER3
165        vars.X := vars.X + 1;
166        if vars.X > 1000 then
167            return fail;  # a timeout
168        fi;
169        els[4] := PseudoRandom(G);
170        els[5] := els[3]^els[4];
171        els[6] := els[3]*els[5];
172        vars.D := RECOG.ProjectiveOrder(els[6]);
173        if not(vars.D in [1, 2, 3, 4, 5, 6]) then
174            return fail;
175        fi;
176    until vars.D in [3,6];
177    vars.E := QuoInt(vars.D,3);
178    els[7] := els[6]^vars.E;
179
180    vars.X := 0;
181    repeat    # label CONJUGATE
182        vars.X := vars.X + 1;
183        if vars.X > 1000 then
184            return fail;  # a timeout
185        fi;
186        els[8] := PseudoRandom(G);
187        els[7] := els[7]^els[8];
188        els[9] := els[2]*els[7];
189        vars.F := RECOG.ProjectiveOrder(els[9]);
190
191        if not(vars.F in [2, 3, 5, 6, 8, 10, 11]) then
192            return fail;
193        fi;
194    until vars.F = 11;
195    return els{[2, 7]};
196end;
197
198# Created by bbtogap.py from M22G1-find1 from the Atlas web page
199BBStdGenFinder.M22 :=
200function(arg)
201    local vars,els,G;
202    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
203    els := ShallowCopy(arg);
204    vars := rec();
205    G := Group(arg);
206
207    # Black box algorithm to find standard generators
208    # of M22
209
210    vars.V := 0;
211
212    repeat    # label START
213        els[1] := PseudoRandom(G);
214        vars.A := RECOG.ProjectiveOrder(els[1]);
215        vars.V := vars.V + 1;
216        if vars.V > 1000 then
217            return fail;  # a timeout
218        fi;
219        if not(vars.A in [1, 2, 3, 4, 5, 6, 7, 8, 11]) then
220            return fail;
221        fi;
222    until vars.A = 8;
223
224    els[3] := els[1]*els[1];
225    els[2] := els[3]*els[3];
226
227    vars.X := 0;
228
229    repeat    # label CONJ
230        vars.X := vars.X + 1;
231        if vars.X > 1000 then
232            return fail;  # a timeout
233        fi;
234        els[4] := PseudoRandom(G);
235        els[3] := els[3]^els[4];
236        els[5] := els[2]*els[3];
237        vars.D := RECOG.ProjectiveOrder(els[5]);
238        if not(vars.D in [2, 3, 4, 5, 6, 7, 8, 11]) then
239            return fail;
240        fi;
241        if vars.D <> 11 then
242            continue;    # was jmp to CONJ
243        fi;
244
245        els[6] := els[5]*els[3];
246        els[7] := els[5]*els[6];
247        vars.E := RECOG.ProjectiveOrder(els[7]);
248
249        if vars.E <> 11 then
250            continue;    # was jmp to CONJ
251        fi;
252        break;  # this is a success
253    until false;
254
255    return els{[2, 3]};
256end;
257
258# Created by bbtogap.py from J2G1-find1 from the Atlas web page
259BBStdGenFinder.J2 :=
260function(arg)
261    local vars,els,G;
262    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
263    els := ShallowCopy(arg);
264    vars := rec();
265    G := Group(arg);
266
267    # Black box algorithm to find standard generators of J2
268
269    vars.F := 0;
270    vars.G := 0;
271    vars.H := 0;
272    vars.V := 0;
273    vars.X := 0;
274    repeat    # label SEMISTD
275        els[1] := PseudoRandom(G);
276        vars.A := RECOG.ProjectiveOrder(els[1]);
277        vars.V := vars.V + 1;
278        if vars.V > 1000 then
279            return fail;  # a timeout
280        fi;
281        if not(vars.A in [1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15]) then
282            return fail;
283        fi;
284        if vars.F = 0 then
285            if vars.A in [2, 6, 10] then
286                vars.B := QuoInt(vars.A,2);
287                els[2] := els[1]^vars.B;
288                vars.F := 1;
289            fi;
290        fi;
291        if vars.G = 0 then
292            if vars.A in [3, 6] then
293                vars.C := QuoInt(vars.A,3);
294                els[3] := els[1]^vars.C;
295                vars.G := 1;
296            fi;
297        fi;
298
299        # As well as finding elements of order 2 and 3 (for the
300        # generators), we find a 2A-element. This allows us
301        # to prove that the elements we have are in the right classes
302        # before starting the random conjugating.
303        if vars.H = 0 then
304            if vars.A in [4, 8, 12] then
305                vars.D := QuoInt(vars.A,2);
306                els[4] := els[1]^vars.D;
307                vars.H := 1;
308            fi;
309        fi;
310
311        if vars.F = 0 then
312            continue;    # was jmp to SEMISTD
313        fi;
314        if vars.G = 0 then
315            continue;    # was jmp to SEMISTD
316        fi;
317        if vars.H = 0 then
318            continue;    # was jmp to SEMISTD
319        fi;
320
321        els[5] := els[2]*els[4];
322        vars.D := RECOG.ProjectiveOrder(els[5]);
323        if vars.D in [1, 2, 3, 4, 5] then
324            # Probably a 2A element
325            vars.F := 0;
326            continue;    # was jmp to SEMISTD
327        fi;
328
329        els[6] := els[3]*els[4];
330        vars.E := RECOG.ProjectiveOrder(els[6]);
331        if vars.E in [6, 12] then
332            # Probably a 3A element
333            vars.G := 0;
334            continue;    # was jmp to SEMISTD
335        fi;
336        break;
337    until false;
338
339    # The elements are definitely in classes 2B and 3B now.
340
341    repeat    # label CONJUGATE
342        vars.X := vars.X + 1;
343        if vars.X > 1000 then
344            return fail;  # a timeout
345        fi;
346        els[7] := PseudoRandom(G);
347        els[3] := els[3]^els[7];
348        els[8] := els[2]*els[3];
349        vars.D := RECOG.ProjectiveOrder(els[8]);
350        if not(vars.D in [2, 3, 5, 6, 7, 8, 10, 12, 15]) then
351            return fail;
352        fi;
353
354        if vars.D <> 7 then
355            continue;    # was jmp to CONJUGATE
356        fi;
357
358        els[9] := els[8]*els[3];
359        els[10] := els[8]*els[9];
360
361        vars.E := RECOG.ProjectiveOrder(els[10]);
362
363        if not(vars.E in [10, 12, 15]) then
364            return fail;
365        fi;
366        if vars.E <> 12 then
367            continue;    # was jmp to CONJUGATE
368        fi;
369        break;
370    until false;
371
372    return els{[2, 3]};
373end;
374
375# Created by bbtogap.py from Co3G1-find1 from the Atlas web page
376BBStdGenFinder.Co3 :=
377function(arg)
378    local vars,els,G;
379    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
380    els := ShallowCopy(arg);
381    vars := rec();
382    G := Group(arg);
383
384    # Black box algorithm to find standard generators of Co3
385
386    vars.F := 0;
387    vars.G := 0;
388    vars.V := 0;
389    repeat    # label SEMISTD
390        els[1] := PseudoRandom(G);
391        vars.A := RECOG.ProjectiveOrder(els[1]);
392        vars.V := vars.V + 1;
393        if vars.V > 1000 then
394            return fail;  # a timeout
395        fi;
396        if not(vars.A in [1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,21,22,
397                          23,24,30]) then
398            return fail;
399        fi;
400
401        if vars.F = 0 then
402            if vars.A in [9,18,24,30] then
403                vars.B := QuoInt(vars.A,3);
404                els[2] := els[1]^vars.B;
405                vars.F := 1;
406            fi;
407        fi;
408        if vars.G = 0 then
409            if vars.A = 20 then
410                els[3] := els[1]^5;
411                vars.G := 1;
412            fi;
413        fi;
414
415        if vars.F = 0 then
416            continue;    # was jmp to SEMISTD
417        fi;
418        if vars.G = 0 then
419            continue;    # was jmp to SEMISTD
420        fi;
421        break;
422    until false;
423
424    vars.X := 0;
425    repeat    # label CONJUGATE
426        vars.X := vars.X + 1;
427        if vars.X > 1000 then
428            return fail;  # a timeout
429        fi;
430        els[4] := PseudoRandom(G);
431        els[3] := els[3]^els[4];
432        els[5] := els[2]*els[3];
433        vars.D := RECOG.ProjectiveOrder(els[5]);
434        if not(vars.D in [4,5,6,7,8,9,10,11,12,14,15,18,20,22,23,24]) then
435            return fail;
436        fi;
437        if vars.D <> 14 then
438            continue;    # was jmp to CONJUGATE
439        fi;
440        break;
441    until false;
442
443    return els{[2, 3]};
444end;
445
446# Created by bbtogap.py from Co2G1-find1 from the Atlas web page
447BBStdGenFinder.Co2 :=
448function(arg)
449    local vars,els,G,toSEMISTD;
450    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
451    els := ShallowCopy(arg);
452    vars := rec();
453    G := Group(arg);
454
455    # Black box algorithm to find standard generators of Co2
456
457    vars.F := 0;
458    vars.G := 0;
459    vars.V := 0;
460    vars.X := 0;
461
462    repeat    # label SEMISTD
463        els[1] := PseudoRandom(G);
464        vars.A := RECOG.ProjectiveOrder(els[1]);
465        vars.V := vars.V + 1;
466        if vars.V > 1000 then
467            return fail;  # a timeout
468        fi;
469        if not(vars.A in [1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,23,24,
470                          28,30]) then
471            return fail;
472        fi;
473        if vars.F = 0 then
474            if vars.A in [16,18,28] then
475                vars.B := QuoInt(vars.A,2);
476                els[2] := els[1]^vars.B;
477                vars.F := 1;
478            fi;
479        fi;
480        if vars.G = 0 then
481            if vars.A in [15,30] then
482                vars.C := QuoInt(vars.A,5);
483                els[3] := els[1]^vars.C;
484                vars.G := 1;
485            fi;
486        fi;
487
488        if vars.F = 0 then
489            continue;    # was jmp to SEMISTD
490        fi;
491        if vars.G = 0 then
492            continue;    # was jmp to SEMISTD
493        fi;
494
495        vars.Y := 0;
496        vars.Z := 0;
497        vars.U := 0;
498        repeat    # label CONJUGATE
499            vars.X := vars.X + 1;
500            if vars.X > 1000 then
501                return fail;  # a timeout
502            fi;
503            vars.Y := vars.Y + 1;
504            els[4] := PseudoRandom(G);
505            els[3] := els[3]^els[4];
506            els[5] := els[2]*els[3];
507            vars.D := RECOG.ProjectiveOrder(els[5]);
508            if not(vars.D in [4,5,6,7,8,9,10,11,12,14,15,16,18,20,23,24,
509                              28,30]) then
510                return fail;
511            fi;
512
513            if vars.D = 7 then
514                vars.Z := 1;
515            fi;
516
517            if vars.Z = 0 then
518                if vars.Y > 35 then
519                    vars.G := 0;
520                    toSEMISTD := true;
521                    break;    # was jmp to SEMISTD
522                fi;
523
524                # Certain product orders are much more likely to
525                # occur with 5B elements (and vice versa)
526                if vars.D in [6,12,14,24,30] then
527                    vars.U := vars.U + 1;
528                fi;
529                if vars.D in [9,11,15,23] then
530                    vars.U := vars.U + 1;
531                fi;
532
533                if vars.U = 3 then
534                    # Probably a 5B element.
535                    vars.G := 0;
536                    toSEMISTD := true;
537                    break;    # was jmp to SEMISTD
538                fi;
539            fi;
540
541            if vars.D <> 28 then
542                continue;    # was jmp to CONJUGATE
543            fi;
544
545            # Once we've got y s.t. o(xy) = 28, we need to check
546            # o(xyy) = 9 if we don't yet know that y is in the right
547            # class.
548            if vars.Z = 0 then
549                els[6] := els[5]*els[3];
550
551                vars.E := RECOG.ProjectiveOrder(els[6]);
552
553                if not(vars.E in [9, 15]) then
554                    return fail;
555                fi;
556                if vars.E = 15 then
557                    vars.G := 0;
558                    toSEMISTD := true;
559                    break;    # was jmp to SEMISTD
560                fi;
561            fi;
562            toSEMISTD := false;
563            break;
564        until false;
565        if not(toSEMISTD) then break; fi;
566    until false;
567
568    return els{[2,3]};
569end;
570
571# Created by bbtogap.py
572BBStdGenFinder.Ly :=
573function(arg)
574    local vars,els,G;
575    if Length(arg) > 0 and IsList(arg[1]) then arg := arg[1]; fi;
576    els := ShallowCopy(arg);
577    vars := rec();
578    G := Group(arg);
579
580    # Black box algorithm to find standard generators of Ly
581
582    vars.F := 0;
583    vars.G := 0;
584    vars.V := 0;
585    repeat    # label SEMISTD
586        els[1] := PseudoRandom(G);
587        vars.A := RECOG.ProjectiveOrder(els[1]);
588        vars.V := vars.V + 1;
589        if vars.V > 1000 then
590            return fail;  # a timeout
591        fi;
592        if not(vars.A in [1,2,3,4,5,6,7,8,9,10,11,12,14,15,
593                 18,20,21,22,24,25,28,30,31,33,37,40,42,67]) then
594            return fail;
595        fi;
596        if vars.F = 0 then
597            if vars.A in [2,4,6,8,10,12,14,18,20,22,24,28,30,40,42] then
598                vars.B := QuoInt(vars.A,2);
599                els[2] := els[1]^vars.B;
600                vars.F := 1;
601            fi;
602        fi;
603        if vars.G = 0 then
604            if vars.A in [20,25,40] then
605                vars.C := QuoInt(vars.A,5);
606                els[3] := els[1]^vars.C;
607                vars.G := 1;
608            fi;
609        fi;
610    until vars.F <> 0 and vars.G <> 0;
611
612    vars.X := 0;
613    repeat    # label CONJUGATE
614        vars.X := vars.X + 1;
615        if vars.X > 3000 then
616            return fail;  # a timeout
617        fi;
618        els[4] := PseudoRandom(G);
619        els[3] := els[3]^els[4];
620        els[5] := els[2]*els[3];
621        vars.D := RECOG.ProjectiveOrder(els[5]);
622        if not(vars.D in [2,6,7,8,9,10,11,12,14,15,18,20,
623                      21,22,24,25,28,30,31,33,37,40,42,67]) then
624            return fail;
625        fi;
626        if vars.D <> 14 then
627            continue;    # was jmp to CONJUGATE
628        fi;
629
630        els[6] := els[5]*els[3];
631        els[7] := els[5]*els[5];
632        els[8] := els[7]*els[6];
633        vars.E := RECOG.ProjectiveOrder(els[8]);
634        if vars.E <> 67 then
635            continue;    # was jmp to CONJUGATE
636        fi;
637        break;
638    until false;
639    return els{[2,3]};
640end;
641
642SLPForElementGenSift := function(ri,x)
643  local s,y;
644  GenSift.HasOrderIn := SiftHasOrderInByProjOrder;
645  GenSift.IsOne := IsOneProjective;
646  GenSift.IsEq := IsEqualProjective;
647  repeat
648      y := GeneralizedSift(ri!.siftrec,x^-1,1/100);
649  until y[Length(y)] <> fail;
650  s := MakeCompleteSLP(ri!.siftrec,y);
651  # Do a security check: ==> not necessary, because the gensift does
652  # detect a wrong result!
653  #if ResultOfStraightLineProgram(s,NiceGens(ri)) <> x then
654  #    return fail;
655  #else
656  #fi;
657  return s;
658end;
659
660InstallGlobalFunction( "SporadicsWorkerGenSift", function(name,size,ri,G)
661  local Gm,r,siftrec,stdgens;
662  Gm := GeneratorsWithMemory(GeneratorsOfGroup(G));
663  repeat
664      stdgens := BBStdGenFinder.(name)(Gm);
665  until stdgens <> fail;
666  Setslptonice(ri,SLPOfElms(stdgens));
667  stdgens := StripMemory(stdgens);
668  ri!.siftrec := PrepareSiftRecords(PreSift.(name),
669                                    GroupWithGenerators(stdgens));
670  Setslpforelement(ri,SLPForElementGenSift);
671  SetFilterObj(ri,IsLeaf);
672  SetSize(ri,size);
673  return true;
674end);
675
676##
677##  This program is free software: you can redistribute it and/or modify
678##  it under the terms of the GNU General Public License as published by
679##  the Free Software Foundation, either version 3 of the License, or
680##  (at your option) any later version.
681##
682##  This program is distributed in the hope that it will be useful,
683##  but WITHOUT ANY WARRANTY; without even the implied warranty of
684##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
685##  GNU General Public License for more details.
686##
687##  You should have received a copy of the GNU General Public License
688##  along with this program.  If not, see <http://www.gnu.org/licenses/>.
689##
690
691