// Path: src/main/java/com/tiemens/secretshare/exceptions/SecretShareException.java
// 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
//     // ==================================================
// }


import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import com.tiemens.secretshare.exceptions.SecretShareException;
/*******************************************************************************
 * Copyright (c) 2009, 2014 Tim Tiemens.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the GNU Lesser Public License v2.1
 * which accompanies this distribution, and is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 *
 * Contributors:
 *     Tim Tiemens - initial API and implementation
 *******************************************************************************/
package com.tiemens.secretshare.math.equation;




/**
 * "Easy" implementation of linear equation solver.
 *
 *
 * Example: given 3 equations like:
 * 1491 =  83a + 32b + 22c
 *  329 =   5a + 13b + 22c
 *  122 =   3a +  2b + 19c
 * The goal is to solve for a, b, and c [3 unknowns, 3 equations].
 *
 * The problem above is encoded into a matrix of numbers like:
 *  1491   83   32   22
 *   329    5   13   22
 *   122    3    2   19
 * and stored in this class as a List[Row] objects.
 *
 * Then, this class can "solve" it into the 'diagonal 1', giving:
 *   11    1    0    0
 *   16    0    1    0
 *    3    0    0    1
 *  Which in turn means that a=11, b=16 and c=3
 *
 *
 * This implementation is called "easy" because it is really straight-forward,
 *   but also really inefficient.
 * Values are "canceled" by multiplying the two together.
 * e.g. "8" and "4" just needs the "4" to be multiplied by 2, then subtracted.
 * This implementation takes 8*4 and subtracts 4*8 because that just works, and you don't
 *   need to compute the least common multiple.
 *
 * This implementation is also "easy" since it doesn't use any lin-eq library.
 *   There are a lot of those libraries available: it turns out it was easier
 *   to write this class than to figure out how to use the horrible APIs they presented.
 *   [The ones with good APIs didn't support BigInteger]
 *
 * @author tiemens
 *
 */
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)
        {
// Path: src/main/java/com/tiemens/secretshare/exceptions/SecretShareException.java
// 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
//     // ==================================================
// }


// Path: src/main/java/com/tiemens/secretshare/math/equation/EasyLinearEquation.java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import com.tiemens.secretshare.exceptions.SecretShareException;

/*******************************************************************************
 * Copyright (c) 2009, 2014 Tim Tiemens.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the GNU Lesser Public License v2.1
 * which accompanies this distribution, and is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 *
 * Contributors:
 *     Tim Tiemens - initial API and implementation
 *******************************************************************************/
package com.tiemens.secretshare.math.equation;




/**
 * "Easy" implementation of linear equation solver.
 *
 *
 * Example: given 3 equations like:
 * 1491 =  83a + 32b + 22c
 *  329 =   5a + 13b + 22c
 *  122 =   3a +  2b + 19c
 * The goal is to solve for a, b, and c [3 unknowns, 3 equations].
 *
 * The problem above is encoded into a matrix of numbers like:
 *  1491   83   32   22
 *   329    5   13   22
 *   122    3    2   19
 * and stored in this class as a List[Row] objects.
 *
 * Then, this class can "solve" it into the 'diagonal 1', giving:
 *   11    1    0    0
 *   16    0    1    0
 *    3    0    0    1
 *  Which in turn means that a=11, b=16 and c=3
 *
 *
 * This implementation is called "easy" because it is really straight-forward,
 *   but also really inefficient.
 * Values are "canceled" by multiplying the two together.
 * e.g. "8" and "4" just needs the "4" to be multiplied by 2, then subtracted.
 * This implementation takes 8*4 and subtracts 4*8 because that just works, and you don't
 *   need to compute the least common multiple.
 *
 * This implementation is also "easy" since it doesn't use any lin-eq library.
 *   There are a lot of those libraries available: it turns out it was easier
 *   to write this class than to figure out how to use the horrible APIs they presented.
 *   [The ones with good APIs didn't support BigInteger]
 *
 * @author tiemens
 *
 */
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");