-
Notifications
You must be signed in to change notification settings - Fork 0
/
add.c
124 lines (112 loc) · 2.03 KB
/
add.c
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#define DEBUG 0
typedef struct point_s {
int x;
int y;
} point;
void input_point(point * p)
{
scanf("%d,%d", &(p->x), &(p->y));
}
int check_P(point P[], point * R)
{
int i;
for (i = 0; i < 10; i++) {
if (P[i].x == R->x && P[i].y == R->y) {
return i;
}
}
return -1;
}
int mod(int num, int p)
{
if (num % p == 0) {
num = 0;
} else if (num < 0) {
num = p - ((-num) % p);
} else {
num %= p;
}
return num;
}
void extgcd(int a, int b, int *x, int *y, int *d)
{
int u, v, q, tmp;
*x = 1;
*y = 0;
u = 0;
v = 1;
while (b > 0) {
q = a / b;
tmp = u;
u = *x - q * u;
*x = tmp;
tmp = v;
v = *y - q * v;
*y = tmp;
tmp = b;
b = a - q * b;
a = tmp;
}
*d = a;
}
void add(point * P, point * Q, point * R, int a, int p)
{
int x, y, d;
if (P->x == -1 && P->y == -1) {
R->x = Q->x;
R->y = Q->y;
} else if (Q->x == -1 && Q->y == -1) {
R->x = P->x;
R->y = P->y;
} else {
if (P->x == Q->x && P->y == mod(-Q->y, p)) {
R->x = -1;
R->y = -1;
} else {
int lambda;
int numerator, denominator;
if (P->x != Q->x) {
numerator = P->y - Q->y;
denominator = P->x - Q->x;
} else {
numerator = 3 * P->x * P->x + a;
denominator = 2 * P->y;
}
numerator = mod(numerator, p);
denominator = mod(denominator, p);
extgcd(p, denominator, &x, &y, &d);
lambda = mod(numerator * y, p);
R->x = mod(lambda * lambda - P->x - Q->x, p);
R->y = mod(lambda * (P->x - R->x) - P->y, p);
#if DEBUG
printf
("\tnumerator is %d\n\tdenominator is %d\n\tlamda is %d\n\tR=(%d,%d)\n",
numerator, denominator, lambda, R->x, R->y);
#endif
}
}
}
int main()
{
int a, b, p;
point P[10] = { {-1, -1}, {0, 2}, {1, 1}, {2, 2}, {5, 2},
{6, 0}, {5, 5}, {2, 5}, {1, 6}, {0, 5}
};
point R;
printf("a:");
scanf("%d", &a);
printf("b:");
scanf("%d", &b);
printf("p:");
scanf("%d", &p);
int i, j;
for (i = 0; i < 10; i++) {
for (j = 0; j < 10; j++) {
add(&P[i], &P[j], &R, a, p);
printf("P%d+P%d=P%d\n", i, j, check_P(P, &R));
}
printf("\n\n");
}
return 0;
}