fork download 
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. // package ellipticCurve;
  7. import static java.lang.Math.cbrt;
  8. import static java.lang.Math.pow;
  9. import static java.lang.Math.sqrt;
  10. import java.util.ArrayList;
  11. import java.util.Locale;
  12.  
  13. /**
  14.  *
  15.  * @author Trần Hoàng
  16.  */
  17.  
  18. class Point {
  19.  
  20.     double x, y;
  21.  
  22.     public static void main(String[] args) {
  23. //      /**-----------------------**/
  24. //		ELLIPTIC (E) trên trường hữu hạn F(M):            y^2 mod M = x^3 + a*x + b mod M
  25. //		Khởi tạo các hệ số của (E), M
  26. 		long a, b, M;
  27. 		a = (long)1; 
  28. 		b = (long)1;
  29. 		M = (long)17;
  30. //		Chọn điểm cơ sở
  31.         Point p = new Point(16, 13);
  32. //		In điểm cơ sở ra
  33.         p.inString("P");
  34. //		Tìm bậc của (E)
  35.         caculateRankECC(p, a, b, M);
  36.         /**-----------------------**/    
  37.     }
  38.  
  39.     public Point() {
  40.     }
  41.  
  42.     // Contructor có đối số của thằng Point
  43.     public Point(double x, double y) {
  44.         this.x = x;
  45.         this.y = y;
  46.     }
  47.     // Tìm tạo độ điểm x từ điểm y
  48.     public Point calXfromY(double y, int a, int b) {
  49.         return new Point(cbrt(pow(y,2) - b), y);
  50.     }
  51.     // Tạo một điểm zeroPoint ~ 0
  52.     public Point zeroPoint() {
  53.         return new Point(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
  54.     }
  55.     // Kiểm tra một điểm có là zeroPoint hay không
  56.     public static boolean isZeroPoint(Point p) {
  57.         return p.x > 1e18 || p.x < -1e18;
  58.     }
  59.     // Tạo điểm đối xứng qua trục hoành
  60.     public Point negativePoint() {
  61.         return new Point(this.x, -this.y);
  62.     }
  63.  
  64.     public static long pow_modulo(long base, long exponent, long M) {
  65.         if(exponent == 0) return 1;
  66.         if(exponent == 1) return base;
  67.         long half = pow_modulo(base, exponent/2, M);
  68.         if((exponent&1) > 0) return (((half*half)%M)*base)%M;
  69.         else return (half*half)%M; 
  70.     }
  71.  
  72.     public static long modulo_invert_fermat(long n, long M) {
  73.         return pow_modulo(n, M-2, M);
  74.     }
  75.  
  76.     public static long modNegative(long y, long N) {
  77.         if(y < (long)0) {
  78.             y = N*Math.abs(y/N) + y;
  79.             return ((y+N)%N);
  80.         }
  81.         return (y%N);
  82.     }
  83.  
  84.     public static Point duplicatedPointModN(Point p, long a, long b, long N) {
  85.         if( isZeroPoint(p) ) {
  86.             return p;
  87.         }
  88.         // delta = (3*(xP^2) + a) / ( 2*(yP)
  89.         long delta_tu = (long)(3*p.x*p.x) + a;
  90.         long delta_mau =  2*(long)p.y;
  91.         // vì sau khi tính delta có thể âm nên ta cần mod cho N để hết âm
  92.         delta_tu = modNegative(delta_tu, N);
  93.         delta_mau = modNegative(delta_mau, N);
  94.         // delta = delta_tu/delta_mau => cần tính mod nghịch đảo
  95.         // Nếu delta_mau chia hết cho N thì không tồn tại modulo nghịch đảo.
  96.         if(delta_mau%N == 0) {
  97.             System.out.println("Khong ton tai modulo nghich dao");
  98.             return new Point().zeroPoint();
  99.         }
  100.         else {
  101.             delta_mau = modulo_invert_fermat(delta_mau, N);
  102.         }
  103.         long delta = (delta_tu*delta_mau)%N;
  104. //        System.out.println("Nhan delta: " + delta);
  105.         // R = 2*P; xR = delta^2 - 2*xP theo (IV)
  106.         long xR = ((delta*delta) - 2*(long)p.x);
  107. //        System.out.println("xR: " + xR);
  108.         xR = modNegative(xR, N);
  109. //        System.out.println("xR: " + xR);
  110.         // R = 2*P; yR = delta*(xP - xR) - yP theo(V)
  111.         long yR = (delta*((long)p.x - xR) - (long)p.y);
  112. //        System.out.println("yR: " + yR);
  113.         yR = modNegative(yR, N);
  114.         return new Point((double)xR, (double )yR);
  115.     }
  116.  
  117.     public static Point plusModN(Point p, Point q, long a, long b, long N) {
  118.         // check 2 điểm P, Q bằng nhau => dùng công thức nhân đôi
  119.         if( p.x == q.x && p.y == q.y ) 
  120.             return duplicatedPointModN(p,a, b, N);
  121.         // check zeroPoint P
  122.         if( isZeroPoint(q) )
  123.             return p;
  124.         // check zeroPoint Q
  125.         if( isZeroPoint(p) )
  126.             return q;
  127.         /*
  128.             Công thức cộng 2 điểm P(xP, yP) và Q(xQ, yQ) trên đường cong Elliptic
  129.             P # Q, P #O, Q # O
  130.             delta = delta_tu/ delta_mau = (yQ - yP) / (xQ - xP)
  131.         */
  132.         long delta_tu = modNegative(((long)q.y - (long)p.y), N);
  133.         long delta_mau = modNegative(((long)q.x - (long)p.x), N);
  134.  
  135.         // delta = delta_tu/delta_mau => cần tính mod nghịch đảo
  136.         // Nếu delta_mau chia hết cho N thì không tồn tại modulo nghịch đảo.
  137.         if(delta_mau%N == 0) {
  138.             System.out.println("Khong ton tai modulo nghich dao");
  139.             return new Point().zeroPoint();
  140.         }
  141.         else {
  142.             delta_mau = modulo_invert_fermat(delta_mau, N);
  143.         }
  144.         long delta = (delta_tu*delta_mau)%N;
  145. //        System.out.println("plus - delta: " + delta);
  146.         long xR = ((delta*delta) - ((long)p.x + (long)q.x));
  147. //        System.out.println("xR: " + xR);
  148.         xR = modNegative(xR, N);
  149.         long yR = (delta*((long)p.x - (long)xR) - (long)p.y);
  150. //        System.out.println("yR: " + yR);
  151.         yR = modNegative(yR, N);
  152.         return new Point((double)xR, (double)yR);
  153.     }
  154.  
  155.     public void inString(String msg) {
  156.         System.out.println( msg + "(" + x + ", " + y + ")");
  157.     }
  158.  
  159.     public static void caculateRankECC(Point p, long a, long b, long N) {
  160.         int cnt = 0;
  161.         // điểm temp là điểm trung gian, dùng để lưu 1 điểm vừa tính được
  162.         Point temp = new Point().zeroPoint();
  163.         // Lặp đến khi tìm thấy bậc của ECC
  164.         for( int i = 2;; i++) {
  165.             cnt++;
  166.             if(i == 2) {
  167.                 temp = duplicatedPointModN(p, a, b, N);
  168.             }
  169.             else {
  170.                 temp = plusModN(p, temp, a, b, N);
  171.             }
  172.             String msg = "";
  173.             if(isZeroPoint(temp)) {
  174.                 msg = i + "P = 0\nBậc của #E" + N + " = " + i;
  175.                 System.out.println(msg);
  176.                 // Kết thúc việc tìm bậc
  177.                 return;
  178.             }
  179.             else msg = i+ "P";
  180.             temp.inString(msg);
  181.         }
  182.     }
  183. }
  184.  
Success #stdin #stdout 0.19s 60364KB
comments (?)
stdin 
Standard input is empty
stdout 
P(16.0, 13.0)
2P(15.0, 12.0)
3P(4.0, 16.0)
4P(13.0, 16.0)
5P(6.0, 11.0)
6P(10.0, 12.0)
7P(0.0, 1.0)
8P(9.0, 5.0)
9P(11.0, 0.0)
10P(9.0, 12.0)
11P(0.0, 16.0)
12P(10.0, 5.0)
13P(6.0, 6.0)
14P(13.0, 1.0)
15P(4.0, 1.0)
16P(15.0, 5.0)
17P(16.0, 4.0)
Khong ton tai modulo nghich dao
18P = 0
Bậc của #E17 = 18
https://ideone.com/yChdyK
language:
Java (12.0.1)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!