AKS - Невозможно скомпилировать 16-битное целое число для проверки простоты

Question

Я пытаюсь выполнить проверку простоты 16-битного числа с помощью алгоритма AKS.Я продолжаю получать ошибку.Может кто-нибудь, пожалуйста, скомпилируйте мои коды и помогите мне с ошибкой.(пример номера, который я хочу скомпилировать: 1425412525412545.)

Это мой класс AKSPrime:

import java.math.BigInteger;

public class AKSPrime
{
public static void main(String[] args)
{
    AKSPrime p = new AKSPrime();

    TextReader k = new TextReader();

    System.out.print("Input number for primality testing: ");

    int i = k.readInt();

    System.out.println("Is " + i + " prime? " + p.isPrime(i));
}
public boolean isPrime(int numberToTest)
{
    boolean prime = true;
    boolean flag = true;
    boolean suitableQFound = false;
    boolean polynomialsCongruent = true;
    int b, q;
    int suitableQ;
    double power;

    for(int a = 2; a <= Math.sqrt(numberToTest); a++)
    {
        b = 2;
        power = Math.pow(a, b);

        while(!(power > numberToTest))
        {
            power = Math.pow(a, b);

            if(power == numberToTest)
            {
                prime = false;
                break;
            }

            b++;
        }
    }

    // Algorithm Line 2
    int r = 2;

    // Algorithm Line 3
    while( r < numberToTest && flag && !suitableQFound)
    {
        //Algorithm Line 4
        if(GCD(numberToTest, r) != 1)
        {
            return false;
        }

        //Algorithm Line 5
        if(nonAKSisPrime(r))
        {
            // Algorithm Line 6
            q = largestPrimeFactor(r - 1);
            double sqrtR = Math.sqrt(r);
            double logN = Math.log(numberToTest)/Math.log(2);

            // Algorithm Line 7
            if( q >= 4*Math.sqrt(r)*Math.log(numberToTest)/Math.log(2) )
            {
                // Algorithm Line 8
                suitableQ = q;
                suitableQFound = true;
            }
        }

        // Algorithm Line 9
        if(!suitableQFound)
            r++;
    }


    for(int a = 1; a <= 2 * Math.sqrt(r) * Math.log(numberToTest)/Math.log(2); a++)
    {

        PolynomialArray poly1 = new PolynomialArray();
        poly1.binomialExpansionViaSquaring(-1 * a, numberToTest);

        int [] coeffs2 = {1, numberToTest, -1 * a, 0};
        PolynomialArray poly2 = new PolynomialArray(coeffs2);

        poly1.subtract(poly2);

        polynomialsCongruent = poly1.specialMod(r, numberToTest);

        if(!polynomialsCongruent)
            prime = false;

    }

    return prime;
}

private boolean nonAKSisPrime(int x)
{
    int f = 2;
    boolean result = true;

    int s = (int)Math.sqrt(x);

    while(f <= s && result)
    {
        if(x % f == 0)
            result = false;
        f++;
    }

    return result;
}
private static int GCD(int u, int v)
{
    BigInteger bigU = new BigInteger (Integer.toString (u));
    BigInteger bigV = new BigInteger (Integer.toString (v));
    int gcd = bigU.gcd (bigV).intValue ();

    return gcd;
}

private static int largestPrimeFactor(int input)
{
    int f = 1;
    int r = 2;
    int x = input;

    while(x != 1 && r * r <= input)
    {
        while(x % r == 0)
        {
            x = x / r;
            f = r;
        }

        r++;
    }

    if(x == 1)
        return f;
    else
        return x;
}
}

Это мой класс PolynomialArray:

import java.math.BigInteger;


public class PolynomialArray
{
// instance variables
private BigInteger [] poly;
private int degree;
private int arraySize;
private static final int DEFAULT_SIZE = 1000000;


// constructor
public PolynomialArray()
{
    arraySize = DEFAULT_SIZE;
    poly = new BigInteger[arraySize];
    degree = 0;
}

// constructor that takes size as input
public PolynomialArray(int size)
{
    poly = new BigInteger[size];
    degree = 0;
    arraySize = size;
}

// constructor that takes data as input
public PolynomialArray(int[] data)
{
    poly = new BigInteger[DEFAULT_SIZE];


    for(int ctr = 1; ctr < data.length; ctr = ctr + 2)
    {
        if(data[ctr] > degree)
            degree = data[ctr];

        poly[data[ctr]] = new BigIntExtended(data[ctr - 1]);
    }
}

// constructor that takes size and data as inputs
public PolynomialArray(BigInteger[] data, int deg)
{
    poly = data;
    degree = deg;
}





// This method returns a String representation of the object.
public String toString()
{
    String outputString = "";

    if(degree != 0)
    {
        for(int i = 0; i <= degree; i++)
        {
            if(poly[i] != null && !poly[i].equals(BigInteger.ZERO))
            {
                outputString += "" + poly[i] + "*x^" + i + " + ";
            }
        }
    }
    else
        outputString += "0";
    return outputString;
}

// This method adds two PolynomialArrays
public void add(PolynomialArray p)
{
    if(p.getDegree() > degree)
    {
        degree = p.getDegree();
        BigInteger [] temp = new BigInteger [degree + 1];

        for(int d = 0; d <= degree; d++)
        {
            if(!this.getCoeffAtIndex(d).equals(BigIntExtended.ZERO))
            {
                if(temp[d] != null)
                    temp[d] = temp[d].add(this.getCoeffAtIndex(d));
                else
                    temp[d] = this.getCoeffAtIndex(d);
            }
        }

        for(int c = 0; c <= degree; c++)
        {
            if(!p.getCoeffAtIndex(c).equals(BigIntExtended.ZERO))
            {
                    temp[c] = p.getCoeffAtIndex(c);
            }
        }

        poly = temp;
    }

    for(int c = 0; c <= p.getDegree(); c++)
    {
        if(!p.getCoeffAtIndex(c).equals(BigIntExtended.ZERO))
        {
            this.addCoeffAtIndex(c, p.getCoeffAtIndex(c));
        }
    }



}

// This method subtracts p from this polynomial
public void subtract(PolynomialArray p)
{

    p.multiplyByConstant(-1);

    this.add(p);
}

// This method multiplies the coefficients of this polynomial
// by a constant c
public void multiplyByConstant(int c)
{
    for(int p = 0; p <= degree; p++)
    {
        if(poly[p] != null)
            poly[p] = poly[p].multiply(new BigIntExtended(c));
    }

}

// makes this Polynomial into a polynomial
// representing (x + a)^n, using an algorithm of
//  binomial expansion
public void binomialExpansion(int a, int n)
{
    poly = new BigInteger[n + 1];
    BigInteger temp = new BigIntExtended("0");
    BigInteger bigA = new BigIntExtended(a);


    for(int k = 0; k <= n; k++)
    {

        temp = factorial(n);
        temp = temp.divide(factorial(n-k).multiply(factorial(k)));

        bigA = new BigIntExtended(a);
        bigA = bigA.pow(k);

        poly[n - k] = temp.multiply( bigA);
    }

    degree = n;
}


// makes this Polynomial into a polynomial
// representing (x + a)^n, using an algorithm of
// successive squaring
public void binomialExpansionViaSquaring(int a, int n)
{
    poly = new BigInteger[n + 1];
    BigInteger[] tempPoly = new BigInteger[n + 1];
    tempPoly[0] = new BigIntExtended(a);
    tempPoly[1] = new BigIntExtended(1);
    int tempDegree = 1;

    BigInteger[] newPoly = new BigInteger[n + 1];
    newPoly[0] = new BigIntExtended(a);
    newPoly[1] = new BigIntExtended(1);
    int newDegree = 1;

    String binaryN = Integer.toBinaryString(n);

    char c;

    tempPoly = multiply(tempPoly, tempDegree, tempPoly, tempDegree);
    tempDegree *= 2;

    for(int index = 1; index < binaryN.length(); index++)
    {
        c = binaryN.charAt(index);
        if(c == '1')
        {
            tempPoly = multiply(tempPoly, tempDegree, newPoly, newDegree);
            tempDegree++;
        }

        if(index != binaryN.length() - 1)
        {
            tempPoly = multiply(tempPoly, tempDegree, tempPoly, tempDegree);
            tempDegree *= 2;
        }

    }

    poly = tempPoly;
    degree = tempDegree;
}



// This private helper method multiplies two polynomials
private BigInteger[] multiply(BigInteger[] bi1, int degree1, BigInteger[] bi2, int degree2)
{
    BigInteger [] polya = bi1;
    BigInteger [] polyb = bi2;
    int newDegree = degree1 + degree2;

    BigInteger [] polytemp = new BigInteger[newDegree + 1];

    for(int c = 0; c <= degree1; c++)
    {
        for(int d = 0; d <= degree2; d++)
        {
            if(polya[c] != null && polyb[d] != null)
            {
                BigInteger t = polya[c].multiply(polyb[d]);

                if(polytemp[c + d] != null)
                    polytemp[c + d] = polytemp[c + d].add(t);
                else
                {
                    polytemp[c + d] = new BigInteger("0");
                    polytemp[c + d] = polytemp[c + d].add(t);
                }
            }
        }
    }

    return polytemp;
}









// This method checks to see if this Polynomial
// is congruent to zero mod (x^r - 1, n)
public boolean specialMod(int r, int n)
{
    BigInteger total = new BigIntExtended("0");
    boolean mod = true;

    for(int start = 0; start < r; start++)
    {

        total = new BigIntExtended("0");

        for(int x = start; x < this.getDegree(); x = x + r)
        {
            BigInteger temp = poly[x];
            total = total.add(temp);
        }

        BigIntExtended bigN = new BigIntExtended(n);

        if(!total.mod(bigN).equals(BigIntExtended.ZERO))
            mod = false;
    }

    return mod;
}



// This method multiplies two polynomials together.
// Its runtime is O(n^2), because it has two nested
// loops that each run O(n) time.
public void multiply(PolynomialArray p)
{
    BigInteger [] poly2 = p.getPoly();
    int newDegree = this.getDegree() + p.getDegree();

    BigInteger [] polytemp = new BigInteger[newDegree + 1];

    for(int c = 0; c < poly.length; c++)
    {
        for(int d = 0; d < poly2.length; d++)
        {
            BigInteger t = poly[c].multiply(poly[d]);
            if(polytemp[c + d] != null)
                polytemp[c + d].add(t);
            else
            {
                polytemp[c + d] = new BigInteger("0");
                polytemp[c + d].add(t);
            }
        }
    }

    poly = polytemp;
    degree = newDegree;
}



// GETTERS AND SETTERS

// This method returns the array of coefficients
public BigInteger[] getPoly()
{
    return poly;
}

// This method returns the degree of the polynomial.
public int getDegree()
{
    return degree;
}

// This method returns the coefficient at the given
// power in the polynomial
public BigInteger getCoeffAtIndex(int index)
{
    if(poly[index] != null)
        return poly[index];
    else
        return BigInteger.ZERO;
}

// This method adds a to the coefficient at the given index
public void addCoeffAtIndex(int index, BigInteger a)
{
    if(poly[index] != null)
        poly[index] = poly[index].add(a);
    else
        poly[index] = a;
}

// This method computes the factorial of x, and
// returns it as a BigInteger, due to the tendency
// of factorial to exceed the capacity of ints
// extremely rapidly
public static BigInteger factorial(int x)
{
    if(x == 0)
        return new BigInteger("1");

    BigInteger result = new BigIntExtended("1");
    BigIntExtended c;

    for(int i = x; i >= 1; i--)
    {
        c = new BigIntExtended(i);
        result = result.multiply(c);
    }
    return result;
}
}

ЭтоМой класс BigIntExtended:

import java.math.BigInteger;

public class BigIntExtended extends BigInteger
{

// constructor that takes a primitive int,
// parses it to a String, and calls the
// superclass's constructor
public BigIntExtended(int n)
{
    super(new Integer(n).toString());
}

// constructor that takes a String
public BigIntExtended(String s)
{
    super(s);
}
}

Мой третий класс TextReader:

import java.io.*;
public class TextReader
{
  private PushbackReader in;   // the input stream
  private boolean rePrompting; // users should be prompted, but not files
  public TextReader(  )
  { 
    in = new PushbackReader( new InputStreamReader( System.in ) );
   rePrompting = true;
  }
  public TextReader( String fileName )
  { 
    try {
      in = new PushbackReader(new FileReader(fileName));
     rePrompting = false;
   }
    catch( Exception e ) {
      System.out.println("Can't open input file '" + fileName + "', program terminated");
      System.exit(1);
    }
  }
  private void error( String where )

  { 
    System.out.println("\n***Failure in " + where + " message. Program terminated***" );
    System.exit( 1 );
  }   
  public boolean readBoolean()
  {  
    do 
    {
      String torf = readWord( );
      if( torf.equalsIgnoreCase( "true" ) ) 
       return true;
      else if( torf.equalsIgnoreCase( "false" ) ) 
        return false;
      else  
       System.out.println( torf + " is not 'true' or 'false'. Try again"); 
    } while( true );
  }
  public String readLine( )
  {
    String result = "";
    try {
      do
      {
        int next = in.read( );
        if( next == '\r' ) 
          continue;
        if( next == -1 || next == '\n' )
          break;
        result += (char)next;
      } while(true); 
    } 
    catch( Exception e ) {
      error ( "readLine" );
    }
    return result;

  }
  public char readChar()
  {
    return read( );
  }
  public char read( )

  {
    char result = ' ';

    try {
      result = (char)in.read();
      if (result == '\r') 
       result = (char)in.read();
    }
    catch( Exception e ) {
      System.out.println( "Failure in call on read method, program terminated." );
      System.exit( 1 );
    }
  return result;
  }

  public void unread( char ch )
  { 
    try {
      in.unread((byte)ch);
    }
    catch( Exception e )
    {
      error( "unread" );
    }
  }

  public char peek( )
  {
    int next = 0;
    try {
      next = in.read( );
    }
    catch( Exception e ) {
      error( "peek" );
   }

    if( next != -1 )

      unread( (char)next );

    return (char)next;

  }

  public String readWord()   
  { 
    String result = "";
    try {
      int next;
      do
      {
        next = in.read();
      } while( next != -1 && Character.isWhitespace( (char)next) );

      while (next != -1 && !Character.isWhitespace( (char)next ) ) 
      {
        result += (char)next;

        next = in.read();

      }
     while (next != -1 && next != '\n' && Character.isWhitespace((char)next))
      {
        next = in.read();
      }  
  if (next != -1 && next != '\n')
        unread((char)next);
      } // end try
      catch (Exception e) 
      {

       error( "readWord" );

      } // end catch
    return result;
  }
  public int readInt()
  { 
    int result = 0;
    do // keep on trying until a valid double is entered
    {
      try 
      {
        result = Integer.parseInt(readWord());
        break;  // result is good, jump out of loop down to return result; 
      } 
      catch (Exception e) 
      {
        if(rePrompting)
          System.out.println("Invalid integer. Try again.");
        else
        {
          error( "readInt" );

          break;
        }  
      }
    } while( true );

    return result;
  }
  public double readDouble()

  {    double result = 0.0;
    do  // keep on trying until a valid double is entered
    {
      try {
        result = new Double(readWord()).doubleValue();
        break;  // result is good, jump out of loop down to return result;
      } 
      catch( Exception e )
      {
        if(rePrompting)
          System.out.println("Invalid floating-point number. Try again.");
        else
        {
          error("readDouble");
          break;
        }
      }
    } while( true );
    return result;
  }
  public boolean ready( )
  {
    boolean result = false;
    try {
      result = in.ready();
    }
    catch (IOException e) {
      error ( "ready" );
    }
    return result;
  }
  public static void main( String[] args )
  {
     System.out.print( "Enter password: " );
     String pass = "";
     TextReader k = new TextReader( );
     while( true )
     {
       char ch = k.peek();
       if(ch == '\n')
         break;
       pass += ""+ch;
//       k.unread( '*' );
     }
     System.out.println( pass );
  }
}

Answer 1

Боюсь, вы имеете в виду 16 байт целое число, а не бит .Java int - это 4 байта, 32 бита, long 8 байтов, 64 бита.

1425412525412545 может вписываться в long, конечно, не в int, и, возможно, вам следует использовать BigInteger в принципе, чтобы покрыть все 16 байтов.

Поскольку это больше не является примитивным типом, требуется немного больше записи.

Answer 2

Эта реализация теста простоты AKS ограничена использованием 32-битных типов данных, которые могут хранить числа до 2,147,483,647.Ваш номер намного больше этого, поэтому не читайте его правильно.

Звучит легко исправить, мы должны иметь возможность просто изменить все вхождения с int на long, начиная с longтипы данных могут хранить очень большие числа.К сожалению, это не сработает, потому что мы по-прежнему ограничены максимальным размером массивов в Java, который является 32-разрядным.Таким образом, совершенно непрактично обходиться без небезопасного доступа к памяти.

Если вы хотите проверить первичность чисел, которые могут быть большими, вы можете изменить код следующим образом:

Заменить main следующим:

public static void main(String[] args)
{
    AKSPrime p = new AKSPrime();

    TextReader k = new TextReader();

    System.out.print("Input number for primality testing: ");

    long i = k.readLong();

    System.out.println("Is " + i + " prime? " + p.nonAKSisPrime(i));
}

ЗаменитьnonAKSisPrime функция с этим:

private boolean nonAKSisPrime(long x)
{
    long f = 2;
    boolean result = true;

    long s = (long)Math.sqrt(x);

    while(f <= s && result)
    {
        if(x % f == 0)
            result = false;
        f++;
    }

    return result;
}

И добавить эту новую функцию к TextReader, которая читает long значения:

  public long readLong()
{ 
    long result = 0;
    do // keep on trying until a valid long is entered
    {
      try 
      {
        result = Long.parseLong(readWord());
        break;  // result is good, jump out of loop down to return result; 
      } 
      catch (Exception e) 
      {
        if(rePrompting)
          System.out.println("Invalid long. Try again.");
        else
        {
          error( "readLong" );

          break;
        }  
      }
    } while( true );

    return result;
  }