-
Notifications
You must be signed in to change notification settings - Fork 0
/
ECC.java
66 lines (66 loc) · 2.09 KB
/
ECC.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Scanner;
public class ECC{
public static int modPow(int base, int exponent, int modulus) {
if (modulus == 1) return 0;
int result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}
public static int findDiscreteLogarithm(int p, int a, int b, int xQ, int yQ, int xP, int yP) {
int i = 1;
int num = 0;
int den = 0;
int xr = xP;
int yr = yP;
while (true) {
if (i == 1) {
num = (3 * xP * xP + a);
den = 2 * yP;
} else {
num = yr - yP;
den = xr - xP;
}
if (den < 0) {
num = -num;
den = -den;
}
den = modPow(den, p - 2, p);
int l = (num * den) % p;
xr = (l * l - xP - xr + p) % p;
yr = (l * (xP - xr) - yP + p) % p;
System.out.println(i + "P = (" + xr + ", " + yr + ")");
i++;
if (xr == xQ && yr == yQ) {
break;
}
}
return i;
}
public static void main(String[] args) {
Scanner sn = new Scanner(System.in);
System.out.print("Enter p: ");
int p = sn.nextInt();
System.out.print("Enter a: ");
int a = sn.nextInt();
System.out.print("Enter b: ");
int b = sn.nextInt();
System.out.print("Enter x coordinate of Q: ");
int xQ = sn.nextInt();
System.out.print("Enter y coordinate of Q: ");
int yQ = sn.nextInt();
System.out.print("Enter x coordinate of P: ");
int xP = sn.nextInt();
System.out.print("Enter y coordinate of P: ");
int yP = sn.nextInt();
sn.close();
int steps = findDiscreteLogarithm(p, a, b, xQ, yQ, xP, yP);
System.out.println("Number of steps taken: " + steps);
}
}