// global variables

letsnums = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789';
others = '`~!@#$%^&*()-_=+[{]}\\|;:\'",<.>/?';
legalchars = letsnums + others;

function writeCharacterTable ()
{
    var numcols = 8;
    document.write( '<table border=0><tr>' );
    var j, k;
    for ( j = 0 ; j < numcols ; j++ ) {
        if ( j ) document.write( '<th> &nbsp; &nbsp; &nbsp; </th>' );
        document.write( '<th align=\'right\'>#&nbsp;</th>'
                      + '<th align=\'left\'>&nbsp;Sym</th>' );
    }
    document.write( '</tr>\n' );
    var partway = 13;//Math.ceil( legalchars.length / numcols );
    for ( j = 0 ; j < partway ; j++ ) {
        document.write( '<tr>' );
        for ( k = 0 ; k < numcols ; k++ ) {
            if ( k ) document.write( '<td></td>' );
            var n = k*partway + j;
            if ( n < legalchars.length ) {
                var c = legalchars.charAt( n );
                if ( c == ' ' ) c = '(spc)';
                document.write( '<td align=\'right\'>' + n + '&nbsp;</td>'
                              + '<td align=\'left\'>&nbsp;' + c + '</td>' );
            } else {
                document.write( '<td></td><td></td>' );
            }
        }
        document.write( '</tr>\n' );
    }
    document.write( '</table>\n' );
}

function writeOtherChars ()
{
    var j;
    for ( j = 0 ; j < others.length ; j++ ) {
        if ( j ) document.write( ' ' );
        document.write( others.charAt( j ) );
    }
}

// routines for verifying input

function checkInt ( inp, name, positive, out )
{
    var tocheck = parseInt( inp.value );
    var error = positive ? ( 'Error: ' + name + ' must be a positive integer.\n' )
                         : ( 'Error: ' + name + ' must be an integer.\n' );
    if ( isNaN( tocheck ) ) {
        out.value += error;
        return 0;
    }
    if ( positive && ( tocheck <= 0 ) ) {
        out.value += error;
        return positive ? 0 : 'error';
    }
    inp.value = tocheck;
    return tocheck;
}

function checkMessage ( inp, name, out )
{
    var tocheck = inp.value;
    var i;
    if ( !tocheck.length ) {
        out.value += 'Error: no message given in ' + name + '.\n';
        return 0;
    }
    for ( i = 0 ; i < tocheck.length ; i++ ) {
        if ( legalchars.search( tocheck.charAt( i ) ) < 0 ) {
            out.value += 'Error: ' + name + ' uses invalid symbol (#'
                                   + (i+1) + ').\n';
            return 0;
        }
    }
    return tocheck;
}

// number-theoretic utility functions

function mymod ( n, m )
{
    var oldmod = n % m;
    if ( n >= 0 ) return oldmod; else return oldmod + m;
}

function gcd ( a, b )
{
    var m = mymod( a, b );
    if ( !m ) return b;
    return gcd( b, m );
}

function extendedEuclidean ( x, y, out )
{
    var origx, origy, a1, a2, b1, b2, a, b, q, r;
    if ( out )
        out.value += 'Using the technique from pp. 66-7 of the textbook:\n';
    origx = x;  origy = y;
    a2 = b1 = 1;
    if ( out ) out.value += x + '  1  0\n';
    a1 = b2 = 0;
    if ( out ) out.value += y + '  0  1\n';
    q = Math.floor( x / y );
    r = x - y*q;
    a = q;  b = 0; // in case r is 0
    while ( r ) {
        a = a2 - q*a1;
        b = b2 - q*b1;
        if ( out ) out.value += r + '  ' + a + '  ' + b + '\n';
        a2 = a1;  a1 = a;
        b2 = b1;  b1 = b;
        x = y;  y = r;
        q = Math.floor( x / y );
        r = x - y*q;
    }
    if ( out ) {
        out.value += a + '(' + origx + ') + ' + b + '(' + origy + ') = '
                       + a*origx + ' + ' + b*origy + ' = '
                       + (a*origx+b*origy) + '\n';
        out.value += 'Answer:  a = ' + a + ',  b = ' + b + '\n';
    }
    return new Array( a, b );
}

function multiplicativeInverse ( elt, modthis )
{
    if ( gcd( elt, modthis ) != 1 ) {
        alert( 'Error: Trying to find multiplicative inverse of\n'
             + elt + ' mod ' + modthis + ', but ' + elt + ' and ' + modthis + '\n'
             + 'are not relatively prime.  Returning 0 as an error indicator.' );
        return 0;
    }
    return mymod( extendedEuclidean( elt, modthis, 0 )[0], modthis );
}

function Mtosmodr ( M, s, r )
{
    var i, p, origs = s, origM = M;
    if ( s < 0 ) {
        s = -s;
        M = multiplicativeInverse( M, r );
    }
    for ( i = 0 ; Math.pow( 2, i ) <= s ; i++ ) { }
    var bits = new Array( i );
    for ( i = 0 ; i < bits.length ; i++ ) bits[i] = 0;
    for ( i = bits.length-1 ; i >= 0 ; i-- ) {
        p = Math.pow( 2, i );
        if ( p <= s ) { bits[i] = 1; s -= p; }
    }
    p = M;
    var result = 1;
    for ( i = 0 ; i < bits.length ; i++ ) {
        if ( bits[i] ) result = mymod( result * p, r );
        p = mymod( p * p, r );
    }
    return result;
}

// event handlers for each algorithm

function doAlg1 ()
{
    var out = document.alg1.alg1out;
    out.value = '';
    var x = checkInt( document.alg1.alg1inpx, 'x', 1, out );
    var y = checkInt( document.alg1.alg1inpy, 'y', 1, out );
    if ( !x || !y ) return;
    if ( gcd( x, y ) != 1 ) {
        out.value += 'Error: gcd( x, y ) must be 1.\n';
        return;
    }
    extendedEuclidean( x, y, out );
}

function doAlg2 ()
{
    var out = document.alg2.alg2out;
    out.value = '';
    var b = checkInt( document.alg2.alg2inpb, 'b', 1, out );
    var c = checkInt( document.alg2.alg2inpc, 'c', 1, out );
    var m = checkInt( document.alg2.alg2inpm, 'm', 1, out );
    var n = checkInt( document.alg2.alg2inpn, 'n', 1, out );
    if ( !b || !c || !m || !n ) return;
    if ( gcd( m, n ) != 1 ) {
        out.value += 'Error: gcd( m, n ) must be 1.\n';
        return;
    }
    /*
    if ( m <= n ) {
        out.value += 'Error: m must be greater than n.\n';
        return;
    }
    */
    var xy = extendedEuclidean( m, n, 0 );
    out.value += 'Using the technique from pp. 66-7 of the textbook\n'
               + 'finds ' + xy[0] + 'm + ' + xy[1] + 'n = '
               + xy[0]*m + ' + ' + xy[1]*n + ' = 1.\n\n';
    var ans = b*n*xy[1] + c*m*xy[0];
    out.value += 'As on p. 98 of the textbook, the answer is therefore\n'
               + xy[1] + 'bn + ' + xy[0] + 'cm = '
               + b*n*xy[1] + ' + ' + c*m*xy[0] + ' = '
               + ( b*n*xy[1] + c*m*xy[0] ) + '.\n\n';
    if ( ( ans >= m*n ) || ( ans < 0 ) )
        out.value += 'Because we want the answer to be less than mn,\n'
                   + 'i.e. less than ' + (m*n) + ', '
                   + 'we take instead ' + mymod( ans, m*n ) + ', which is\n'
                   + 'congruent to ' + ans + ' mod ' + (m*n) + '.\n';
}

function doAlg3 ()
{
    var out = document.alg3.alg3out;
    out.value = '';
    var M = checkMessage( document.alg3.alg3inpM, 'M', out );
    var r = checkInt( document.alg3.alg3inpr, 'r', 1, out );
    var s = checkInt( document.alg3.alg3inps, 's', 1, out );
    if ( !M || !r || !s ) return;
    var blocksize = -1;
    var maxblocknum = 0;
    while ( maxblocknum < r ) {
        maxblocknum = maxblocknum * 100 + 99;
        blocksize++;
    }
    if ( blocksize <= 0 ) {
        out.value += 'Error: r is too small even for one-letter blocks.\n';
        return;
    }
    while ( mymod( M.length, blocksize ) ) M += ' ';
    out.value += 'With r = ' + r + ', blocks up to length ' + blocksize
                             + ' are possible.\n';
    out.value += 'Text portion  -->  as number  ~~>  encrypted\n';
    var thisblock = '', thischar, blockval, encrypted;
    for ( i = 0 ; i < M.length ; i++ ) {
        if ( !mymod( i, blocksize ) ) {
            out.value += 'Block ' + Math.floor( i / blocksize + 1 ) + ': "';
            thisblock = 0;
            thischar = '';
        }
        out.value += M.charAt( i );
        thischar = legalchars.search( M.charAt( i ) );
        thisblock = thisblock * 100 + thischar;
        thischar = ''+thischar;
        while ( thischar.length < 2 ) thischar = '0' + thischar;
        if ( !mymod( i + 1, blocksize ) ) {
            blockval = parseInt( thisblock );
            encrypted = Mtosmodr( blockval, s, r );
            out.value += '"   -->   ' + thisblock + '  ~~>  ' + encrypted + '\n';
        }
    }
}

function doAlg4 ()
{
    var out = document.alg4.alg4out;
    out.value = '';
    var x = checkInt( document.alg4.alg4inpx, 'x', 1, out );
    var y = checkInt( document.alg4.alg4inpy, 'y', 0, out );
    var m = checkInt( document.alg4.alg4inpm, 'm', 1, out );
    if ( !x || !m || ( y == 'error' ) ) return;
    ans = Mtosmodr( x, y, m );
    out.value += x + '^' + y + ' is congruent to ' + ans + ' mod ' + m + '.\n';
}