content: // <XMP>
  // Decomposition of a number in a sum of up to four squares
  //
  // Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
  // Last updated December 20th, 2002.
  // See http://www.alpertron.com.ar/FSQUARES.HTM
  //
  // No part of this code can be used for commercial purposes without
  // the written consent from the author. Otherwise it can be used freely
  // except that you have to write somewhere in the code this header.
  // 
  import java.applet.*;
  import java.util.*;
  import java.awt.*;
  import java.math.*;
  
  public final class fsquares extends Applet implements Runnable {
  
    private static final int maxsieve = 65536;
    private TextField textNumber;
    private TextArea lowerTextArea;
    private static final BigInteger BigInt0 = BigInteger.valueOf(0L);
    private static final BigInteger BigInt1 = BigInteger.valueOf(1L);
    private static final BigInteger BigInt2 = BigInteger.valueOf(2L);
    private static final BigInteger BigInt3 = BigInteger.valueOf(3L);
    private boolean TerminateThread;
    private Thread calcThread;
    private String StringToLabel;
    private String textAreaContents;
    private int digitsInGroup = 6;
    private int [] sieve = new int [maxsieve/2];
    private int [] primediv = new int [maxsieve/4];
    private int [] primeexp = new int [maxsieve/4];
    private long [] TestNbr = new long [1200];
    private BigInteger mult1, mult2, mult3, mult4;
    private BigInteger Nbr = BigInt0;
    private String paneFooter;
  
    public static void main(String args[])
    {
      BigInteger nbr = new BigInteger(args[0]);
      System.out.println(pollardBrentRho(nbr,100000));
    }
  
    public void init() {
      Label labelTop, labelBottom;
      int i,j;
  
      // Determine primes (for primes sieve[i] >= 0)
  
      for (i=0; i<maxsieve/2; i++)
      {
        sieve[i] = 0;
      }
      for (i=3; i*i<maxsieve/2; i+=2)
      {
        j = i*i-3;
        j = (j%2 == 0)? j/2: (j+i)/2;
        for (; j<maxsieve/2; j+=i)
        {
          sieve[j] = -1;             // Indicate number is composite.
        }
      }
      setBackground(Color.lightGray);
      setLayout(null);
      labelTop = new Label("Type number or numerical expression here and press Return");
      labelTop.reshape(10, 10, 570, 14);
      labelTop.setFont(new Font("Courier", Font.PLAIN, 12));
      labelTop.setAlignment(Label.CENTER);
      add(labelTop);
      textNumber = new TextField(1000);
      textNumber.reshape(10, 30, 570, 30);
      textNumber.setEditable(true);
      add(textNumber);
      lowerTextArea = new TextArea("", 6,75, TextArea.SCROLLBARS_VERTICAL_ONLY);
      lowerTextArea.reshape(10, 70, 570, 200);
      lowerTextArea.setEditable(false); 
      lowerTextArea.setFont(new Font("Courier", Font.PLAIN, 12));
      add(lowerTextArea);
      labelBottom = new Label("Written by Dario Alejandro Alpern. Last updated December 20th, 2002");
      labelBottom.reshape(10, 280, 570, 14);
      labelBottom.setFont(new Font("Courier", Font.PLAIN, 12));
      labelBottom.setAlignment(Label.CENTER);
      add(labelBottom);
      textNumber.requestFocus();
      validate();
      }
  
    public void destroy() {           /* Applet end */
      TerminateThread = true;
    }
  
  public boolean handleEvent(Event e) {
    if (e.id == Event.KEY_PRESS && e.key == Event.ENTER) {
      if (calcThread != null) {
        TerminateThread = true;
        try {
          calcThread.join();        /* Wait until the solving thread dies */
          } catch (InterruptedException ie) {};
        }
      calcThread = new Thread(this);  /* Start solving thread */
      calcThread.start();
      return true;
      }
    return false;
    }
  
    public void run() {
      BigInteger nbr, modulus, Mult1, Mult2, Mult3, Mult4, p, q, K, M1, M2, Tmp;
      BigInteger [] ExpressionResult = new BigInteger[1];
      int power4, r, s, shRight, ExpressionRC;
      int modularexp;
      boolean Computing3Squares;
      long StartTime, remainder;
      BigInteger Divisor;
      int i, j, sum;
      int nbrDivisors = 0;
      int nbrModExp = 0;
      int iMult3, iMult4;
      int NumberLength;
      byte Result[];
      long L, P, Q;
      long [] TestNbr = this.TestNbr;
  
      StartTime = System.currentTimeMillis();
      TerminateThread = false;
  
      lowerTextArea.setText("Computing input expression...");
      try {
        ExpressionRC = expression.ComputeExpression(textNumber.getText().trim(),0,ExpressionResult);
      } catch (OutOfMemoryError e) {
        lowerTextArea.setText("Out of memory.");
        return;
      } catch (ArithmeticException e) {
        return;
      }
      modulus = nbr = ExpressionResult[0];
      if (ExpressionRC != 0) {
        switch (ExpressionRC) {
          case -1:
            lowerTextArea.setText("Number too low (less than 2).");
            break;
          case -2:
            lowerTextArea.setText("Number too high (more than 1000 digits).");
            break;
          case -3:
            lowerTextArea.setText("Intermediate expression too high (more than 2000 digits).");
            break;
          case -4:
            lowerTextArea.setText("Non-integer division.");
            break;
          case -5:
            lowerTextArea.setText("Parentheses mismatch.");
            break;
          case -6:
            lowerTextArea.setText("Syntax error.");
            break;
          case -7:
            lowerTextArea.setText("Too many parentheses.");
            break;
          case -8:
            lowerTextArea.setText("Invalid parameter.");
            break;
          }
        return;
        }
      // If modulus is a perfect square, show the square root.
      Mult1 = squareRoot(modulus);
      if (Mult1.multiply(Mult1).equals(modulus))
      {
        Mult2 = BigInt0;
        iMult3 = iMult4 = 0;
        power4 = 0;
      }
      else
      {
        power4 = modulus.getLowestSetBit() / 2;
        modulus = modulus.shiftRight(2*power4);    // modulus is not multiple of 4.
        if (modulus.compareTo(BigInt3) <= 0)
        {
          Mult1 = Mult2 = BigInt0;
          iMult3 = iMult4 = 0;
          switch (modulus.intValue())
          {
            case 3:
              iMult3 = 1;
            case 2:
              Mult2 = BigInt1;
            case 1:
              Mult1 = BigInt1;
          }
        }
        else
        {
  
          // Store in TestNbr the value of modulus.
          Result = modulus.toByteArray();
          NumberLength = (Result.length+3)/4;
          j = 0;
          L = 1;
          P = 0;
          for (i=Result.length-1; i>=0; i--)
          {
            P += L*(long)(Result[i]>=0?Result[i]:Result[i]+256);
            L *= 0x100;
            if (L == 0x100000000L)
            {
              TestNbr[j] = P;
              j++;
              L = 1;
              P = 0;
            }
          }
          TestNbr[j] = P;
        
          r = (int)TestNbr[0] & 7;                    // modulus mod 8
      
           // Fill sieve array with r%n
  
          for (i=0; i<maxsieve/2; i++)
          {
            if (sieve[i] >= 0)                        // If prime...
            {
              Q = 2*i+3;                              // Prime
              long Divid, Rem = 0;
  
              for (j=NumberLength-1; j>=0; j--)
              {
                Divid = TestNbr[j] + (Rem << 32);
                Rem = Divid % Q;
              }
              sieve[i] = (int)Rem;
            }
          }
  
          if (r != 7)   // n!=7 (mod 8) => Sum of three squares
          {
            lowerTextArea.setText("Computing sum of three squares...");
            Computing3Squares = true;
            iMult4 = 0;
            iMult3 = -1;
          }
          else
          {
            iMult3 = -1;
            iMult4 = 0;
            lowerTextArea.setText("Computing sum of four squares...");
            Computing3Squares = false;
          }
  compute_squares_loop:
          while (true)
          {
            if (TerminateThread)
            {
              return;                           
            }
            if (Computing3Squares == false && iMult3 >= iMult4)
            {
              iMult3 = 1;
              iMult4++;
            }
            else
            {
              iMult3++;
            }
            sum = iMult3 * iMult3 + iMult4 * iMult4;
            p = modulus.subtract(BigInteger.valueOf(sum));
            shRight = p.getLowestSetBit();
            p = p.shiftRight(shRight);
            if (p.testBit(0) == false || p.testBit(1) == true)
            {
              continue;         /* p is not congruent to 1 mod 4 */
            }
            
            // Now compute modulus over the product of all odd divisors
            // less than maxsieve.
  
            nbrDivisors = 0;
            for (i = 0; i<maxsieve/2; i++)
            {
              if (sieve[i] >= 0 && (sieve[i] - sum) % (i*2+3) == 0)
              {                          // Divisor found.
                primediv[nbrDivisors] = i*2+3;   // Store divisor.
                primeexp[nbrDivisors] = 0;       // Store exponent.
                Divisor = BigInteger.valueOf(i*2+3);
                while (p.remainder(Divisor).signum() == 0)
                {
                  p = p.divide(Divisor);
                  primeexp[nbrDivisors]++;       // Increment exponent.
                }
                if ((i*2+3)%4 == 3 && primeexp[nbrDivisors]%2 != 0)
                {                   // Divisor of the form 4k+3 not square.
                  continue compute_squares_loop;  // Discard this value.
                }
                nbrDivisors++;
              }
            }
  
            if (p.equals(BigInt1))
            {
              Mult1 = BigInt1;
              Mult2 = BigInt0;
            }
            else
            {
              // At this moment p must be prime, otherwise we must discard it.
  
              q = p.subtract(BigInt1);              // q = p - 1.
              K = BigInt1;
              j = q.getLowestSetBit();
              Mult3 = q.shiftRight(j);
              Mult4 = BigInt0;
              do
              {                 // Compute Mult1 = sqrt(-1) (mod p).
                K = K.add(BigInt1);
                Mult1 = K.modPow(Mult3,p);
                nbrModExp++;
                for (i=0; i<j; i++)
                {
                  Mult4 = Mult1.multiply(Mult1).mod(p);
                  if (Mult4.equals(q))
                  {
                    break;      // Mult1^2 = -1 (mod p), so exit loop.
                  }
                  Mult1 = Mult4;
                }
              } while (Mult4.equals(BigInt1));  // Loop if number is at least PRP.
              if (Mult4.equals(q) == false)
              {            // Cannot find sqrt(-1) (mod p), go to next candidate.
                continue; 
              }
              Mult2 = BigInt1;
              while (true)
              {
                K = Mult1.multiply(Mult1).add(Mult2.multiply(Mult2)).divide(p);
                if (K.equals(BigInt1))
                {                                   // Calculation finished
                  break;
                }
                if (p.mod(K).signum() == 0)
                {                                   // The number is not prime
                  continue; 
                }
                M1 = Mult1.mod(K);
                M2 = Mult2.mod(K);
                if (M1.compareTo(K.shiftRight(1)) > 0) {M1 = M1.subtract(K);}
                if (M2.compareTo(K.shiftRight(1)) > 0) {M2 = M2.subtract(K);}
                Tmp = Mult1.multiply(M1).add(Mult2.multiply(M2)).divide(K);
                Mult2 = Mult1.multiply(M2).subtract(Mult2.multiply(M1)).divide(K);
                Mult1 = Tmp;
              }      /* end while */
            }
      
            // Use the other divisors of modulus in order to get Mult1 and Mult2.
  
            for (i=0; i<nbrDivisors; i++)
            {
              if (primeexp[i] >= 2)
              {
                Tmp = BigInteger.valueOf(primediv[i]).pow(primeexp[i]/2);
                Mult1 = Mult1.multiply(Tmp);
                Mult2 = Mult2.multiply(Tmp);
              }
              if (primeexp[i]%2 == 1)
              {
                // Since the value primediv[i] is very low it is faster to use
                // trial and error than the general method in order to find
                // the sum of two squares.
  
                s = primediv[i];
                j = 1;
                while (true)
                {
                  r = (int)Math.sqrt(s-j*j);
                  if (r*r+j*j == s)
                  {
                    break;
                  }
                  j++;
                }
  
                M1 = BigInteger.valueOf(j);
                M2 = BigInteger.valueOf(r);
                Tmp = Mult1.multiply(M1).add(Mult2.multiply(M2));
                Mult2 = Mult1.multiply(M2).subtract(Mult2.multiply(M1));
                Mult1 = Tmp;
              }
            }            /* end for */
            break;
          }              /* end while */
  
          Mult1 = Mult1.shiftLeft(shRight/2);
          Mult2 = Mult2.shiftLeft(shRight/2);
          if (shRight%2 == 1)
          {
            Tmp = Mult1.add(Mult2);
            Mult2 = Mult1.subtract(Mult2).abs();
            Mult1 = Tmp;
          }
        }
      }
      Mult1 = Mult1.shiftLeft(power4).abs();
      Mult2 = Mult2.shiftLeft(power4).abs();
      Mult3 = BigInteger.valueOf(iMult3).shiftLeft(power4);
      Mult4 = BigInteger.valueOf(iMult4).shiftLeft(power4);
      // Sort squares
      if (Mult1.compareTo(Mult2)<0) {Tmp=Mult1; Mult1=Mult2; Mult2=Tmp;}
      if (Mult1.compareTo(Mult3)<0) {Tmp=Mult1; Mult1=Mult3; Mult3=Tmp;}
      if (Mult2.compareTo(Mult3)<0) {Tmp=Mult2; Mult2=Mult3; Mult3=Tmp;}
      if (Mult1.compareTo(Mult4)<0) {Tmp=Mult1; Mult1=Mult4; Mult4=Tmp;}
      if (Mult2.compareTo(Mult4)<0) {Tmp=Mult2; Mult2=Mult4; Mult4=Tmp;}
      if (Mult3.compareTo(Mult4)<0) {Tmp=Mult3; Mult3=Mult4; Mult4=Tmp;}
  
      // Validate
  
      if (Mult1.multiply(Mult1).add(Mult2.multiply(Mult2)).
          add(Mult3.multiply(Mult3)).add(Mult4.multiply(Mult4)).equals(nbr)
          == false)
      {
        lowerTextArea.setText("Internal error!\n\nPlease send the number to the author of the applet");
        Nbr = BigInt0;
        return;
      }
  
      mult1 = Mult1;
      mult2 = Mult2;
      mult3 = Mult3;
      mult4 = Mult4;
      Nbr = nbr;
      long t=(System.currentTimeMillis()-StartTime)/1000;
      String timeElapsed = "Time elapsed: "+t/86400+"d "+(t%86400)/3600+"h "+((t%3600)/60)+"m "+(t%60)+"s";
      paneFooter = "\n\n"+timeElapsed+
                   "\n\nNumber of modular exponentiations: "+nbrModExp;
      ShowPane();
    }
  
    private void ShowPane()
    {
      textAreaContents = "";
      StringToLabel = "n = ";
      insertBigNbr(Nbr);
      textAreaContents += StringToLabel + "\n\n";
  
      if (mult4.signum() == 0)
      {
        if (mult3.signum() == 0)
        {
          if (mult2.signum() == 0)
          {
            textAreaContents += "n = a^2\n";
            StringToLabel = "a = ";            // Start new line.
            insertBigNbr(mult1);
          }
          else
          {
            textAreaContents += "n = a^2 + b^2\n";
            StringToLabel = "a = ";            // Start new line.
            insertBigNbr(mult1);
            textAreaContents += StringToLabel + "\n";
            StringToLabel = "b = ";            // Start new line.
            insertBigNbr(mult2);
          }
        }
        else
        {
          textAreaContents += "n = a^2 + b^2 + c^2\n";
          StringToLabel = "a = ";            // Start new line.
          insertBigNbr(mult1);
          textAreaContents += StringToLabel + "\n";
          StringToLabel = "b = ";            // Start new line.
          insertBigNbr(mult2);
          textAreaContents += StringToLabel + "\n";
          StringToLabel = "c = ";            // Start new line.
          insertBigNbr(mult3);
        }
      }
      else
      {
        textAreaContents += "n = a^2 + b^2 + c^2 + d^2\n";
        StringToLabel = "a = ";            // Start new line.
        insertBigNbr(mult1);
        textAreaContents += StringToLabel + "\n";
        StringToLabel = "b = ";            // Start new line.
        insertBigNbr(mult2);
        textAreaContents += StringToLabel + "\n";
        StringToLabel = "c = ";            // Start new line.
        insertBigNbr(mult3);
        textAreaContents += StringToLabel + "\n";
        StringToLabel = "d = ";            // Start new line.
        insertBigNbr(mult4);
      }
      lowerTextArea.setText(textAreaContents + StringToLabel + paneFooter);
    }
  
    private void addStringToLabel(String value) {
      if (value.length() + 1 + StringToLabel.length() >= 79) {
        textAreaContents += StringToLabel + "\n";
        StringToLabel = value+" ";
      }
      else {
        StringToLabel += value+" ";
      }
    }
  
    private void insertBigNbr(BigInteger N)
    {
      int i,dig;
      dig = digitsInGroup & 0x3FF;
      String value = N.toString();
      i = (value.length() + dig - 1)%dig + 1;
      addStringToLabel(value.substring(0,i));
      while (i<value.length())
      {
        addStringToLabel(value.substring(i,i+dig));
        i += dig;
      }
    }
  
    // Compute square root using Newton's algorithm. 
    private BigInteger squareRoot(BigInteger value)
    {
      BigInteger sqrt = BigInt0;
      BigInteger newsqrt = BigInt1.shiftLeft((value.bitLength()+1)/2);
      do
      {
        sqrt = newsqrt;
        newsqrt = sqrt.add(value.divide(sqrt)).shiftRight(1);
      } while (sqrt.compareTo(newsqrt) > 0);
      return sqrt;
    }
  
    private static BigInteger pollardBrentRho(BigInteger value, int nbrLoops)
    {
      int r = 1;
      int i, k;
      int m = 20;
      BigInteger x;
      BigInteger ys = BigInt0;
      BigInteger G = value;
      BigInteger y = BigInt1;
      BigInteger q = BigInt1;
      BigInteger BigInt3 = BigInteger.valueOf(3L);
      do
      {
        x = y;
        for (i=1; i<=r; i++)
        {
          y = y.multiply(y).add(BigInt3).mod(value);
        }
        k = 0;
        do
        {
          ys = y;
          i = (m<r-k? m:r-k);
          for (; i>=1; i--)
          {
            y = y.multiply(y).add(BigInt3).mod(value);
            q = q.multiply(x.subtract(y)).mod(value);
          }
          G = q.gcd(value);
          k += m;
          if (k > nbrLoops)
          {
            return value;      /* Factor not found */
          }
        } while (k<r && G.compareTo(BigInt1)<=0);
        r *= 2;
      } while (G.compareTo(BigInt1)<=0);
      if (G.equals(value))
      {
        do
        {
          ys = ys.multiply(ys).add(BigInt3).mod(value);
          G = x.subtract(ys).abs().gcd(value);
        } while (G.compareTo(BigInt1)<=0);
      }
      return G;
    }
  
    public String getTextFromPane()
    {
      if ((calcThread == null || calcThread.isAlive() == false) &&
           lowerTextArea.getText() != "")
      {
        String text="<HTML><TITLE>Sum of squares</TITLE><BODY><H2>Sum of squares</H2><P><I>Written by Dario Alejandro Alpern (alpertron@hotmail.com)</I><P><PRE>"
                 + lowerTextArea.getText() + "</PRE><BODY></HTML>";
        return text;
      }
      return "";
    }
  
    public void setDigits(int digits)
    {
      digitsInGroup = digits;
      if ((calcThread == null || calcThread.isAlive() == false) &&
           lowerTextArea.getText() != "")
      {
        ShowPane();
      }
    }
  }       // End applet class
  
  // </XMP>
  