fork download
copy 
  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(0, 1);
  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.24s 60504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
P(0.0, 1.0)
Nhan delta: 9
xR: 81
xR: 13
2P(13.0, 1.0)
plus - delta: 0
xR: -13
yR: -1
3P(4.0, 16.0)
plus - delta: 8
xR: 60
yR: -73
4P(9.0, 12.0)
plus - delta: 5
xR: 16
yR: -81
5P(16.0, 4.0)
plus - delta: 14
xR: 180
yR: -141
6P(10.0, 12.0)
plus - delta: 13
xR: 159
yR: -79
7P(6.0, 6.0)
plus - delta: 15
xR: 219
yR: -226
8P(15.0, 12.0)
plus - delta: 3
xR: -6
yR: -34
9P(11.0, 0.0)
plus - delta: 3
xR: -2
yR: -46
10P(15.0, 5.0)
plus - delta: 15
xR: 210
yR: -91
11P(6.0, 11.0)
plus - delta: 13
xR: 163
yR: -131
12P(10.0, 5.0)
plus - delta: 14
xR: 186
yR: -225
13P(16.0, 13.0)
plus - delta: 5
xR: 9
yR: -46
14P(9.0, 5.0)
plus - delta: 8
xR: 55
yR: -33
15P(4.0, 1.0)
plus - delta: 0
xR: -4
yR: -1
16P(13.0, 16.0)
plus - delta: 9
xR: 68
yR: -1
17P(0.0, 16.0)
Khong ton tai modulo nghich dao
18P = 0
Bậc của #E17 = 18
https://ideone.com/gEl3kS
language:
Java (12.0.1)
created:
4 hours 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!