public class SecretShareException
    extends RuntimeException
{
    // ==================================================
    // class static data
    // ==================================================

    private static final long serialVersionUID = 2193317873773384997L;

    // ==================================================
    // class static methods
    // ==================================================



    // ==================================================
    // instance data
    // ==================================================

    // ==================================================
    // factories
    // ==================================================

    // ==================================================
    // constructors
    // ==================================================


    /** Constructs a new runtime exception with the specified detail message.
     * The cause is not initialized, and may subsequently be initialized by a
     * call to {@link #initCause}.
     *
     * @param   message   the detail message. The detail message is saved for
     *          later retrieval by the {@link #getMessage()} method.
     */
    public SecretShareException(final String message)
    {
        super(message);
    }

    /**
     * Constructs a new runtime exception with the specified detail message and
     * cause.  <p>Note that the detail message associated with
     * <code>cause</code> is <i>not</i> automatically incorporated in
     * this runtime exception's detail message.
     *
     * @param  message the detail message (which is saved for later retrieval
     *         by the {@link #getMessage()} method).
     * @param  cause the cause (which is saved for later retrieval by the
     *         {@link #getCause()} method).  (A <code>null</code> value is
     *         permitted, and indicates that the cause is nonexistent or
     *         unknown.)
     */
    public SecretShareException(final String message,
                                final Throwable cause)
    {
        super(message, cause);
    }

    // ==================================================
    // public methods
    // ==================================================

    // ==================================================
    // non public methods
    // ==================================================
} public class CombinationGenerator<E>
        implements Iterator<List<E>>,
                   Iterable<List<E>>
{
    // ==================================================
    // class static data
    // ==================================================

    // ==================================================
    // class static methods
    // ==================================================

    public static void main(String[] args)
    {
        System.out.println("fact(5)=" + factorial(5));
        System.out.println("fact(3)=" + factorial(3));
        List<String> list = Arrays.asList("1", "2", "3", "4", "5");
        CombinationGenerator<String> combos = new CombinationGenerator<String>(list, 3);
        int count = 1;
        System.out.println("Total number=" + combos.getTotalNumberOfCombinations());
        for (List<String> combination : combos)
        {
            System.out.println(count + ": " + combination + " {" + combos.indexesAsString + "}");
            count++;
        }
    }

    // ==================================================
    // instance data
    // ==================================================

    private final List<E> list;

    // currentIndexes contains the indexes to use for the NEXT iteration
    private int[] currentIndexes;

    // indexesAsString contains either null or the CURRENT iteration's indexes
    private String indexesAsString;

    //
    private final BigInteger totalNumberOfCombinations;
    // ranges 0 to totalNumber, where "0" means "you haven't called next() yet"
    private BigInteger combinationNumber;

    // ==================================================
    // factories
    // ==================================================

    // ==================================================
    // constructors
    // ==================================================

    public CombinationGenerator(final List<E> inList,
                                final int inChoiceSize)
    {
        if (inChoiceSize < 1)
        {
            throw new SecretShareException("choice size cannot be less than 1:" + inChoiceSize);
        }

        if (inChoiceSize > inList.size())
        {
            throw new SecretShareException("choice size cannot be greater than size");
        }

        List<E> ourlist = new ArrayList<E>(inList);

        this.list = Collections.unmodifiableList(ourlist);

        this.currentIndexes = new int[inChoiceSize];
        for (int i = 0; i < inChoiceSize; i++)
        {
            this.currentIndexes[i] = i;
        }

        totalNumberOfCombinations = computeNfactdivkNkFact(this.list.size(), inChoiceSize);
        combinationNumber = BigInteger.ZERO;
    }



    /**
     * Return (n!) / ( k! * (n-k)! ).
     *
     * @param n
     * @param k
     * @return value from equation above
     */
    private BigInteger computeNfactdivkNkFact(final int n,
                                              final int k)
    {
        final int nminusk = n - k;

        BigInteger kfactTimesnmkfact = factorial(k).multiply(factorial(nminusk));
        BigInteger nfactorial = factorial(n);

        return nfactorial.divide(kfactTimesnmkfact);
    }



    // ==================================================
    // public methods
    // ==================================================

    public final BigInteger getCurrentCombinationNumber()
    {
        return combinationNumber;
    }

    public final BigInteger getTotalNumberOfCombinations()
    {
        return totalNumberOfCombinations;
    }

    @Override
    public Iterator<List<E>> iterator()
    {
        return this;
    }

    @Override
    public boolean hasNext()
    {
        return (currentIndexes != null);
    }

    public String getIndexesAsString()
    {
        return indexesAsString;
    }

    @Override
    public List<E> next()
    {
        if (! hasNext())
        {
            // ouch - Java's exception type design makes this a hard choice:
            //        It would be nice to throw new SecretShareException() here.
            throw new NoSuchElementException();
        }

        combinationNumber = combinationNumber.add(BigInteger.ONE);

        List<E> currentCombination = new ArrayList<E>();
        for (int i : currentIndexes)
        {
            currentCombination.add(list.get(i));
        }

        // capture before moving the indexes:
        indexesAsString = Arrays.toString(currentIndexes);

        moveIndexesToNextCombination();

        return currentCombination;
    }

    @Override
    public void remove()
    {
        // ouch again
        throw new UnsupportedOperationException();
    }

    // ==================================================
    // private methods
    // ==================================================

    private void moveIndexesToNextCombination()
    {
        for (int i = currentIndexes.length - 1, j = list.size() - 1; i >= 0; i--, j--)
        {
            if (currentIndexes[i] != j)
            {
                currentIndexes[i]++;
                for (int k = i + 1; k < currentIndexes.length; k++)
                {
                    currentIndexes[k] = currentIndexes[k - 1] + 1;
                }
                return;
            }
        }
        // otherwise, we are all done:
        currentIndexes = null;
    }
//    int i = r - 1;
//    while (a[i] == (n - r + i))
//    {
//        i--;
//    }
//    a[i] = a[i] + 1;
//    for (int j = i + 1; j < r; j++)
//    {
//        a[j] = a[i] + j - i;
//    }

    private static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = n; i > 1; i--)
        {
            ret = ret.multiply(BigInteger.valueOf(i));
        }
        return ret;
    }



} public final class EasyLinearEquation
{
    // ==================================================
    // class static data
    // ==================================================
    // want to turn on debug?  See EasyLinearEquationTest.enableLogging()
    private static Logger logger = Logger.getLogger(EasyLinearEquation.class.getName());

    private static boolean debugPrinting = false;

    // ==================================================
    // class static methods
    // ==================================================

    public static Logger getLogger()
    {
        return logger;
    }


    public static BigInteger[][] convertIntToBigInteger(int[][] inMatrix)
    {
        BigInteger[][] cvt = new BigInteger[inMatrix.length][];
        for (int i = 0, n = inMatrix.length; i < n; i++)
        {
            cvt[i] = new BigInteger[inMatrix[i].length];
            for (int c = 0, rn = inMatrix[i].length; c < rn; c++)
            {
                cvt[i][c] = BigInteger.valueOf(inMatrix[i][c]);
            }
        }
        return cvt;
    }

    // ==================================================
    // instance data
    // ==================================================
    private final List<Row> rows;

    // 'modulus' can be null, which means do not perform mod() on values
    private final BigInteger modulus;

    // ==================================================
    // factories
    // ==================================================

    /**
     * Create solver for polynomial equations.
     *
     * Polynomial linear equations are a special case, because the C,x,x^2,x^3 coefficients
     *  can be turned into the rows we need by being given:
     *    a) which "x" values were used
     *    b) what "constant" values were computed
     * This information happens to be exactly what the holder of a "Secret" in
     *     "Secret Sharing" has been given.
     *   So this constructor can be used to recover the secret if
     *     given enough of the secrets.
     *
     * @param xarray the "X" values
     * @param fofxarray the "f(x)" values
     * @return instance for solving this special case
     */
    public static EasyLinearEquation createForPolynomial(final BigInteger[] xarray,
                                                         final BigInteger[] fofxarray)
    {
        if (xarray.length != fofxarray.length)
        {
            throw new SecretShareException("Unequal length arrays are not allowed");
        }
        final int numRows = xarray.length;
        final int numCols = xarray.length + 1;

        BigInteger[][] cvt = new BigInteger[numRows][];
        for (int row = 0; row < numRows; row++)
        {
            cvt[row] = new BigInteger[numCols];

            fillInPolynomial(cvt[row],
                             fofxarray[row],
                             xarray[row]);
        }

        return create(cvt);
    }


    /**
     * Convenience factory to create an instance with 'int's instead of BigIntegers.
     *
     * @param inMatrix given in 'int's
     * @return instance
     */
    public static EasyLinearEquation create(int[][] inMatrix)
    {
        BigInteger[][] cvt = convertIntToBigInteger(inMatrix);

        return create(cvt);
    }


    /**
     * Most typical factory, for BigInteger arrays.
     *
     * @param inMatrix given in BigIntegers, where the first column is the constant
     *     and all the other columns are the variables
     * @return instance
     */
    public static EasyLinearEquation create(BigInteger[][] inMatrix)
    {
        EasyLinearEquation ret = null;
        final int width = inMatrix[0].length;
        for (BigInteger[] row : inMatrix)
        {
            if (width != row.length)
            {
                throw new SecretShareException("All rows must be " +
                                               width + " wide");
            }
        }
        List<Row> rows = new ArrayList<Row>();
        for (BigInteger[] row : inMatrix)
        {
            Row add = Row.create(row);
            rows.add(add);
        }
        ret = new EasyLinearEquation(rows);
        return ret;
    }


    // ==================================================
    // constructors
    // ==================================================

    private EasyLinearEquation(final List<Row> inRows)
    {
        this(inRows, null);
    }
    private EasyLinearEquation(final List<Row> inRows,
                               final BigInteger inModulus)
    {
        rows = new ArrayList<Row>();
        rows.addAll(inRows);

        modulus = inModulus;
    }

    public EasyLinearEquation createWithPrimeModulus(BigInteger primeModulus)
    {
        if (primeModulus != null)
        {
            return new EasyLinearEquation(this.rows, primeModulus);
        }
        else
        {
            throw new SecretShareException("modulus cannot be null");
        }
    }


    // ==================================================
    // public methods
    // ==================================================

    public BigInteger[][] getMatrix()
    {
        BigInteger[][] ret = new BigInteger[rows.size()][rows.get(0).size()];

        final int height = ret.length;
        final int width = ret[0].length;
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                ret[i][j] = rows.get(i).getColumn(j);
            }
        }

        return ret;
    }

    public EasySolve solve()
    {
        EasySolve ret = null;

        List<Row> solverows = new ArrayList<Row>();
        solverows.addAll(rows);
        debugRows("Initial rows", solverows, modulus);
        for (int workrowindex = 0, maxindex = solverows.size(); workrowindex < maxindex; workrowindex++)
        {
            Row otherrow = solverows.get(workrowindex);
            for (int fixindex = workrowindex + 1; fixindex < maxindex; fixindex++)
            {
                int columnIndexToCancel = workrowindex + 1;

                Row cancelrowr = solverows.get(fixindex).cancelColumn(columnIndexToCancel,
                                                                      otherrow,
                                                                      modulus);
                solverows.set(fixindex, cancelrowr);
            }
            debugRows("after workrowindex=" + workrowindex + " finished", solverows, modulus);
        }
        debugRows("after all loops", solverows, modulus);
        //
        // the matrix should look like this now:
        //
        // 33  a b c
        // -51 0 d e
        // -13 0 0 f
        // so, start at the bottom, and solve and cancel the other direction:
        for (int workrowindex = solverows.size() - 1; workrowindex >= 0; workrowindex--)
        {
            Row reducedToOne = solverows.get(workrowindex).solveThisRow(modulus);
            logger.fine("reverse, index=" + workrowindex + " is " + reducedToOne.debugRow());
            solverows.set(workrowindex, reducedToOne);
            for (int fixindex = workrowindex - 1; fixindex >= 0; fixindex--)
            {
                int columnIndexToCancel = workrowindex + 1;

                logger.finer("  going to cancel fixindex=" + fixindex + " is " +
                             solverows.get(fixindex).debugRow() + " using row " +
                             reducedToOne.debugRow());
                Row cancelrowr = solverows.get(fixindex).cancelColumn(columnIndexToCancel,
                                                                      reducedToOne,
                                                                      modulus);
                solverows.set(fixindex, cancelrowr);
            }
            debugRows("After reverse loopindex=" + workrowindex + " finished", solverows, modulus);
        }
        //
        // the matrix should look like this now:
        //
        //  3 1 0 0
        // -5 0 1 0
        // -3 0 0 1
        BigInteger[] answers = new BigInteger[solverows.size() + 1];
        answers[0] = null;
        for (int i = 1, n = answers.length; i < n; i++)
        {
            answers[i] = solverows.get(i - 1).getColumn(0);
        }
        ret = new EasySolve(answers);
        return ret;
    }
    private void debugRows(String where,
                           List<Row> solverows,
                           BigInteger useModulus)
    {
        // want to turn on debug?  See EasyLinearEquationUT.enableLogging()
        if (logger.isLoggable(Level.FINE))
        {
            logger.fine(where + " (modulus=" + useModulus + ")");
            for (Row row : solverows)
            {
                logger.fine(row.debugRow());
            }
        }
    }
    // ==================================================
    // non public methods
    // ==================================================
    public static class EasySolve
    {
        private final BigInteger[] answers;
        public EasySolve(BigInteger[] inAnswers)
        {
            answers = new BigInteger[inAnswers.length];
            System.arraycopy(inAnswers, 0, answers, 0, answers.length);
        }

        public BigInteger getAnswer(int i)
        {
            if (i < 0)
            {
                throw new SecretShareException("Answer index cannot be negative: " + i);
            }
            if (i == 0)
            {
                throw new SecretShareException("Answer index 0 is the constant, not an answer." +
                                               "  Use range 1-n [not 0-n-1]");
            }
            return answers[i];
        }

    }

    private static class Trial
    {
        private final String which;
        private final BigInteger result;
        private final boolean correct;

        public Trial(final String inWhich,
                     final BigInteger inOriginal,
                     final BigInteger inDivideby)
        {
            which = inWhich;
            result = inOriginal.divide(inDivideby);
            correct = result.multiply(inDivideby).equals(inOriginal);
        }

        public BigInteger getResult()
        {
            if (correct)
            {
                return result;
            }
            else
            {
                throw new SecretShareException("Tried to get result from non-correct trial");
            }
        }
        @SuppressWarnings("unused")
        public String dumpDebug()
        {
            return "Trial[" + which + " result=" + result;
        }


        /**
         * Construct all the permutations we need.
         */
        public static List<Trial> createList(final BigInteger original,
                                             final BigInteger divideby,
                                             final BigInteger useModulus)
        {
            List<Trial> list =  new ArrayList<Trial>();

            BigInteger o = original;
            int c = 0;
            Trial trial = new Trial("" + c, o, divideby);
            list.add(trial);
            boolean somethingBroke = false;
            while (! trial.correct)
            {
                c++;
                if (c > 10000)
                {
                    somethingBroke = true;
                    break;
                }
                o = o.add(useModulus);
                trial = new Trial("" + c, o, divideby);
            }
            if (somethingBroke)
            {
                getLogger().log(Level.SEVERE,
                                "limit exceeded.  original {0} divideby {1} useModulus {2}",
                                new Object[] { original, divideby, useModulus});
//                System.out.format("ERROR\noriginal %80s\n" +
//                                        "dividedby %80s\n" +
//                                        "modulus   %80s\n",
//                                        original,
//                                        divideby,
//                                        useModulus);
            }
//            c = 0;
//            while (! trial.correct)
//            {
//                c++;
//                if (c > 10000)
//                {
//                    throw new SecretShareException("two loop failure");
//                }
//                o = o.subtract(useModulus);
//                trial = new Trial("" + c, o, divideby);
//            }

            list.add(trial);
            return list;
        }
        /**
         * Pick the "best" correct result [if any].
         *
         */
        public static Trial pickSuccess(List<Trial> list)
        {
            if (list.get(list.size() - 1).correct)
            {
                return list.get(list.size() - 1);
            }
            else
            {
                getLogger().warning("trial[0] did not succeed.");
//                System.out.println("WARN: trial[0] did not succeed.");
                for (Trial ret : list)
                {
                    if (ret.correct)
                    {
                        return ret;
                    }
                }
                throw new SecretShareException("Programmer error, no trial correct, list.size=" + list.size());
            }
        }



        /**
         * Original implementation.  Wrong.
         */
        public static List<Trial> createList2(final BigInteger original,
                                             final BigInteger divideby,
                                             final BigInteger useModulus)
        {
            List<Trial> list =  new ArrayList<Trial>();

            list.add(new Trial("original", original, divideby));
            list.add(new Trial("modoriginal", original.mod(useModulus), divideby));
            list.add(new Trial("moddivide", original, divideby.mod(useModulus)));
            list.add(new Trial("mod both", original.mod(useModulus), divideby.mod(useModulus)));

            BigInteger gcd = original.gcd(divideby);
            if ((gcd != null) &&
                (gcd.compareTo(BigInteger.ONE) > 0))
            {
                BigInteger divO = original.divide(gcd);
                BigInteger divD = divideby.divide(gcd);
                list.add(new Trial("gcd original", divO, divD));
                list.add(new Trial("gcd modoriginal", divO.mod(useModulus), divD));
                list.add(new Trial("gcd moddivide", divO, divD.mod(useModulus)));
                list.add(new Trial("gcd both", divO.mod(useModulus), divD.mod(useModulus)));
            }
            return list;
        }
    }

    private static class Row
    {
        private final BigInteger[] cols;

        public static Row create(BigInteger[] in)
        {
            return new Row(in);
        }
        public Row(Row copy)
        {
            this(copy.cols);
        }
        private Row(BigInteger[] in)
        {
            cols = new BigInteger[in.length];
            System.arraycopy(in, 0, cols, 0, cols.length);
        }
        public int size()
        {
            return cols.length;
        }
        public BigInteger getColumn(final int index)
        {
            return cols[index];
        }
        /**
         * @return row with col[0] non-zero and one-and-only-one other column non-zero,
         *           all the other columns must be ZERO    OR
         *         throw exception
         * @throws SecretShareException if more than 2 columns [the 1st and 1 other] are non-zero
         */
        public Row solveThisRow(final BigInteger useModulus)
        {
            // Determine non-zero column:
            Integer nonZeroColumn = null;
            for (int col = 1, n = cols.length; col < n; col++)
            {
                if (! this.isColumnZero(col))
                {
                    if (nonZeroColumn != null)
                    {
                        logger.severe("Row cannot be solved:\n" + debugRow());
                        throw new SecretShareException("Two columns are non-zero, c=" +
                                                       nonZeroColumn + " and c=" + col);
                    }
                    else
                    {
                        nonZeroColumn = col;
                    }
                }
            }
            if (nonZeroColumn == null)
            {
                throw new SecretShareException("No non-zero column found in row; error");
            }


            Row ret = new Row(this);
            final BigInteger divideby = cols[nonZeroColumn];

            //
            // This is kind of like 'row.divideby()', except:
            // a) we know only 2 cols[] are non-zero
            // b) we absolutely need to make sure the result does not have a remainder,
            //    which means we have to "know" about the modulus sometimes
            //
            for (int col = 0, n = ret.cols.length; col < n; col++)
            {
                if ((col == 0) ||
                    (col == nonZeroColumn))
                {
                    BigInteger original = ret.cols[col];
                    BigInteger result = divideNormallyOrModulus(original, divideby, useModulus);
                           // this doesn't always work:  result = original.divide(divideby);
                    ret.cols[col] = result;
                }
                else
                {
                    // Leave the column alone.  Just do a safety-check:
                    if (! ret.isColumnZero(col))
                    {
                        throw new SecretShareException("Programmer error.  " +
                                                       "Column " + col + " must be zero, " +
                                                       "but instead is " + ret.getColumn(col));
                    }
                }
            }

            return ret;
        }


        /**
         * This _should be_ the implementation.
         * The problem is, it doesn't work.
         *
         */
        @SuppressWarnings("unused")
        private BigInteger divideNormallyOrModulusBroken(final BigInteger original,
                                                         final BigInteger divideby,
                                                         final BigInteger useModulus)
        {
            BigInteger result = null;

            if (useModulus == null)
            {
                result = original.divide(divideby);
            }
            else
            {
                result = original.divide(divideby);

                // do the "math check" before the modulus:
                safetyCheckDivision(result, divideby, original);

                // modfix: not proven to help reduce errors:  mod down the result
                //result = result.mod(useModulus);
            }

            return result;
        }

        /**
         * The modulus stuff is really strange.
         * Sometimes the divide-by just works.
         * Sometimes it is negative but "odd", and needs mod() to positive and "even".
         * Sometimes it is positive but "too big and odd" and needs mod() to a smaller "even" number.
         * Sometimes it needs multiple-add-the-modulus, especially for small values of
         *       the modulus versus large values of the coefficients.
         *
         * This routine just tries a bunch of things, including:
         *     1) original / divideby and
         *     2) (original mod useModulus) / divideby
         *  See class Trial.
         *
         * @param original
         * @param divideby
         * @param useModulus
         * @return
         */
        private BigInteger divideNormallyOrModulus(final BigInteger original,
                                                   final BigInteger divideby,
                                                   final BigInteger useModulus)
        {
            BigInteger result = null;

            if (useModulus == null)
            {
                result = original.divide(divideby);
            }
            else
            {
                // Create all of the trial "divide by" combinations
                List<Trial> list = Trial.createList(original, divideby, useModulus);

                // Pick the "best correct solution"
                Trial success = Trial.pickSuccess(list);

                if (success == null)
                {
                    throw new SecretShareException("All trial divide bys failed");
                }
                else
                {
                    result = success.getResult();
                    result = result.mod(useModulus);
                    //
                    // For big (192-bit) modulus, it is almost always "0"
                    // For small (e.g. 59561) modulus, it ranges from 0 to 20
                    // run "UT.testFirst()"
                    if (debugPrinting)
                    {
                        // Debug printing
                        if (! "0".equals(success.which))
                        {
                            System.out.println("Trial.sucess.which=" + success.which);
                        }
                    }
                }
            }

            // safetyCheckDivision(result, divideby, original);
            return result;
        }

        private void safetyCheckDivision(BigInteger result,
                                         BigInteger divideby,
                                         BigInteger original)
        {
            if (! result.multiply(divideby).equals(original))
            {
                throw new SecretShareException("division left remainder: original=" +
                                               original + "\nDivided by=" + divideby +
                                               "\nError.");
            }
        }
        private boolean isColumnZero(int index)
        {
            //        if (this.getColumn(index).compareTo(BigInteger.ZERO) == 0)
            if (0 == this.getColumn(index).compareTo(BigInteger.ZERO))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        public String debugRow()
        {
            String ret = "";
            String sep = "";
            for (BigInteger c : cols)
            {
                ret += sep;
                sep = ",";
                ret += c.toString();
            }
            return ret;
        }
        /**
         * @param index of column to cancel (range 1-to-n)
         * @param otherrow to use for the cancel operation
         * @return row with column value set to "0"
         */
        public Row cancelColumn(final int index,
                                final Row otherrow,
                                final BigInteger useModulus)
        {
            // special case: our col[index] is already zero:
            if (this.isColumnZero(index))
            {
                return this;
            }


            boolean samesign = this.sameSign(index, otherrow);
            BigInteger mult = this.getColumn(index);
            if (samesign)
            {
                mult = mult.negate();
            }
            Row cancel = otherrow.multiplyConstant(mult);

            mult = otherrow.getColumn(index);
            Row usethis = this.multiplyConstant(mult);
            if (! samesign)
            {
                usethis = usethis.negate();
            }

            Row ret = null;
            if (! usethis.sameSign(index, cancel))
            {
                ret = usethis.add(cancel);

                if (useModulus != null)
                {
                    if (ret.cols[0].signum() == -1)
                    {
                        // modfix: not proven to reduce errors: mod down the column value
                        //ret.cols[0] = ret.cols[0].mod(useModulus);

                        // modfix: let's try keeping cols[0] positive:
                        usethis = usethis.negate();
                        cancel = cancel.negate();
                        ret = usethis.add(cancel);
                    }
                }
            }
            else
            {
                throw new SecretShareException("prog error this(" + index + ")=" +
                                               this.getColumn(index) +
                                               " other(" + index + ")=" +
                                               cancel.getColumn(index));
            }
            return ret;
        }
        public boolean sameSign(final int index,
                                final Row other)
        {
            return sameSign(this.getColumn(index), other.getColumn(index));
        }
        private boolean sameSign(final BigInteger one,
                                 final BigInteger other)
        {
            int thisc  = one.compareTo(BigInteger.ZERO);
            int otherc = other.compareTo(BigInteger.ZERO);
            // change ZERO into positive
            thisc  = (thisc == 0)  ? 1 : thisc;
            otherc = (otherc == 0) ? 1 : otherc;

            boolean ret = (thisc == otherc);
            logger.finest("  samesign=" + ret + " on one=" + one +
                          " other=" + other);

            return ret;
        }
        public Row multiplyConstant(final BigInteger mult)
        {
            Row ret = new Row(this);

            for (int c = 0, n = cols.length; c < n; c++)
            {
                ret.cols[c] = this.cols[c].multiply(mult);
            }
            return ret;
        }
        @SuppressWarnings("unused")
        public Row addConstant(final BigInteger add)
        {
            Row ret = new Row(this);

            for (int c = 0, n = cols.length; c < n; c++)
            {
                ret.cols[c] = this.cols[c].add(add);
            }
            return ret;
        }
        public Row add(final Row add)
        {
            Row ret = new Row(this);

            for (int c = 0, n = cols.length; c < n; c++)
            {
                ret.cols[c] = this.cols[c].add(add.getColumn(c));
            }
            return ret;
        }

        public Row negate()
        {
            return multiplyConstant(BigInteger.valueOf(-1));
        }
    } // class Row



    /**
     *
     * @param array to fill with values
     * @param theconstant the value of the "C"
     * @param x the "x" value used
     */
    private static void fillInPolynomial(BigInteger[] array,
                                         BigInteger theconstant,
                                         BigInteger x)
    {
        // what was f(x) becomes our constant:
        array[0] = theconstant;
        // what was "C" becomes an unknown, with the coefficient "1"
        array[1] = BigInteger.ONE;

        // the other coefficients are x, x^2, x^3, x^4 etc:
        BigInteger current = BigInteger.ONE;
        for (int i = 2, n = array.length; i < n; i++)
        {
            current = current.multiply(x);
            array[i] = current;
        }
    }

} public class PolyEquationImpl
{

    // ==================================================
    // class static data
    // ==================================================

    // ==================================================
    // class static methods
    // ==================================================

    // ==================================================
    // instance data
    // ==================================================

    // [0] is x^0, i.e. "*1" the "constant term"
    // [1] is x^1, i.e. "*x" the "x term"
    // [2] is x^2, i.e. the "*x^2 term"
    private BigInteger[] coefficients;

    // ==================================================
    // factories
    // ==================================================

    /**
     * Helper factory to create instances.
     * Accepts 'int', converts them to BigInteger, and calls the constructor.
     *
     * @param args as int values
     * @return instance
     */
    public static PolyEquationImpl create(final int... args)
    {
        BigInteger[] bigints = new BigInteger[args.length];
        for (int i = 0, n = args.length; i < n; i++)
        {
            bigints[i] = BigInteger.valueOf(args[i]);
        }
        return new PolyEquationImpl(bigints);
    }
    // ==================================================
    // constructors
    // ==================================================
    public PolyEquationImpl(final BigInteger[] inCoeffs)
    {
        if (inCoeffs.length <= 0)
        {
            throw new SecretShareException("Must have at least 1 coefficient");
        }
        coefficients = new BigInteger[inCoeffs.length];

        for (int i = 0, n = inCoeffs.length; i < n; i++)
        {
            if (inCoeffs[i] == null)
            {
                throw new SecretShareException("Coefficient index=" + i +
                                               " is null, and cannot be null");
            }
            coefficients[i] = inCoeffs[i];
        }

        // Constraint check:
        for (Number n : coefficients)
        {
            if (n == null)
            {
                throw new SecretShareException("Programmer error - internal coefficient is null");
            }
        }
    }
    // ==================================================
    // public methods
    // ==================================================

    public BigInteger calculateFofX(final BigInteger x)
    {
        // pick up the 0th term directly:
        BigInteger ret = coefficients[0];

        // for each of the other terms:
        for (int term = 1, n = coefficients.length; term < n; term++)
        {
            // the index of term N is N:
            final int indexOfTerm = term;

            // the exponent of term N is N:
            final int powerOfTerm = term;

            BigInteger base = x;
            BigInteger power = base.pow(powerOfTerm);

            BigInteger add = coefficients[indexOfTerm].multiply(power);
            ret = ret.add(add);
        }
        return ret;
    }

    public String debugDump()
    {
        String ret = "PolyEqImpl[\n";
        for (int i = 0, n = coefficients.length; i < n; i++)
        {
            ret += "  x^" + i + " * " + coefficients[i].toString() + " + \n";
        }
        ret += "]";
        return ret;
    }

    public void debugPrintEquationCoefficients(PrintStream out)
    {
        // print the coefficients:
        for (int i = 0, n = coefficients.length; i < n; i++)
        {
            out.println("DEBUG: C" + i + " = " + coefficients[i]);
        }
        // print the equation:
        String sep = "";
        out.print("DEBUG: f(x) = ");
        for (int i = 0, n = coefficients.length; i < n; i++)
        {
            out.print(sep);
            sep = " + ";
            out.print(coefficients[i]);
            out.print("*x^" + i);
        }
        out.println("");
    }

    // ==================================================
    // non public methods
    // ==================================================
} public class BigRationalMatrix extends NumberMatrix<BigRational>
{

    protected BigRationalMatrix(BigRational[][] in)
    {
        super(in);
    }

    public BigRationalMatrix(int height, int width)
    {
        super(height, width);
    }

    public static BigRationalMatrix create(BigInteger[][] matrix)
    {
        final int height = matrix.length;
        final int width = matrix[0].length;
        BigRational[][] in = new BigRational[height][width];
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                in[i][j] = new BigRational(matrix[i][j]);
            }
        }
        return new BigRationalMatrix(in);
    }

    @Override
    protected BigRational[][] create(int height, int width)
    {
        return new BigRational[height][width];
    }

    @Override
    protected BigRational zero()
    {
        return BigRational.ZERO;
    }

    @Override
    protected BigRational one()
    {
        return BigRational.ONE;
    }


    @Override
    protected BigRational add(BigRational o1, BigRational o2)
    {
        return o1.add(o2);
    }

    @Override
    protected BigRational subtract(BigRational o1, BigRational o2)
    {
        return o1.subtract(o2);
    }

    @Override
    protected BigRational multiply(BigRational o1, BigRational o2)
    {
        return o1.multiply(o2);
    }

    @Override
    protected BigRational reciprocal(BigRational o1)
    {
        return o1.reciprocal();
    }

    @Override
    protected BigRational negate(BigRational o1)
    {
        return o1.negate();
    }

    @Override
    protected BigRational createValue(int v)
    {
        return new BigRational(v);
    }
} public abstract class NumberMatrix<E extends Number>
{
    protected E[][] matrix;

    /** Abstract method to create a matrix.
     * @param height of matrix
     * @param width of matrix
     * @return array-array of element
     */
    protected abstract E[][] create(int height, int width);

    /** Abstract method for defining zero for the matrix element.
     * @return element
     */
    protected abstract E zero();

    protected abstract E one();

    /** Abstract method for creating a cell with equivalent value "v".
     * @param v integer value
     * @return element
     */
    protected abstract E createValue(int v);

    /** Abstract method for adding two elements of the matrices.
     * @param o1 element
     * @param o2 element
     * @return element o1 + o2
     */
    protected abstract E add(E o1, E o2);

    /** Abstract method for subtracting elements of the matrices.
     * @param o1 element
     * @param o2 element
     * @return element o1 - o2
     */
    protected abstract E subtract(E o1, E o2);

    /** Abstract method for multiplying two elements of the matrices.
     * @param o1 element
     * @param o2 element
     * @return element o1 * o2
     */
    protected abstract E multiply(E o1, E o2);

    /** Abstract method for returning 1/E.
     * @param o1 element
     * @return element 1 / o1
     */
    protected abstract E reciprocal(E o1);

    /** Abstract method for megating element.
     * @param o1 element
     * @return element negative o1
     */
    protected abstract E negate(E o1);



    public E[][] getArray()
    {
        return matrix;
    }

    protected NumberMatrix(E[][] in)
    {
        matrix = in;
    }

    public NumberMatrix(int height, int width)
    {
        matrix = create(height, width);
    }

    public int getHeight()
    {
        return matrix.length;
    }

    public int getWidth()
    {
        return matrix[0].length;
    }

    public final boolean isValueOne(E other)
    {
        return one().equals(other);
    }

    public void fill(int j, int... rowsandcols)
    {
        if ((rowsandcols.length % j) != 0)
        {
            throw new SecretShareException("array size must be evenly divisible by j(" + j + ")");
        }
        int i = rowsandcols.length / j;
        if (i != getHeight())
        {
            throw new SecretShareException("refusing to resize height from " + getHeight() + " to " + i);
        }
        if (j != getWidth())
        {
            throw new SecretShareException("refusing to resize width from " + getWidth() + " to " + j);
        }
        for (int r = 0; r < i; r++)
        {
            for (int c = 0; c < j; c++)
            {
                int index = r * j + c;
                matrix[r][c] = createValue(rowsandcols[index]);
            }
        }
    }


    /** Add two matrices.
     * @param matrix1 first
     * @param matrix2 second
     * @return maxtrix 1 + 1
     */
    public E[][] addMatrix(E[][] matrix1, E[][] matrix2)
    {
        // Check bounds of the two matrices
        if ((matrix1.length != matrix2.length) ||
            (matrix1[0].length != matrix2[0].length))
        {
            throw new SecretShareException("The matrices do not have the same size");
        }

        E[][] result = //(E[][])new Number[matrix1.length][matrix1[0].length];
                create(matrix1.length, matrix1[0].length);

        // Perform addition
        for (int i = 0; i < result.length; i++)
        {
            for (int j = 0; j < result[i].length; j++)
            {
                result[i][j] = add(matrix1[i][j], matrix2[i][j]);
            }
        }

        return result;
    }

    /** Multiply two matrices.
     * @param matrix1 array-array
     * @param matrix2 array-array
     * @return matrix 1 * 2
     */
    public E[][] multiplyMatrix(E[][] matrix1, E[][] matrix2)
    {
        // Check bounds
        if (matrix1[0].length != matrix2.length)
        {
            throw new SecretShareException("The matrices do not have compatible size");
        }

        // Create result matrix
        E[][] result = //(E[][]) new Number[matrix1.length][matrix2[0].length];
                create(matrix1.length, matrix2[0].length);

        // Perform multiplication of two matrices
        for (int i = 0; i < result.length; i++)
        {
            for (int j = 0; j < result[0].length; j++)
            {
                result[i][j] = zero();

                for (int k = 0; k < matrix1[0].length; k++)
                {
                    result[i][j] = add(result[i][j],
                                   multiply(matrix1[i][k], matrix2[k][j]));
                }
            }
        }

        return result;
    }
    //  det(a(rs) a(rj)
    //      a(is) a(ij))  = a(rs)*a(ij)  -  a(is)*a(rj)
    //
    // det(c11 c12)                        ( a b )
    //    (c21 c22)  = c11*c22 - c21*c12   ( c d )
    //   called as det(0, 0, 1, 1) -- index starts at 0
    /**
     * Return the determinant.
     * @param matrix array
     * @param r index
     * @param s index
     * @param i index
     * @param j index
     * @return element determinant
     */
    public E determinant(E[][] matrix, int r, int s, int i, int j)
    {
        E a, b, c, d;
        a = matrix[r][s];
        b = matrix[r][j];
        c = matrix[i][s];
        d = matrix[i][j];
        E ad  = multiply(a, d); // matrix[r][s], matrix[i][j]);
        E bc = multiply(b, c); // matrix[i][s], matrix[r][j]);
        E ret = subtract(ad, bc);

        return ret;
    }

    /**
     * Print this matrix.
     * @param out printstream
     */
    public void printResult(PrintStream out)
    {
        printResult(getArray(), out);
    }

    /**
     * Print this array-array.
     * @param string header
     * @param matrix2 array-array
     * @param out printstream
     */
    public static void print(String string, Number[][] matrix2, PrintStream out)
    {
        if (out == null)
        {
            return;
        }
        out.println(string);
        printResult(matrix2, out);
    }

    /**
     * Print array-array.
     * @param m1 array-array
     * @param out printstream
     */
    public static void printResult(Number[][] m1, PrintStream out)
    {
        if (out == null)
        {
            return;
        }
        for (int i = 0; i < m1.length; i++)
        {
            for (int j = 0; j < m1[0].length; j++)
            {
                out.print(" " + m1[i][j]);
            }
            out.println("");
        }
    }

    /** Print matrices, the operator, and their operation result.
     * @param m1 array-array
     * @param m2 array-array
     * @param m3 array-array
     * @param op operator
     * @param out printstream
     */
    public static void printResult(Number[][] m1, Number[][] m2, Number[][] m3, char op, PrintStream out)
    {
        for (int i = 0; i < m1.length; i++)
        {
            for (int j = 0; j < m1[0].length; j++)
            {
                out.print(" " + m1[i][j]);
            }

            if (i == m1.length / 2)
            {
                out.print("  " + op + "  ");
            }
            else
            {
                out.print("     ");
            }

            for (int j = 0; j < m2.length; j++)
            {
                out.print(" " + m2[i][j]);
            }

            if (i == m1.length / 2)
            {
                out.print("  =  ");
            }
            else
            {
                out.print("     ");
            }

            for (int j = 0; j < m3.length; j++)
            {
                out.print(m3[i][j] + " ");
            }

            out.println();
        }
    }
} public class NumberSimplex<E extends Number>
{

    // ==================================================
    // class static data
    // ==================================================

    // ==================================================
    // class static methods
    // ==================================================

    // ==================================================
    // instance data
    // ==================================================

    /** Abstract method to create a matrix */
    private final NumberMatrix<E> matrix;
    /** index of the "B" column - i.e. the index of the constants */
    private final int constantsInThisColumnIndex; // 0-based index

    // computed values
    private NumberOrVariable<E>[] mTop;
    private NumberOrVariable<E>[] mSide;
    private E[][] mArrayhide;
    private Map<NumberOrVariable<E>, E> mAnswers;

    // ==================================================
    // factories
    // ==================================================

    // ==================================================
    // constructors
    // ==================================================


    public NumberSimplex(NumberMatrix<E> inMatrix, int inConstantsIndex)
    {
        matrix = inMatrix;
        constantsInThisColumnIndex = inConstantsIndex;
        //System.out.println("SIMPLEX cons matrix.h=" + matrix.getHeight() + " matrix.w=" + matrix.getWidth() +
        //                   " m.array.length=" +
        //                   matrix.getArray().length + " m.array[0].length=" + matrix.getArray()[0].length);

    }


    // ==================================================
    // public methods
    // ==================================================

    // .initForSolve(), then .solve(), then .getAnswer()

    public void initForSolve(PrintStream out)
    {
        final int width = matrix.getWidth();
        final int height = matrix.getHeight();

        mTop = fillInTopVariables(width - 1);
        mSide = fillInConstants(height);
        //System.out.println("INIT-SOLVE matrix.h=" + matrix.getHeight() +
        //        " matrix.w=" + matrix.getWidth() + " m.array.length=" +
        //        matrix.getArray().length + " m.array[0].length=" + matrix.getArray()[0].length);
        mArrayhide = fillInArray(matrix.getArray(), constantsInThisColumnIndex);

        nullPrintln(out, "INIT-SOLVE, TOP.length = " + mTop.length + " matrix.height=" + height + " matrix.w=" + width);
        printTopArraySide(out);

    }

    public void solve(PrintStream out)
    {
        final int height = mArrayhide.length;
        final int width = mArrayhide[0].length;
        if (height != width)
        {
            throw new SecretShareException("h=" + height + " w=" + width + " must match");
        }

        final int numberOfPivots = width;

        for (int p = 0; p < numberOfPivots; p++)
        {
            Pairij pairij = findPivot(mArrayhide);
            pivot(pairij.i, pairij.j);

            nullPrintln(out, "PIVOT COMPLETE, #" + p + " pivot=" + pairij);
            printTopArraySide(out);
        }
        mAnswers = computeAnswers(mTop, mArrayhide, mSide);
        printAnswers(out, mAnswers);
    }

    /**
     * @param i range 0-to-
     * @return answer
     */
    public E getAnswer(int i)
    {
        E ret = mAnswers.get(createVariableForIndex(i));
        if (ret != null)
        {
            return ret;
        }
        else
        {
            throw new SecretShareException("Could not find answer at index " + i + " answers=" + mAnswers);
        }
    }

    public E getConstantNumbered(int j)
    {
        return matrix.getArray()[j][constantsInThisColumnIndex];
    }


    // ==================================================
    // non public methods
    // ==================================================

    private void nullPrintln(PrintStream out, String line)
    {
        if (out != null)
        {
            out.println(line);
        }
    }
    private void printTopArraySide(PrintStream out)
    {
        print(mTop, mArrayhide, mSide, out);
    }


    private void printAnswers(PrintStream out, Map<NumberOrVariable<E>, E> answers)
    {
        if (out == null)
        {
            return;
        }
        for (NumberOrVariable<E> var : answers.keySet())
        {
            out.print(var);
            out.print("=");
            out.print(answers.get(var));
            out.println("");
        }
    }

    private Map<NumberOrVariable<E>, E> computeAnswers(NumberOrVariable<E>[] tops,
                                                       E[][] array,
                                                       NumberOrVariable<E>[] sides)
    {
        Map<NumberOrVariable<E>, E> ret = new HashMap<NumberOrVariable<E>, E>();

        // sanity checks:
        for (NumberOrVariable<E> v : tops)
        {
            if (v.isVariable())
            {
                throw new SecretShareException("Not a number: " + v);
            }
        }
        for (NumberOrVariable<E> v : sides)
        {
            if (v.isNumber())
            {
                throw new SecretShareException("Not a variable: " + v);
            }
        }
        final int height = array.length;
        final int width = array[0].length;
        for (int i = 0; i < height; i++)
        {
            E answer = zero();
            for (int j = 0; j < width; j++)
            {
                answer = add(answer, multiply(array[i][j], tops[j].getNumber()));
            }

            ret.put(sides[i], answer);
        }
        return ret;
    }



    private void pivot(int i, int j)
    {
        mArrayhide = createAbar(mArrayhide, i, j);

        // Swap top and side
        NumberOrVariable<E> tmp = mSide[i];
        mSide[i] = mTop[j];
        mTop[j] = tmp;
    }

    private Pairij findPivot(E[][] array)
    {
        List<Pairij> allPossible = findAllPossiblePivots(array);
        if (allPossible.size() > 0)
        {
            return allPossible.get(0);
        }
        else
        {
            return null;
        }
    }

    private List<Pairij> findAllPossiblePivots(E[][] array)
    {
        Pairij retValueIsOne = null;
        List<Pairij> ret = new ArrayList<Pairij>();
        final int height = array.length;
        final int width = array[0].length;
        AllDone:
        for (int i = 0; i < height; i++)
        {
            if (mSide[i].isNumber())
            {
                for (int j = 0; j < width; j++)
                {
                    if (mTop[j].isVariable())
                    {
                        // candidate found:
                        Pairij pair = new Pairij(i, j);
                        if (isValueOne(array[i][j]))
                        {
                            retValueIsOne = pair;
                            break AllDone;
                        }
                        ret.add(pair);
                    }
                }
            }
        }

        // Now make sure value "1" has priority slot #0 ...
        if (retValueIsOne != null)
        {
            ret.clear();
            ret.add(retValueIsOne);
        }

        return ret;
    }


    public static class Pairij
    {
        public final int i;
        public final int j;

        public Pairij(int i2, int j2)
        {
            i = i2;
            j = j2;
        }
        @Override
        public String toString()
        {
            return "Pairij[i=" + i + " j=" + j + "]";
        }
    }

    private void print(NumberOrVariable<E>[] top,
                       E[][] array,
                       NumberOrVariable<E>[] side,
                       PrintStream out)
    {
        if (out == null)
        {
            return;
        }
        final int width = array[0].length;
        final int height = array.length;
        String sep = "";
        for (int j = 0; j < width; j++)
        {
            out.print(sep);
            sep = " ";
            out.print(top[j]);
        }
        out.println("");

        for (int i = 0; i < height; i++)
        {
            sep = "";
            for (int j = 0; j < width; j++)
            {
                out.print(sep);
                sep = " ";
                out.print(array[i][j]);
            }
            out.print(sep);
            out.print(side[i]);
            out.println("");
        }
    }

    @SuppressWarnings("unchecked")
    private NumberOrVariable<E>[] createNumberOrVariable(int size)
    {
        return new NumberOrVariable[size];
    }

    private E[][] fillInArray(E[][] origin, int ignoreThisColumnIndex)
    {
        final int height = origin.length;
        final int width = origin[0].length;
        final int widthForReturn = width - 1;
        //System.out.println("origin.w=" + width + " origin.height=" + height);

        E[][] ret = create(height, widthForReturn);

        for (int i = 0; i < height; i++)
        {
            int targetJindex = 0;
            for (int j = 0; j < width; j++)
            {
                if (j != ignoreThisColumnIndex)
                {
                    ret[i][targetJindex] = origin[i][j];
                    targetJindex++;
                }
                else
                {
                    // skip this column
                }
            }
        }
        //System.out.println("Started at (w=" + width + " h=" + height + ") ended at
        //    (w=" + ret[0].length + " h=" + ret.length + ")");
        return ret;
    }



    private NumberOrVariable<E>[] fillInConstants(int height)
    {
        NumberOrVariable<E>[] ret = createNumberOrVariable(height);
        for (int j = 0; j < height; j++)
        {
            ret[j] = new NumberOrVariable<E>(getConstantNumbered(j));
        }
        return ret;
    }

    private NumberOrVariable<E>[] fillInTopVariables(int width)
    {
        NumberOrVariable<E>[] ret = createNumberOrVariable(width);
        for (int i = 0; i < width; i++)
        {
            ret[i] = createVariableForIndex(i);
        }
        return ret;
    }

    private NumberOrVariable<E> createVariableForIndex(int i)
    {
        return new NumberOrVariable<E>(Integer.toHexString(i + 10));
    }

    public static final class NumberOrVariable<E>
    {
        private E number;
        private String variable;

        public NumberOrVariable(E in)
        {
            if (in == null)
            {
                throw new SecretShareException("cannot be null");
            }
            number = in;
        }
        public NumberOrVariable(String name)
        {
            if (name == null)
            {
                throw new SecretShareException("cannot be null");
            }
            variable = name;
        }
        public boolean isNumber()
        {
            return number != null;
        }
        public boolean isVariable()
        {
            return variable != null;
        }
        public E getNumber()
        {
            return number;
        }
        public String getVariable()
        {
            return variable;
        }
        @Override
        public String toString()
        {
            if (isNumber())
            {
                return number.toString();
            }
            else
            {
                return variable;
            }
        }
        @Override
        public int hashCode()
        {
            final int prime = 31;
            int result = 1;
            result = prime * result +
                    ((number == null) ? 0 : number.hashCode());
            result = prime * result +
                    ((variable == null) ? 0 : variable.hashCode());
            return result;
        }
        @Override
        public boolean equals(Object obj)
        {
            if (this == obj)
            {
                return true;
            }
            if (obj == null)
            {
                return false;
            }
            if (getClass() != obj.getClass())
            {
                return false;
            }
            NumberOrVariable<?> other = (NumberOrVariable<?>) obj;
            if (number == null)
            {
                if (other.number != null)
                {
                    return false;
                }
            }
            else if (!number.equals(other.number))
            {
                return false;
            }

            if (variable == null)
            {
                if (other.variable != null)
                {
                    return false;
                }
            }
            else if (!variable.equals(other.variable))
            {
                return false;
            }

            return true;
        }
    }


    // Samples for testing
    // 2 -1 1 = 2
    // 1 2 -1 = 3
    // 3 1 2 = -1
    // answer x=2 y=-1 z=-3
    //    Output:  current pivots on [i=0 j=2], [i=1 j=1], [i=2 j=0]   13, 22, 31

    // 1 -3 1 = -2
    // 2 1 -1 = 6
    // 1 2 2 = 2

    // 1 -1 1 = 2
    // 1 1 0 = 1
    // 1 1 1 = 8

    // 3 -6 1 = 7
    // 1 2 1 = 5
    // -2 5 -2 = -1


    // AX = B
    // pivot on a(ij) to obtain
    // AbarXbar = Bbar
    // Abar = a(rs) =
    //   if r!=i and s!=j   (1/a(ij))*det(a(rs) a(rj)
    //                                    a(is) a(ij))
    //   if r!=i and s==j   a(rj) / a(ij)
    //   if r==i and s!=j   -1*a(is)/ a(ij)
    //   if r==i and s==j    1/a(ij)
    // Bbar = (b1 .. b(i-1) x(j) b(i+1) ... b(m))
    // Xbar = (x1 .. x(j-1) b(i) x(j+1) ... x(n))  // TODO: b(j)?? or b(i)  or x(i) above?
    //
    //   i m r height      j n s width
    //
    // det(c11 c12)
    //    (c21 c22)  = c11*c22 - c21*c12
    private E[][] createAbar(E[][] array, int i, int j)
    {
        E[][] ret = createSameSize(array);
        int height = ret.length;
        int width = ret[0].length;
        for (int r = 0; r < height; r++)
        {
            for (int s = 0; s < width; s++)
            {
                if ((r != i) && (s != j))
                {
                    E det = determinant(array, r, s, i, j);
                    E oneOverAij = reciprocal(array[i][j]);
                    ret[r][s] = multiply(det, oneOverAij);
                }
                else if ((r != i) && (s == j))
                {
                    E oneOverAij = reciprocal(array[i][j]);
                    ret[r][s] = multiply(array[r][j], oneOverAij);
                }
                else if ((r == i) && (s != j))
                {
                    E oneOverAij = reciprocal(array[i][j]);
                    E negAis = negate(array[i][s]);
                    ret[r][s] = multiply(negAis, oneOverAij);
                }
                else if ((r == i) && (s == j))
                {
                    E oneOverAij = reciprocal(array[i][j]);
                    ret[r][s] = oneOverAij;
                }
                else
                {
                    throw new SecretShareException("Programmer error");
                }
                //System.out.println("h=" + height + " w=" + width +
                // " r=" + r + " s=" + s + " val=" + ret[r][s]);
            }
        }

        return ret;
    }


    private E[][] createSameSize(E[][] array)
    {
        int height = array.length;
        int width = array[0].length;
        E[][] ret = create(height, width);
        //System.out.println("Same size of h=" + height + " w=" + width +
        // " result h=" + ret.length + " w=" + ret[0].length);
        return ret;
    }



    private E[][] create(int height, int width)
    {
        return matrix.create(height, width);
    }

    public boolean isValueOne(E v)
    {
        return matrix.isValueOne(v);
    }

    private E negate(E v)
    {
        return matrix.negate(v);
    }

    private E multiply(E o1, E o2)
    {
        return matrix.multiply(o1, o2);
    }

    private E add(E o1, E o2)
    {
        return matrix.add(o1, o2);
    }

    private E reciprocal(E v)
    {
        return matrix.reciprocal(v);
    }

    private E determinant(E[][] array, int r, int s, int i, int j)
    {
        return matrix.determinant(array, r, s, i, j);
    }

    private E zero()
    {
        return matrix.zero();
    }
} public final class BigIntStringChecksum
{
    // ==================================================
    // class static data
    // ==================================================

    /**
     * The prefix string that identifies the 6hex-6hex-md5sum6hex pattern
     *   we've invented to signify a BigIntegerChecksum value.
     * This value must be in lower case.
     */
    public static final String PREFIX_BIGINT_DASH_CHECKSUM = "bigintcs:".toLowerCase();

    /**
     * Constant for how many characters/digits are in each "6hex" section.
     */
    private static final int DIGITS_PER_GROUP              = 6;

    // 16 as a constant
    private static final int HEX_RADIX                     = 16;

    // ==================================================
    // class static methods
    // ==================================================

    // ==================================================
    // instance data
    // ==================================================

    /**
     * Contains a hex-encoded [i.e. RADIX 16] string of the big integer.
     * Does not contain dashes ("-")
     */
    private final String       asHex;

    /**
     * Contains a hex-encoded string of the md5sum of "asHex".
     * Our implementation is limited to 6 characters of checksum.
     */
    private final String       md5checksum;

    // ==================================================
    // factories
    // ==================================================

    /**
     * Utility to test if the input string can even -possibly- be a BigIntStringChecksum encoded.
     * This is check is "necessary, but not sufficient" for the input string
     *   to parse correctly.
     *
     * @param input the string to check
     * @return true if the string starts with (case-insensitive)
     *                 BigIntStringChecksum.PREFIX_BIGINT_DASH_CHECKSUM
     *         false all other cases
     */
    public static boolean startsWithPrefix(final String input)
    {
        boolean ret = false;
        if (input != null)
        {
            ret = input.toLowerCase().startsWith(PREFIX_BIGINT_DASH_CHECKSUM);
        }
        else
        {
            ret = false;
        }
        return ret;
    }

    /**
     * Take input string, and create the instance.
     * As of version 1.3.2 forward, the case of the INPUT is not relevant.
     * Note, however, that when the Checksum CCCCCC is computed, the hex hhhhhh- string
     *                is LOWER CASE.
     *
     * @param bics string in "bigintcs:hhhhhh-hhhhhh-CCCCCC" format
     * @return big integer string checksum object
     * @throws SecretShareException on error, such as null input, OR
     *               input doesn't start with correct prefix OR
     *               string does not have 0-9a-f digits OR
     *               checksum doesn't match.
     */
    public static BigIntStringChecksum fromString(final String bics)
    {
        boolean returnIsNegative = false;
        BigIntStringChecksum ret = null;
        if (bics == null)
        {
            createThrow("Input cannot be null", "<null>");
        }
        if (startsWithPrefix(bics))
        {
            String noprefix = bics.substring(PREFIX_BIGINT_DASH_CHECKSUM.length());
            String noprefixnosign = noprefix;
            if (noprefixnosign.startsWith("-"))
            {
                returnIsNegative = true;
                noprefixnosign = noprefixnosign.substring(1);
            }
            String[] split = noprefixnosign.split("-");
            if (split.length <= 1)
            {
                createThrow("Missing checksum section", bics);
            }
            else
            {
                String asHex = "";
                if (returnIsNegative)
                {
                    asHex = "-";
                }
                for (int i = 0, n = split.length - 1; i < n; i++)
                {
                    asHex += split[i];
                }
                String computedMd5sum = computeMd5ChecksumLimit6(asHex);
                String givenMd5sum = split[split.length - 1];
                if (computedMd5sum.equalsIgnoreCase(givenMd5sum))
                {
                    ret = new BigIntStringChecksum(asHex, computedMd5sum);
                }
                else
                {
                    createThrow("Mismatch checksum given='" + givenMd5sum +
                                "' computed='" + computedMd5sum + "'", bics);
                }
            }
        }
        else
        {
            createThrow("Input must start with '" +
                        PREFIX_BIGINT_DASH_CHECKSUM + "'",
                        bics);
        }
        // The call to .asBigInteger() should never throw an exception at this point.
        // But, if it is going to throw an exception, it is better to do it now rather than later:
        ret.asBigInteger();

        return ret;
    }

    /**
     * Take string as input, and either return an instance or return null.
     *
     * @param bics string in "bigintcs:hhhhhh-hhhhhh-CCCCCC" format
     * @return big integer string checksum object
     *         OR  null if incorrect format, error parsing, etc.
     */
    public static BigIntStringChecksum fromStringOrNull(String bics)
    {
        BigIntStringChecksum ret;
        if (bics == null)
        {
            ret = null;
        }
        else if (! startsWithPrefix(bics))
        {
            ret = null;
        }
        else
        {
            try
            {
                ret = fromString(bics);

                // completely test the input: make sure
                // asBigInteger will throw a SecretShareException on error
                if (ret.asBigInteger() == null)
                {
                    // asBigInteger() is not allowed to return null.
                    // but just in case it does:
                    throw new SecretShareException("Programmer error converting '" +
                                                   bics + "' to BigInteger");
                }
            }
            catch (SecretShareException e)
            {
                ret = null;
            }
        }
        return ret;
    }



    /**
     * Routine to construct an instance that allows you to print the hex strings.
     * Such as
     *    String s = BigIntStringChecksum create(biginteger).toString();
     *    s.equals("bigintcs:00f3ea-CBA3D0");
     *
     * @param in the big integer to hexify and md5 check sum
     * @return big integer string checksum object
     */
    public static BigIntStringChecksum create(final BigInteger in)
    {
        if (in == null)
        {
            throw new SecretShareException("Input BigInteger cannot be null");
        }

        final String inHex = in.toString(HEX_RADIX);
        final String inAsHex = pad(inHex);

        String md5checksum = computeMd5ChecksumLimit6(inAsHex);

        return new BigIntStringChecksum(inAsHex, md5checksum);
    }


    // ==================================================
    // constructors
    // ==================================================

    /**
     * Construct an instance of BISC.
     *  Performs NO validation of input.
     *
     * Normally 'private', but Unit Tests need access.
     *
     * @param inAsHex        just the hex, no dashes
     * @param inMd5checksum  just the hex, no dashes
     */
    /*default*/ BigIntStringChecksum(final String inAsHex,
                                     final String inMd5checksum)
    {
        asHex = inAsHex;
        md5checksum = inMd5checksum;
    }

    // ==================================================
    // public methods
    // ==================================================


    /**
     * @return the formatted string that can be parsed back into this object
     */
    @Override
    public String toString()
    {
        String hex6perdash = insertDashesIntoHex(asHex);
        return PREFIX_BIGINT_DASH_CHECKSUM +
               hex6perdash +
               "-" +
               md5checksum;
    }

    /**
     * Return the original BigInteger.
     *   (or throw an exception if something went wrong).
     *
     * @return BigInteger or throw exception
     * @throws SecretShareException if the hex is invalid
     */
    public BigInteger asBigInteger()
    {
        try
        {
            return new BigInteger(asHex, HEX_RADIX);
        }
        catch (NumberFormatException e)
        {
            throw new SecretShareException("Invalid input='" + asHex + "'", e);
        }
    }

    // ==================================================
    // non public methods
    // ==================================================

    /* private */static String bytesToHexString(byte... bytes)
    {
        return HexByteUtilities.printAsHex(bytes);
    }

    private static String insertDashesIntoHex(final String inAsHex)
    {
        String ret = "";
        final int lengthPerGroup = 6;
        String input = inAsHex;
        boolean returnIsNegative = false;
        if (input.startsWith("-"))
        {
            returnIsNegative = true;
            input = input.substring(1);
        }
        while ((input.length() % lengthPerGroup) != 0)
        {
            input = "0" + input;
        }
        String sep = "";
        for (int i = 0, n = input.length() / lengthPerGroup; i < n; i++)
        {
            ret += sep;
            sep = "-";
            ret += input.substring((i + 0) * lengthPerGroup,
                                   (i + 1) * lengthPerGroup);
        }
        if (returnIsNegative)
        {
            ret = "-" + ret;
        }
        return ret;
    }


    private static boolean testonlyUseInternalMd5Impl = false;

    private static byte[] computeMd5ChecksumFull(String inAsHex2)
    {
       Md5Checksummer md5summer = null;

       md5summer = Md5ChecksummerFactory.create();

       if (testonlyUseInternalMd5Impl)
       {
           // Normally, you use a "-D" on the command line to change md5sum class.
           // This is just for testing over-ride without needing that "-D" argument.
           // See Md5ChecksummerFactory.create()
           md5summer = Md5ChecksummerFactory
               .createFromClassName("com.tiemens.secretshare.md5sum.Md5ChecksummerImpl");
       }

        byte[] bytes = md5summer.createMd5Checksum(inAsHex2.toLowerCase().getBytes());

        return bytes;
    }

    /**
     * Note: only not-private to allow unit tests access.
     */
    /*private*/ static String computeMd5ChecksumLimit6(String inAsHex2)
    {
        byte[] bytes = computeMd5ChecksumFull(inAsHex2);

        String md5checksum = bytesToHexString(bytes[2],
                                              bytes[1],
                                              bytes[0]);
        return md5checksum;
    }


    /**
     **   @Throw SecretShareException always
     */
    private static void createThrow(String string,
                                    String bics)
    {
        throw new SecretShareException(string + "(input=" + bics + ")");
    }


    private static String pad(final String inHex)
    {
        final int lengthPerGroup = DIGITS_PER_GROUP;
        String useHex = inHex;
        boolean returnIsNegative = false;
        if (useHex.startsWith("-"))
        {
            useHex = useHex.substring(1);
            returnIsNegative = true;
        }
        String ret = useHex;
        while ((ret.length() % lengthPerGroup) != 0)
        {
            ret = "0" + ret;
        }
        if (returnIsNegative)
        {
            ret = "-" + ret;
        }
        return ret;
    }


} public final class BigIntUtilities
{


    // ==================================================
    // class static data
    // ==================================================
    private static final String UTF8 = "UTF-8";

    // ==================================================
    // class static methods
    // ==================================================

    /**
     * Converter class   : "Human"
     * Input format      : Any (human readable) string
     * Example input     : "This is my cat"
     *  gives BigInteger : 1711994770713785234966317640147316
     */
    public static class Human
    {
        /**
         * Convert a "human string" into a BigInteger by using the string's
         *   byte[] array.
         * This is NOT EVEN CLOSE to the same as new BigInteger("string").
         *
         * @param in a string like "This is my cat" or "123FooBar"
         * @return BigInteger
         * @throws SecretShareException on error
         */
        public static BigInteger createBigInteger(final String in)
        {
            BigInteger ret = null;
            try
            {
                byte[] b = in.getBytes(UTF8);
                ret = new BigInteger(b);
                return ret;
            }
            catch (UnsupportedEncodingException e)
            {
                // just can't happen, but if it does:
                throw new SecretShareException("UTF8 not found", e);
            }
        }

        /**
         * @param in the BigInteger whose bytes to use for the String
         *      usually the output of 'createBigInteger()', above.
         * @return String-ified BigInteger.bytes[]
         * @throws SecretShareException on error
         */
        public static String createHumanString(final BigInteger in)
        {
            if (in != null)
            {
                try
                {
                    byte[] b = in.toByteArray();
                    String s = new String(b, UTF8);
                    return s;
                }
                catch (UnsupportedEncodingException e)
                {
                    // just can't happen, but if it does...
                    throw new SecretShareException("UTF8 not found", e);
                }
            }
            else
            {
                return "null";
            }
        }
        public static boolean isValidUTF8(final BigInteger in)
        {
            if (in != null)
            {
                return isValidUTF8(in.toByteArray());
            }
            else
            {
                return false;
            }

        }
        public static boolean isValidUTF8(byte[] input)
        {

            CharsetDecoder cs = Charset.forName(UTF8).newDecoder();

            try
            {
                cs.decode(ByteBuffer.wrap(input));
                return true;
            }
            catch (CharacterCodingException e)
            {
                return false;
            }
        }
    }

    /**
     * Converter class   : "Bigint Checksum"
     * Input format      : String that starts with "bigintcs:", contains Hex groups
     * Example input     : bigintcs:005468-697320-697320-6d7920-636174-D23FBD
     *  gives BigInteger : 1711994770713785234966317640147316
     */
    public static class Checksum
    {
        /**
         * @param value string to test
         * @return true if this value is a big-int-checksum string
         *              (i.e. starts with "bigintcs:")
         *         false otherwise
         */
        public static boolean couldCreateFromStringMd5CheckSum(String value)
        {
            return BigIntStringChecksum.startsWithPrefix(value);
        }

        /**
         * @param hexStringWithMd5sum the bigintcs:hhhhh-CCCCCC string representation
         * @return the bigintstringchecksum
         * @throws SecretShareException on error
         */
        public static BigIntStringChecksum createBiscs(final String hexStringWithMd5sum)
        {
            return BigIntStringChecksum.fromString(hexStringWithMd5sum);
        }

        /**
         * @param hexStringWithMd5sum the bigintcs:hhhhh-CCCCCC string representation
         * @return the biginteger
         * @throws SecretShareException on error
         */
        public static BigInteger createBigInteger(final String hexStringWithMd5sum)
        {
            return createBiscs(hexStringWithMd5sum).asBigInteger();
        }
        /**
         * @param in BigInteger to convert
         * @return the bigintcs:hhhhh-CCCCCC string representation
         */
        public static String createMd5CheckSumString(final BigInteger in)
        {
            return BigIntStringChecksum.create(in).toString();
        }
    }

    /**
     * Converter class   : "Hex"
     * Input format      : String that starts with "0x", contains 0-9A-Fa-f only
     * Example input     : 0x54686973206973206d7920636174
     *  gives BigInteger : 1711994770713785234966317640147316
     */
    public static class Hex
    {
        private static final int HEX_RADIX = 16;

        /**
         * @param value string to test
         * @return true if this value is a hex-encoded string (i.e. starts with "0x")
         */
        public static boolean couldCreateFromStringHex(String value)
        {
            if ((value != null) && (value.length() >= 2))
            {
                if (value.substring(0, 2).equalsIgnoreCase("0x"))
                {
                    return true;
                }
            }
            return false;
        }

        /**
         * @param value string as hex-encoded number
         * @return BigInteger
         * @throws SecretShareException on error
         */
        public static BigInteger createBigInteger(String value)
        {
            if (value == null)
            {
                throw new SecretShareException("value cannot be null");
            }
            if (couldCreateFromStringHex(value))
            {
                String after = value.substring(2);
                try
                {
                    return new BigInteger(after, HEX_RADIX);
                }
                catch (NumberFormatException e)
                {
                    throw new SecretShareException("Hex parse failed for '" + value + "'");
                }
            }
            else
            {
                throw new SecretShareException("value must start with '0x' (input='" + value + "')");
            }
        }

        /**
         * @param bigInteger as input
         * @return "0x" + [hex-value-of-big-integer-input]
         * @throws SecretShareException on error
         */
        public static String createHexString(BigInteger bigInteger)
        {
            if (bigInteger == null)
            {
                throw new SecretShareException("input cannot be null");
            }
            return "0x" + bigInteger.toString(HEX_RADIX);
        }
    }



    public static BigInteger createPrimeBigger(BigInteger valueThatDeterminesNumberOfBits)
    {
        Random random = new SecureRandom();
        return createPrimeBigger(valueThatDeterminesNumberOfBits, random);
    }

    public static BigInteger createPrimeBigger(BigInteger valueThatDeterminesNumberOfBits,
                                               Random random)
    {
        int numbits = valueThatDeterminesNumberOfBits.bitLength() + 1;

        BigInteger ret = BigInteger.probablePrime(numbits, random);
        return ret;
    }



    // ==================================================
    // instance data
    // ==================================================



    // ==================================================
    // factories
    // ==================================================

    // ==================================================
    // constructors
    // ==================================================

    private BigIntUtilities()
    {
        // no instances
    }

    // ==================================================
    // public methods
    // ==================================================

    // ==================================================
    // non public methods
    // ==================================================
} public class BigRational extends Number implements Comparable<BigRational>
{
    // ==================================================
    // class static data
    // ==================================================
    private static final long serialVersionUID = -1035898074640211021L;

    public static final BigRational ZERO = new BigRational(0, 1);
    public static final BigRational ONE = new BigRational(1, 1);

    // ==================================================
    // class static methods
    // ==================================================

    // ==================================================
    // instance data
    // ==================================================

    private BigInteger numerator;
    private BigInteger denominator;

    // ==================================================
    // factories
    // ==================================================

    // ==================================================
    // constructors
    // ==================================================

    public BigRational(BigInteger value)
    {
        this(value, BigInteger.ONE);
    }

    public BigRational(BigInteger numerator, BigInteger denominator)
    {
        init(numerator, denominator);
    }

    public BigRational(int numerator, int denominator)
    {
        this(new BigInteger("" + numerator), new BigInteger("" + denominator));
    }

    public BigRational(int numerator)
    {
        this(numerator, 1);
    }

    /**
     * @param s string of rational number, e.g. "-105/3433"
     */
    public BigRational(String s)
    {
        String[] tokens = s.split("/");
        if (tokens.length == 2)
        {
            init(new BigInteger(tokens[0]), new BigInteger(tokens[1]));
        }
        else if (tokens.length == 1)
        {
            init(new BigInteger(tokens[0]), BigInteger.ONE);
        }
        else
        {
            throw new IllegalArgumentException("Bad format for rational number '" + s + "'");
        }
    }


    private void init(BigInteger num, BigInteger denom)
    {
        if (denom.equals(BigInteger.ZERO))
        {
            throw new ArithmeticException("Denominator is zero");
        }

        // normalize fraction
        BigInteger g = num.gcd(denom);
        numerator = num.divide(g);
        denominator = denom.divide(g);

        // ensure that denominator is positive
        if (denominator.compareTo(BigInteger.ZERO) < 0)
        {
            denominator = denominator.negate();
            numerator = numerator.negate();
        }
    }


    // ==================================================
    // public methods
    // ==================================================

    public BigInteger getNumerator()
    {
        return numerator;
    }

    public BigInteger getDenominator()
    {
        return denominator;
    }

    @Override
    public String toString()
    {
        if (denominator.equals(BigInteger.ONE))
        {
            return numerator + "";
        }
        else
        {
            return numerator + "/" + denominator;
        }
    }

    // return { -1, 0, + 1 } if a < b, a = b, or a > b
    @Override
    public int compareTo(BigRational b)
    {
        BigRational a = this;
        return a.numerator.multiply(b.denominator).compareTo(a.denominator.multiply(b.numerator));
    }

    public boolean isZero()
    {
        return compareTo(ZERO) == 0;
    }

    public boolean isPositive()
    {
        return compareTo(ZERO)  > 0;
    }

    public boolean isNegative()
    {
        return compareTo(ZERO)  < 0;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
        {
            return true;
        }
        if (obj == null)
        {
            return false;
        }
        if (getClass() != obj.getClass())
        {
            return false;
        }
        BigRational other = (BigRational) obj;
        if (denominator == null)
        {
            if (other.denominator != null)
            {
                return false;
            }
        }
        else if (!denominator.equals(other.denominator))
        {
            return false;
        }

        if (numerator == null)
        {
            if (other.numerator != null)
            {
                return false;
            }
        }
        else if (!numerator.equals(other.numerator))
        {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result +
                ((denominator == null) ? 0 : denominator.hashCode());
        result = prime * result +
                ((numerator == null) ? 0 : numerator.hashCode());
        return result;
    }

    /**
     * @param b to multiply
     * @return this * b
     */
    public BigRational multiply(BigRational b)
    {
        BigRational a = this;
        return new BigRational(a.numerator.multiply(b.numerator), a.denominator.multiply(b.denominator));
    }

    /**
     * @param b to add
     * @return this + b
     */
    public BigRational add(BigRational b)
    {
        BigRational a = this;
        BigInteger numerator   = a.numerator.multiply(b.denominator).add(b.numerator.multiply(a.denominator));
        BigInteger denominator = a.denominator.multiply(b.denominator);
        return new BigRational(numerator, denominator);
    }

    /**
     * @return -this
     */
    public BigRational negate()
    {
        return new BigRational(numerator.negate(), denominator);
    }

    /**
     * @param b to subtract
     * @return this - b
     */
    public BigRational subtract(BigRational b)
    {
        BigRational a = this;
        return a.add(b.negate());
    }

    /**
     * @return 1 / this
     */
    public BigRational reciprocal()
    {
        return new BigRational(denominator, numerator);
    }

    /**
     * @param b to divide by
     * @return this / b
     */
    public BigRational divide(BigRational b)
    {
        BigRational a = this;
        return a.multiply(b.reciprocal());
    }


    @Override
    public int intValue()
    {
        return (int) doubleValue();
    }

    @Override
    public long longValue()
    {
        return (long) doubleValue();
    }

    @Override
    public float floatValue()
    {
        return (float) doubleValue();
    }

    @Override
    public double doubleValue()
    {
        final int scale = 32;        // number of digits after the decimal place
        BigDecimal retnumerator   = new BigDecimal(numerator);
        BigDecimal retdenominator = new BigDecimal(denominator);
        BigDecimal quotient    = retnumerator.divide(retdenominator, scale, RoundingMode.HALF_EVEN);
        return quotient.doubleValue();
    }

    public boolean isBigInteger()
    {
        return denominator.equals(BigInteger.ONE);
    }

    public BigInteger bigIntegerValue()
    {
        if (isBigInteger())
        {
            return numerator;
        }
        else
        {
            throw new ArithmeticException("denominator is not 1, it is " + denominator);
        }
    }

    public BigInteger computeBigIntegerMod(BigInteger prime)
    {
        if (isBigInteger())
        {
            return bigIntegerValue();
        }
        else
        {
            //
            // Hideous implementation:  starting from this, loop, each time adding and subtracting prime
            //                          until a BigInteger appears
            //
            BigRational candidateGrow = this;
            BigRational candidateShrink = this;
            int count = 0;
            while ((! candidateGrow.isBigInteger()) && (! candidateShrink.isBigInteger()) && (count < 50000))
            {
                //System.out.println("FAILED biginteger of " + candidate.toString() + " mod=" + prime);

                BigRational trialGrow = new BigRational(candidateGrow.numerator.add(prime), candidateGrow.denominator);
                if (trialGrow.isBigInteger())
                {
                    return trialGrow.bigIntegerValue();
                }
                else
                {
                    candidateGrow = trialGrow;
                }

                BigRational trialShrink = new BigRational(candidateShrink.numerator.subtract(prime),
                                                          candidateShrink.denominator);
                if (trialShrink.isBigInteger())
                {
                    return trialShrink.bigIntegerValue();
                }
                else
                {
                    candidateShrink = trialShrink;
                }
                count++;
            }
            //System.out.println("BigRational = " + this.toString());
            //System.out.println(" mod div by = " + prime);
            //System.out.println("last candiate = " + candidateGrow);

            // If you reach here, this call will throw an exception:
            return candidateGrow.bigIntegerValue();
        }
    }
}
import java.io.PrintStream;
import java.math.BigInteger;
import java.security.SecureRandom;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
import java.util.UUID;
import com.tiemens.secretshare.exceptions.SecretShareException;
import com.tiemens.secretshare.math.combination.CombinationGenerator;
import com.tiemens.secretshare.math.equation.EasyLinearEquation;
import com.tiemens.secretshare.math.equation.PolyEquationImpl;
import com.tiemens.secretshare.math.matrix.BigRationalMatrix;
import com.tiemens.secretshare.math.matrix.NumberMatrix;
import com.tiemens.secretshare.math.matrix.NumberSimplex;
import com.tiemens.secretshare.math.type.BigIntStringChecksum;
import com.tiemens.secretshare.math.type.BigIntUtilities;
import com.tiemens.secretshare.math.type.BigRational;
     */
    public SplitSecretOutput split(final BigInteger secret,
                                   final Random random)
    {
        if (secret == null)
        {
            throw new SecretShareException("Secret cannot be null");
        }
        if (secret.signum() <= 0)
        {
            throw new SecretShareException("Secret cannot be negative");
        }
        if (publicInfo.getPrimeModulus() != null)
        {
            checkThatModulusIsAppropriate(publicInfo.getPrimeModulus(),
                                          secret);

        }

        BigInteger[] coeffs = new BigInteger[publicInfo.getK()];

        // create the equation by setting the coefficients:
        // [a] randomize the coefficients:
        randomizeCoeffs(coeffs, random, publicInfo.getPrimeModulus(), secret);
        // [b] set the constant coefficient to the secret:
        coeffs[0] = secret;

        final PolyEquationImpl equation = new PolyEquationImpl(coeffs);

        SplitSecretOutput ret = new SplitSecretOutput(this.publicInfo,
                                                      equation);

        for (int x = 1, n = publicInfo.getNforSplit() + 1; x < n; x++)
        {
            final BigInteger fofx = equation.calculateFofX(BigInteger.valueOf(x));
            BigInteger data = fofx;
            if (publicInfo.primeModulus != null)
            {
                data = data.mod(publicInfo.primeModulus);
            }
            final ShareInfo share = new ShareInfo(x, data, this.publicInfo);
            if (publicInfo.primeModulus != null)
            {
                if (data.compareTo(publicInfo.getPrimeModulus()) > 0)
                {
                    throw new RuntimeException("" + data + "\n" + publicInfo.getPrimeModulus() + "\n");
                }
            }
            ret.sharesInfo.add(share);
        }

        return ret;
    }

    private void println(String line)
    {
        if (out != null)
        {
            out.println(line);
        }
    }
    /**
     * Combine the shares generated by the split to recover the secret.
     *
     * @param usetheseshares shares to use - only the first "K" of size() will be used
     * @return the combine output instance [which in turn contains the recovered secret]
     */
    public CombineOutput combine(final List<ShareInfo> usetheseshares)
    {
        CombineOutput ret = null;

        sanityCheckPublicInfos(publicInfo, usetheseshares);

        if (true)
        {
            println(" SOLVING USING THESE SHARES, mod=" + publicInfo.getPrimeModulus());
            for (ShareInfo si : usetheseshares)
            {
                println("   " + si.share);
            }
            println("end SOLVING USING THESE SHARES");
        }
        if (publicInfo.getK() > usetheseshares.size())
        {
            throw new SecretShareException("Must have " + publicInfo.getK() +
                                           " shares to solve.  Only provided " +
                                           usetheseshares.size());
        }

        checkForDuplicatesOrThrow(usetheseshares);


        final int size = publicInfo.getK();
        BigInteger[] xarray = new BigInteger[size];
        BigInteger[] fofxarray = new BigInteger[size];
        for (int i = 0, n = size; i < n; i++)
        {
            xarray[i] = usetheseshares.get(i).getXasBigInteger();
            fofxarray[i] = usetheseshares.get(i).getShare();
        }
        EasyLinearEquation ele =
            EasyLinearEquation.createForPolynomial(xarray, fofxarray);
        if (publicInfo.getPrimeModulus() != null)
        {
            ele = ele.createWithPrimeModulus(publicInfo.getPrimeModulus());
        }

        BigInteger solveSecret = null;

        if (false)
        {
            EasyLinearEquation.EasySolve solve = ele.solve();

            solveSecret = solve.getAnswer(1);
        }
        else
        {
            BigInteger[][] matrix = ele.getMatrix();
            NumberMatrix.print("SS.java", matrix, out);
            println("CVT matrix.height=" + matrix.length + " width=" + matrix[0].length);
            BigRationalMatrix brm = BigRationalMatrix.create(matrix);