---

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Параметры кривой secp256k1: y^2 = x^3 + 7 mod p
const char* p_hex = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F";
const char* a_hex = "0000000000000000000000000000000000000000000000000000000000000000";
const char* b_hex = "0000000000000000000000000000000000000000000000000000000000000007";

// Базовая точка G (генератор)
const char* Gx_hex = "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798";
const char* Gy_hex = "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8";

// Точка P (пример: P = G)
const char* Px_hex = "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798";
const char* Py_hex = "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8";

// Преобразование hex символа в число
int hex_char_to_int(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
    if (c >= 'A' && c <= 'F') return c - 'A' + 10;
    return 0;
}

char int_to_hex_char(int n) {
    if (n < 10) return '0' + n;
    return 'A' + (n - 10);
}

// Удаление ведущих нулей
void trim_leading_zeros(char* str) {
    int len = strlen(str);
    int start = 0;
    while (start < len - 1 && str[start] == '0') start++;
    if (start > 0) {
        for (int i = start; i <= len; i++) {
            str[i - start] = str[i];
        }
    }
}

// Сравнение двух hex строк
int compare_hex(const char* a, const char* b) {
    char a_trim[256], b_trim[256];
    strcpy(a_trim, a);
    strcpy(b_trim, b);
    trim_leading_zeros(a_trim);
    trim_leading_zeros(b_trim);
    
    int len_a = strlen(a_trim);
    int len_b = strlen(b_trim);
    
    if (len_a != len_b) return len_a - len_b;
    
    for (int i = 0; i < len_a; i++) {
        if (a_trim[i] != b_trim[i]) {
            return hex_char_to_int(a_trim[i]) - hex_char_to_int(b_trim[i]);
        }
    }
    return 0;
}

// Сложение двух hex строк
void add_hex(const char* a, const char* b, char* result) {
    char a_rev[256], b_rev[256];
    int res[256] = {0};
    int len_a = strlen(a);
    int len_b = strlen(b);
    
    for (int i = 0; i < len_a; i++) a_rev[i] = a[len_a - 1 - i];
    for (int i = 0; i < len_b; i++) b_rev[i] = b[len_b - 1 - i];
    
    int carry = 0;
    int max_len = len_a > len_b ? len_a : len_b;
    
    for (int i = 0; i < max_len; i++) {
        int da = (i < len_a) ? hex_char_to_int(a_rev[i]) : 0;
        int db = (i < len_b) ? hex_char_to_int(b_rev[i]) : 0;
        int sum = da + db + carry;
        res[i] = sum % 16;
        carry = sum / 16;
    }
    if (carry) res[max_len++] = carry;
    
    for (int i = 0; i < max_len; i++) {
        result[i] = int_to_hex_char(res[max_len - 1 - i]);
    }
    result[max_len] = '\0';
    trim_leading_zeros(result);
}

// Вычитание (a >= b)
void sub_hex(const char* a, const char* b, char* result) {
    char a_rev[256], b_rev[256];
    int res[256] = {0};
    int len_a = strlen(a);
    int len_b = strlen(b);
    
    for (int i = 0; i < len_a; i++) a_rev[i] = a[len_a - 1 - i];
    for (int i = 0; i < len_b; i++) b_rev[i] = b[len_b - 1 - i];
    
    int borrow = 0;
    for (int i = 0; i < len_a; i++) {
        int da = hex_char_to_int(a_rev[i]);
        int db = (i < len_b) ? hex_char_to_int(b_rev[i]) : 0;
        int diff = da - db - borrow;
        if (diff < 0) {
            diff += 16;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res[i] = diff;
    }
    
    int len = len_a;
    while (len > 1 && res[len - 1] == 0) len--;
    
    for (int i = 0; i < len; i++) {
        result[i] = int_to_hex_char(res[len - 1 - i]);
    }
    result[len] = '\0';
}

// Умножение двух hex чисел
void mul_hex(const char* a, const char* b, char* result) {
    int len_a = strlen(a);
    int len_b = strlen(b);
    int res[512] = {0};
    
    for (int i = len_a - 1; i >= 0; i--) {
        int da = hex_char_to_int(a[i]);
        for (int j = len_b - 1; j >= 0; j--) {
            int db = hex_char_to_int(b[j]);
            int pos = (len_a - 1 - i) + (len_b - 1 - j);
            res[pos] += da * db;
        }
    }
    
    for (int i = 0; i < 511; i++) {
        res[i + 1] += res[i] / 16;
        res[i] %= 16;
    }
    
    int len = 511;
    while (len > 0 && res[len] == 0) len--;
    
    for (int i = 0; i <= len; i++) {
        result[i] = int_to_hex_char(res[len - i]);
    }
    result[len + 1] = '\0';
    trim_leading_zeros(result);
    if (strlen(result) == 0) strcpy(result, "0");
}

// Деление (упрощённое для модуля)
void divmod_hex(const char* a, const char* b, char* quotient, char* remainder) {
    char temp[512];
    strcpy(temp, a);
    trim_leading_zeros(temp);
    
    char current[512] = "";
    int q_pos = 0;
    char q_digits[512] = "";
    
    for (int i = 0; i < strlen(temp); i++) {
        int len = strlen(current);
        current[len] = temp[i];
        current[len + 1] = '\0';
        trim_leading_zeros(current);
        
        int digit = 0;
        while (compare_hex(current, b) >= 0) {
            char temp_sub[512];
            sub_hex(current, b, temp_sub);
            strcpy(current, temp_sub);
            digit++;
        }
        if (digit > 0 || q_pos > 0 || i == strlen(temp) - 1) {
            q_digits[q_pos++] = int_to_hex_char(digit);
        }
    }
    if (q_pos == 0) {
        q_digits[0] = '0';
        q_digits[1] = '\0';
    } else {
        q_digits[q_pos] = '\0';
    }
    strcpy(quotient, q_digits);
    strcpy(remainder, current);
    if (strlen(remainder) == 0) strcpy(remainder, "0");
}

// Модуль числа
void mod_hex(const char* a, const char* m, char* result) {
    char q[512], r[512];
    divmod_hex(a, m, q, r);
    strcpy(result, r);
}

// Расширенный алгоритм Евклида для обратного элемента
void inverse_hex(const char* a, const char* m, char* result) {
    char t[512] = "0";
    char newt[512] = "1";
    char r[512];
    char newr[512];
    strcpy(r, m);
    strcpy(newr, a);
    
    char quotient[512], temp[512], mul_temp[512], sub_temp[512];
    
    while (compare_hex(newr, "0") != 0) {
        char q[512];
        char rem[512];
        divmod_hex(r, newr, q, rem);
        strcpy(quotient, q);
        
        // temp = t - quotient * newt
        mul_hex(quotient, newt, mul_temp);
        sub_hex(t, mul_temp, sub_temp);
        strcpy(temp, sub_temp);
        
        // t = newt, newt = temp
        strcpy(t, newt);
        strcpy(newt, temp);
        
        // temp = r - quotient * newr
        mul_hex(quotient, newr, mul_temp);
        sub_hex(r, mul_temp, sub_temp);
        strcpy(temp, sub_temp);
        
        // r = newr, newr = temp
        strcpy(r, newr);
        strcpy(newr, temp);
        
        trim_leading_zeros(t);
        trim_leading_zeros(newt);
        trim_leading_zeros(r);
        trim_leading_zeros(newr);
    }
    
    while (compare_hex(t, "0") < 0) {
        char add_temp[512];
        add_hex(t, m, add_temp);
        strcpy(t, add_temp);
    }
    mod_hex(t, m, result);
}

// Сложение двух точек на эллиптической кривой
void point_add(const char* x1, const char* y1, const char* x2, const char* y2, 
               char* x3, char* y3, const char* p) {
    char lambda[512], temp1[512], temp2[512], inv[512];
    
    // Проверка на бесконечно удалённую точку
    if (strcmp(x1, "0") == 0 && strcmp(y1, "0") == 0) {
        strcpy(x3, x2);
        strcpy(y3, y2);
        return;
    }
    if (strcmp(x2, "0") == 0 && strcmp(y2, "0") == 0) {
        strcpy(x3, x1);
        strcpy(y3, y1);
        return;
    }
    
    // Проверка на противоположные точки
    if (strcmp(x1, x2) == 0) {
        char y1_plus_y2[512];
        add_hex(y1, y2, y1_plus_y2);
        if (strcmp(y1_plus_y2, "0") == 0) {
            strcpy(x3, "0");
            strcpy(y3, "0");
            return;
        }
    }
    
    if (strcmp(x1, x2) == 0 && strcmp(y1, y2) == 0) {
        // Удвоение: lambda = (3*x1^2 + a) / (2*y1)
        char x1_sq[512], three_x1_sq[512], two_y1[512];
        mul_hex(x1, x1, x1_sq);
        mul_hex(x1_sq, "3", three_x1_sq);
        // a = 0, поэтому просто three_x1_sq
        mul_hex(y1, "2", two_y1);
        inverse_hex(two_y1, p, inv);
        mul_hex(three_x1_sq, inv, lambda);
    } else {
        // Сложение: lambda = (y2 - y1) / (x2 - x1)
        char dy[512], dx[512];
        sub_hex(y2, y1, dy);
        sub_hex(x2, x1, dx);
        inverse_hex(dx, p, inv);
        mul_hex(dy, inv, lambda);
    }
    
    mod_hex(lambda, p, lambda);
    
    // x3 = lambda^2 - x1 - x2
    char lambda_sq[512];
    mul_hex(lambda, lambda, lambda_sq);
    sub_hex(lambda_sq, x1, temp1);
    sub_hex(temp1, x2, x3);
    mod_hex(x3, p, x3);
    
    // y3 = lambda * (x1 - x3) - y1
    char x1_minus_x3[512];
    sub_hex(x1, x3, x1_minus_x3);
    mul_hex(lambda, x1_minus_x3, temp1);
    sub_hex(temp1, y1, y3);
    mod_hex(y3, p, y3);
}

int main() {
    printf("=== Задание №5: Сложение точек G + P ===\n");
    printf("Полная реализация арифметики эллиптической кривой secp256k1\n\n");
    
    printf("Параметры кривой:\n");
    printf("p = %s\n", p_hex);
    printf("a = %s\n", a_hex);
    printf("b = %s\n\n", b_hex);
    
    printf("Точка G (генератор):\n");
    printf("x = %s\n", Gx_hex);
    printf("y = %s\n\n", Gy_hex);
    
    printf("Точка P:\n");
    printf("x = %s\n", Px_hex);
    printf("y = %s\n\n", Py_hex);
    
    char Rx[512], Ry[512];
    point_add(Gx_hex, Gy_hex, Px_hex, Py_hex, Rx, Ry, p_hex);
    
    printf("Результат G + P:\n");
    printf("x = %s\n", Rx);
    printf("y = %s\n", Ry);
    
    return 0;
}