title: Points calculated using this elliptic curve point multiplication do not lie on the curve and this class brings Arithmetic exception
body: <p>I get stack on my error of point multiplication using standard projective coordinates.  I don't know  what i missed but the multiplied points do not lie on the curve and some times it outputs something like <strong>Arithmetic Exception: integer is not invertible.</strong></p>
  
  <pre><code>public class ECPointArthimetic {
  
      EllipticCurve ec;
      private BigInteger x;
      private BigInteger y;
      private BigInteger z;
      private BigInteger zinv;
      private BigInteger one = BigInteger.ONE;
      private BigInteger zero = BigInteger.ZERO;
      private boolean infinity;
  
      public ECPointArthimetic(EllipticCurve ec, BigInteger x, BigInteger y, BigInteger z) {
          this.ec = ec;
          this.x = x;
          this.y = y;
  
          // Projective coordinates: either zinv == null or z * zinv == 1
          // z and zinv are just BigIntegers, not fieldElements
          if (z == null) {
              this.z = BigInteger.ONE;
          } else {
              this.z = z;
          }
          this.zinv = null;
          infinity = false;
          //TODO: compression flag
      }
  
      public BigInteger getX() {
          if (this.zinv == null) {
              this.zinv = this.z.modInverse(this.ec.getP());
          }
          return this.x.multiply(this.zinv).mod(this.ec.getP());
      }
  
      public BigInteger getY() {
          if (this.zinv == null) {
              this.zinv = this.z.modInverse(this.ec.getP());
          }
          return this.y.multiply(this.zinv).mod(this.ec.getP());
      }
  
      public boolean pointEquals(ECPointArthimetic other) {
          if (other == this) {
              return true;
          }
          if (this.isInfinity()) {
              return other.isInfinity();
          }
          if (other.isInfinity()) {
              return this.isInfinity();
          }
          BigInteger u, v;
          // u = Y2 * Z1 - Y1 * Z2
          u = other.y.multiply(this.z).subtract(this.y.multiply(other.z)).mod(this.ec.getP());
          if (!u.equals(BigInteger.ZERO)) {
              return false;
          }
          // v = X2 * Z1 - X1 * Z2
          v = other.x.multiply(this.z).subtract(this.x.multiply(other.z)).mod(this.ec.getP());
          return v.equals(BigInteger.ZERO);
      }
  
      public boolean isInfinity() {
          if ((this.x == zero) &amp;&amp; (this.y == zero)) {
              return true;
          }
          return this.z.equals(BigInteger.ZERO) &amp;&amp; !this.y.equals(BigInteger.ZERO);
      }
  
      public ECPointArthimetic negate() {
          return new ECPointArthimetic(this.ec, this.x, this.y.negate(), this.z);
      }
  
      public ECPointArthimetic add(ECPointArthimetic b) {
          if (this.isInfinity()) {
              return b;
          }
          if (b.isInfinity()) {
              return this;
          }
          ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
          // u = Y2 * Z1 - Y1 * Z2
          BigInteger u = b.y.multiply(this.z).
                  subtract(this.y.multiply(b.z)).mod(this.ec.getP());
          // v = X2 * Z1 - X1 * Z2
          BigInteger v = b.x.multiply(this.z).
                  subtract(this.x.multiply(b.z)).mod(this.ec.getP());
  
          if (BigInteger.ZERO.equals(v)) {
              if (BigInteger.ZERO.equals(u)) {
                  return this.twice(); // this == b, so double
              }
  
              infinity = true; // this = -b, so infinity
              return R;
          }
  
          BigInteger THREE = new BigInteger("3");
          BigInteger x1 = this.x;
          BigInteger y1 = this.y;
          BigInteger x2 = b.x;
          BigInteger y2 = b.y;
  
          BigInteger v2 = v.pow(2);
          BigInteger v3 = v2.multiply(v);
          BigInteger x1v2 = x1.multiply(v2);
          BigInteger zu2 = u.pow(2).multiply(this.z);
  
          // x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
          BigInteger x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).
                  subtract(v3).multiply(v).mod(this.ec.getP());
          // y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
          BigInteger y3 = x1v2.multiply(THREE).multiply(u).
                  subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).
                  multiply(b.z).add(u.multiply(v3)).mod(this.ec.getP());
          // z3 = v^3 * z1 * z2
          BigInteger z3 = v3.multiply(this.z).multiply(b.z).mod(this.ec.getP());
  
          return new ECPointArthimetic(this.ec, x3, y3, z3);
      }
  
      public ECPointArthimetic twice() {
          if (this.isInfinity()) {
              return this;
          }
          ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
          if (this.y.signum() == 0) {
              infinity = true;
              return R;
          }
  
          BigInteger THREE = new BigInteger("3");
          BigInteger x1 = this.x;
          BigInteger y1 = this.y;
  
          BigInteger y1z1 = y1.multiply(this.z);
          BigInteger y1sqz1 = y1z1.multiply(y1).mod(this.ec.getP());
          BigInteger a = this.ec.getA();
          // w = 3 * x1^2 + a * z1^2
          BigInteger w = x1.pow(2).multiply(THREE);
          if (!BigInteger.ZERO.equals(a)) {
              w = w.add(this.z.pow(2).multiply(a));
          }
          w = w.mod(this.ec.getP());
          // x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
          BigInteger x3 = w.pow(2).subtract(x1.shiftLeft(3).multiply(y1sqz1)).
                  shiftLeft(1).multiply(y1z1).mod(this.ec.getP());
          // y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
          BigInteger y3 = (w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1))).
                  shiftLeft(2).multiply(y1sqz1).subtract(w.pow(2).multiply(w)).mod(this.ec.getP());
          // z3 = 8 * (y1 * z1)^3
          BigInteger z3 = y1z1.pow(2).multiply(y1z1).shiftLeft(3).mod(this.ec.getP());
  
          return new ECPointArthimetic(this.ec, x3, y3, z3);
      }
  
      public ECPointArthimetic multiply(BigInteger k) {
          if (this.isInfinity()) {
              return this;
          }
          ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
          if (k.signum() == 0) {
              infinity = true;
              return R;
          }
  
          BigInteger e = k;
          BigInteger h = e.multiply(new BigInteger("3"));
  
          ECPointArthimetic neg = this.negate();
          R = this;
  
          int i;
          for (i = h.bitLength() - 2; i &gt; 0; --i) {
              R = R.twice();
              boolean hBit = h.testBit(i);
              boolean eBit = e.testBit(i);
  
              if (hBit != eBit) {
                  R = R.add(hBit ? this : neg);
              }
          }
  
          return R;
      }
  
      public ECPointArthimetic implShamirsTrick( BigInteger k,
      ECPointArthimetic Q, BigInteger l){
          int m = Math.max(k.bitLength(), l.bitLength());
          ECPointArthimetic Z = this.add(Q);
          ECPointArthimetic R  = new ECPointArthimetic(ec,zero,zero,null);
  
          for (int i = m - 1; i &gt;= 0; --i){
              R = R.twice();
  
              if (k.testBit(i)){
                  if (l.testBit(i)){
                      R = R.add(Z);
                  }else{
                      R = R.add(this);
                  }
              }else{
                  if (l.testBit(i)){
                      R = R.add(Q);
                  }
              }
          }
          return R;
      }
  }
  </code></pre>
  
  <p>Here are the curves I used : </p>
  
  <pre><code>package NISTCurves;
  import ecc.*;
  import java.math.BigInteger;
  
  public class P192 implements ECDomainParameters {
  
      String p192X = "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012";
      String p192Y = "07192b95ffc8da78631011ed6b24cdd573f977a11e794811";
      String p192B = "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1";
      String p192P = "6277101735386680763835789423207666416083908700390324961279";
      String p192Order = "6277101735386680763835789423176059013767194773182842284081";
      String p192A = "-3";
      BigInteger p = new BigInteger(p192P, 16);
      EllipticCurve ec =
          new EllipticCurve(p,
          new BigInteger(p192A).mod(p),
          new BigInteger(p192B, 16));
      ECPointArthimetic G = new ECPointArthimetic(ec, new BigInteger(p192X,16), 
                 new BigInteger(p192Y,16),null);
      BigInteger order = new BigInteger(p192Order, 16);
  
      @Override
      public BigInteger getP() {
          return p;
      }
  
      @Override
      public EllipticCurve getECCurve() {
          return ec;
      }
  
      @Override
      public BigInteger getOrder() {
          return order;
      }
  
      @Override
      public ECPointArthimetic getGenerator() {
          return G;
      }
  }
  </code></pre>
  
  <p>Specification of Elliptic curve domain parameters</p>
  
  <pre><code>package NISTCurves;
  import ecc.ECPointArthimetic;
  import ecc.EllipticCurve;
  import java.math.BigInteger;
  
  public interface ECDomainParameters {
      public BigInteger getP();
      public ECPointArthimetic getGenerator();  
      public EllipticCurve getECCurve();
      public BigInteger getOrder();
  } 
  </code></pre>
  
  <p>Elliptic curve digital signature Algorithm implementation is here.
  In this code there is main function so use this to test Exception.</p>
  
  <pre><code>package ecc;
  import NISTCurves.ECDomainParameters;
  import NISTCurves.P192;
  import java.io.FileNotFoundException;
  import java.io.IOException;
  import java.math.BigInteger;
  import java.security.MessageDigest;
  import java.security.NoSuchAlgorithmException;
  
  /**
   *
   * @author Gere
   */
  public class ECDSA {
  
      private BigInteger r, s;
      ECDomainParameters param;
      private PrivateKey prvKey;
      private PublicKey pubKey;
      BigInteger zero = BigInteger.ZERO;
      private BigInteger one = BigInteger.ONE;
      private MessageDigest sha;
  
      public ECDSA() {
          try {
              sha = MessageDigest.getInstance("SHA-512");
          } catch (NoSuchAlgorithmException ex) {
              ex.printStackTrace();
          }
      }
  
      public void initSign(PrivateKey prvKey) {
          this.prvKey = prvKey;
          param = prvKey.getParam();
      }
  
      public void initVerify(PublicKey pubKey) {
          this.pubKey = pubKey;
          param = pubKey.getParam();
      }
  
      public void update(byte[] byteMsg) {
          sha.update(byteMsg);
      }
  
      public byte[] sign() throws FileNotFoundException, IOException {
  
          BigInteger c = new BigInteger(
                                     param.getP().bitLength() + 64,  Rand.sr);
          BigInteger k = c.mod(param.getOrder().subtract(one)).add(one);
          while (!(k.gcd(param.getOrder()).compareTo(one) == 0)) {
              c = new BigInteger(param.getP().bitLength() + 64, Rand.sr);
              k = c.mod(param.getOrder().subtract(one)).add(one);
          }
          BigInteger kinv = k.modInverse(param.getOrder());
          ECPointArthimetic p = param.getGenerator().multiply(k);
          if (p.getX().equals(zero)) {
              return sign();
          }
          BigInteger hash = new BigInteger(sha.digest());
          BigInteger r = p.getX().mod(param.getOrder());
  
          BigInteger s = (kinv.multiply((hash.add((prvKey.getPrivateKey()
                                    .multiply(r)))))).mod(param.getOrder());
          if (s.compareTo(zero) == 0) {
              return sign();
          }
  
          System.out.println("r at sign: " + r);
          System.out.println("s at sign: " + s);
  
          byte[] rArr = toUnsignedByteArray(r);
          byte[] sArr = toUnsignedByteArray(s);
          int nLength = (param.getOrder().bitLength() + 7) / 8;
          byte[] res = new byte[2 * nLength];
          System.arraycopy(rArr, 0, res, nLength - rArr.length, rArr.length);
  
          System.arraycopy(sArr, 0, res, 2 * nLength - sArr.length,
                        sArr.length);
          return res;
      }
  
      public boolean verify(byte[] res) {
  
          int nLength = (param.getOrder().bitLength() + 7) / 8;
  
          byte[] rArr = new byte[nLength];
          System.arraycopy(res, 0, rArr, 0, nLength);
          r = new BigInteger(rArr);
  
          byte[] sArr = new byte[nLength];
          System.arraycopy(res, nLength, sArr, 0, nLength);
          s = new BigInteger(sArr);
          System.out.println("r at verify: " + r);
          System.out.println("s at verify: " + s);
          BigInteger w, u1, u2, v;
          // r in the range [1,n-1]
          if (r.compareTo(one) &lt; 0 || r.compareTo(param.getOrder()) &gt;= 0) {
              return false;
          }
  
          // s in the range [1,n-1]
          if (s.compareTo(one) &lt; 0 || s.compareTo(param.getOrder()) &gt;= 0) {
              return false;
          }
          w = s.modInverse(param.getOrder());
  
          BigInteger hash = new BigInteger(sha.digest());
          u1 = hash.multiply(w);
          u2 = r.multiply(w);
  
          ECPointArthimetic G = param.getGenerator();
          ECPointArthimetic Q = pubKey.getPublicKey();
  
          // u1G + u2Q
  
          ECPointArthimetic temp = G.implShamirsTrick(u1, Q, u2);
          v = temp.getX();
          v = v.mod(param.getOrder());
  
          return v.equals(r);
      }
  
      byte[] toUnsignedByteArray(BigInteger bi) {
          byte[] ba = bi.toByteArray();
          if (ba[0] != 0) {
              return ba;
          } else {
              byte[] ba2 = new byte[ba.length - 1];
              System.arraycopy(ba, 1, ba2, 0, ba.length - 1);
              return ba2;
          }
      }
  
      public static void main(String[] args) {
          byte[] msg = "Hello".getBytes();
          byte[] sig = null;
          ECDomainParameters param = new P192();        
          PrivateKey prvObj = new PrivateKey(param);
          PublicKey pubObj = new PublicKey(prvObj);
          ECDSA ecdsa = new ECDSA();
          ecdsa.initSign(prvObj);
          ecdsa.update(msg);
          try {
              sig = ecdsa.sign();
          } catch (FileNotFoundException ex) {
              System.out.println(ex.getMessage());
  
          } catch (IOException ex) {
              System.out.println(ex.getMessage());
          }
          ecdsa.initVerify(pubObj);
          ecdsa.update(msg);
          if (ecdsa.verify(sig)) {
              System.out.println("valid");
          } else {
              System.out.println("invalid");
          }
      }
  }
  </code></pre>
  
  <p>Here PrivateKey class</p>
  
  <pre><code>package ecc;
  import NISTCurves.ECDomainParameters;
  import java.math.BigInteger;
  import java.security.SecureRandom;
  
  /**
   *
   * @author Gere
   */
  public class PrivateKey {
  
      private BigInteger d;
      private ECDomainParameters param;
      private BigInteger one = BigInteger.ONE;
      private BigInteger zero;
      private PublicKey pubKey;
  
      public PrivateKey(ECDomainParameters param) {
          this.param = param;
          BigInteger c = new BigInteger(param.getOrder().bitLength() + 64,
                  new SecureRandom());
          BigInteger n1 = param.getOrder().subtract(one);
          d = c.mod(n1).add(one);
          pubKey = new PublicKey(this);
      }
  
      public BigInteger getPrivateKey() {
          return d;
      }
  
      public ECDomainParameters getParam() {
          return param;
      }
  }
  </code></pre>
  
  <p>PublicKey class</p>
  
  <pre><code>package ecc;
  import NISTCurves.ECDomainParameters;
  
  /**
   *
   * @author Gere
   */
  public class PublicKey {
      private ECDomainParameters param;
      private ECPointArthimetic Q;
  
      public PublicKey(PrivateKey privObj) {
          param = privObj.getParam();
          Q  = param.getGenerator().multiply(privObj.getPrivateKey());
      }
  
      public ECDomainParameters getParam() {
          return param;
      }
  
      public ECPointArthimetic getPublicKey() {
          return Q;
      }
  }
  </code></pre>
  
  <p>Elliptic curve</p>
  
  <pre><code>package ecc;
  import java.math.BigInteger;
  
  /**
   *
   * @author Gere
   */
  public class EllipticCurve {
  
      private BigInteger a;
      private BigInteger b;
      private BigInteger p;
  
      public EllipticCurve(BigInteger a, BigInteger b, BigInteger p) {
          this.a = a;
          this.b = b;
          this.p = p;
      }
  
      public BigInteger getA() {
          return a;
      }
  
      public BigInteger getB() {
          return b;
      }
  
      public BigInteger getP() {
          return p;
      }       
  }
  </code></pre>
  
  <p>Rand class</p>
  
  <pre><code>package ecc;
  import java.security.SecureRandom;
  
  /**
   *
   * @author Gere
   */
  public class Rand {
      public static final SecureRandom sr = new SecureRandom();     
  }
  </code></pre>
  
  <p>Elliptic Curves interface    </p>
  
  <pre><code>package ecc;
  import java.math.BigInteger;
  
  public interface ECConstants{
      public static final BigInteger zero = BigInteger.valueOf(0);
      public static final BigInteger one = BigInteger.valueOf(1);
      public static final BigInteger two = BigInteger.valueOf(2);
      public static final BigInteger three = BigInteger.valueOf(3);
      public static final BigInteger four= BigInteger.valueOf(4);
  }
  </code></pre>