SES Home » Science Departments » Algebraic Cryptography Center » Software Search |  People Finder

# Software

 The CRAG Software Library FAQ ```// Copyright (C) 2006 Alexander Ushakov // Contents: Example for Subgroups of Free Groups. // // Principal Authors: Alexander Ushakov // // Revision History: // #include "Word.h" #include "SubgroupFG.h" int main( ) { int N = 5; int K = 6; int L = 7; // Create a random vector of K freely reduced words each of length L over the alphabet {x_1,...,x_N} vector< Word > generators; for( int i=0 ; i``````// How do I create a subgroup of a free group? SubgroupFG sbgp( N , generators ); ``````// How do I oupput a subgroup of a free group? cout << "SBGP = " << endl << sbgp << endl; ``````// How do I check whether two subgroups coincide? // Create another random subgroup with the same parameters vector< Word > generators2; for( int i=0 ; i``````// How do I find intersection of two subgroups? SubgroupFG sbgp3 = sbgp*sbgp2; ``````// How do I find a set of Nielsen Generators for a subgroup? vector< Word > niels_gens = sbgp.getNielsenGenerators( ); ``````// How do I get a FSA corresponing to a subgroup? IntLabeledGraph FSA = sbgp.getFSA( ); ``````// How do I check whether a word belongs to a subgroup? Word w = Word::randomWord( N , 15 ); // generate random word if( sbgp.doesBelong( w ) ) { // check if it belongs to a subgroup cout << "A word belongs to a subgroup" << endl; } else { cout << "A word does not belong to a subgroup" << endl; } ``````// If a word belongs to a subgroup how do I find actual product of initial generators giving the word? if( sbgp.doesBelong( w ) ) { Word decomposition = sbgp.express( w ); // output the decomposition Word::const_iterator w_it=decomposition.begin( ); for( int c=0 ; w_it!=decomposition.end( ) ; ++w_it, ++c ) cout << ( c>0 ? " * " : "" ) << ( *w_it>0 ? generators[*w_it-1] : -generators[-*w_it-1] ); cout << endl; } ``````// How do I compute the index of a subgroup in a free group? int index = sbgp.getIndex( ); ``````// How do I compute the rank of a subgroup? int rank = sbgp.getRank( ); return 0; } ```

 Stevens Institute of Technology • Hoboken, NJ • (201) 216-5000   Sitemap