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