---

// task6_mul3.c - Умножение базовой точки G на 3 (3G)

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

#define	MaxDig 1000
#define	Osn 0x100
#define	mm	8

typedef struct{
	int lm[MaxDig];
	int len;
	int sign;
} LDig;

// ============ ФУНКЦИИ ДЛИННОЙ АРИФМЕТИКИ ============

void InitLong(LDig *A){
	int i;
	for (i=0; i<MaxDig; i++) A->lm[i]=0;
	A->len=1; 
	A->sign=1;
}

void Read16Long(LDig *A, char *S){
	char chs[3];
	int i,len, b[100],ch,k=0;
	if (S[0]=='-'){ 
		A->sign = -1; 
		k=1; 
	} else {
		A->sign = 1;
	}
	strcpy(chs,"");
	len = strlen(S);
	A->len = len/2;
	for (i=k;i<len;i+=2){
		chs[0]=S[i]; 
		chs[1]=S[i+1]; 
		chs[2]='\0';
		sscanf(chs,"%02x",&ch);
		b[i/2]=ch;
	}
	for(i=0; i<A->len;i++) 
		A->lm[A->len-1-i]=b[i];
}

void Write16Long(LDig *A, char *S){
	char s[10];
	int i;
	if (A->sign<0) strcpy(S,"-");
	else strcpy(S,"");
	for (i=A->len-1;i>=0;i--){
		sprintf(s,"%02x", A->lm[i]);
		strcat(S,s);
	}
}

void ShowLongS(LDig *A){
	char S[256];
	Write16Long(A, S);
	printf("%s\n",S);
}

int IsNulLong(LDig *A){
	return ((A->len==1) && (A->lm[0]==0));
}

void DigToArray(int k, LDig *A){
	int res, i=0, sign=1;
	if (k<0) sign=-1;
	res = (k<0) ? -k : k;
	if (res == 0) {
		A->len=1;
		A->lm[0]=0;
		A->sign=1;
		return;
	}
	while (res>0){
		A->lm[i]=res%Osn;
		res/=Osn;
		i++;
	}
	A->len=i;
	A->sign=sign;
}

int Eq(LDig *A, LDig *B){
	int i;
	if((A->len!=B->len)||(A->sign!=B->sign)) return 0;
	for(i=0;i<A->len;i++) 
		if(A->lm[i]!=B->lm[i]) return 0;
	return 1;
}

int More(LDig *A, LDig *B){
	int i;
	if(A->len > B->len) return 1;
	if(A->len < B->len) return 0;
	for(i=A->len-1;i>=0;i--){
		if(A->lm[i] > B->lm[i]) return 1;
		if(A->lm[i] < B->lm[i]) return 0;
	}
	return 0;
}

int More_Shift(LDig *A, LDig *B, int sp){
	int i;
	if(A->len > B->len+sp) return 0;
	if(A->len < B->len+sp) return 1;
	for(i=A->len-1;i>=sp;i--){
		if(A->lm[i] > B->lm[i-sp]) return 0;
		if(A->lm[i] < B->lm[i-sp]) return 1;
	}
	for(i=0;i<sp;i++) 
		if(A->lm[i]>0) return 0;
	return 2;
}

void Sum_Shift(LDig *A, LDig *B, int sp){
	int i,k;
	if(A->len > B->len+sp) k=A->len;
	else k=B->len+sp;
	for(i=0;i<k;i++){
		A->lm[i+sp+1] += (A->lm[i+sp]+B->lm[i])/Osn;
		A->lm[i+sp] = (A->lm[i+sp]+B->lm[i])%Osn;
	}
	if(A->lm[k]==0) A->len=k;
	else A->len=k+1;
}

void Sub_Shift(LDig *A, LDig *B, int sp){
	int i,j;
	for(i=0;i<B->len;i++){
		A->lm[i+sp] -= B->lm[i];
		j=i;
		while((A->lm[j+sp]<0) && (j<A->len-1)){
			A->lm[j+sp] += Osn;
			A->lm[j+sp+1]--;
			j++;
		}
	}
	i=A->len-1;
	while((i>0) && (A->lm[i]==0)) i--;
	A->len=i+1;
}

void SumTwo(LDig *A, LDig *B, LDig *C){
	*C = *A;
	Sum_Shift(C, B, 0);
}

void SubTwo(LDig *A, LDig *B, LDig *C){
	*C = *A;
	Sub_Shift(C, B, 0);
}

void SumLong(LDig *A, LDig *B, LDig *C){
	if(A->sign == B->sign){
		SumTwo(A, B, C);
		C->sign = A->sign;
	} else {
		if(More(A, B)){
			SubTwo(A, B, C);
			C->sign = A->sign;
		} else {
			SubTwo(B, A, C);
			C->sign = B->sign;
		}
	}
}

void SumLongA(LDig *A, LDig *B){
	LDig C;
	InitLong(&C);
	SumLong(A, B, &C);
	*A = C;
}

void SubLong(LDig *A, LDig *B, LDig *C){
	if(A->sign != B->sign){
		SumTwo(A, B, C);
		C->sign = A->sign;
	} else {
		if(More(A, B)){
			SubTwo(A, B, C);
			C->sign = A->sign;
		} else {
			SubTwo(B, A, C);
			C->sign = -B->sign;
		}
	}
}

void Mul(LDig *A, int K, LDig *C){
	int i;
	InitLong(C);
	if(K != 0){
		int absK = (K>0) ? K : -K;
		for(i=0;i<A->len;i++){
			C->lm[i+1] = (C->lm[i] + A->lm[i]*absK) / Osn;
			C->lm[i] = (C->lm[i] + A->lm[i]*absK) % Osn;
		}
		if(C->lm[A->len] > 0) C->len = A->len+1;
		else C->len = A->len;
	}
	C->sign = A->sign * ((K>0) ? 1 : -1);
}

void MulA(LDig *A, int K){
	LDig C;
	InitLong(&C);
	Mul(A, K, &C);
	*A = C;
}

void MulTwoLong(LDig *A, LDig *B, LDig *C){
	int i;
	LDig C1;
	InitLong(C);
	for(i=0;i<B->len;i++){
		Mul(A, B->lm[i], &C1);
		Sum_Shift(C, &C1, i);
	}
	C->sign = A->sign * B->sign;
}

void LongDivLong(LDig *A, LDig *B, LDig *Res, LDig *Ost){
	int sp, Down, Up, k;
	LDig C;
	*Ost = *A;
	sp = A->len - B->len;
	if(sp < 0) sp = 0;
	if(More_Shift(A, B, sp) == 1) sp--;
	if(sp < 0) sp = 0;
	Res->len = sp+1;
	while(sp >= 0){
		Down = 0; 
		Up = Osn;
		while(Up - 1 > Down){
			InitLong(&C);
			Mul(B, (Up+Down)/2, &C);
			k = More_Shift(Ost, &C, sp);
			if(k == 0) Down = (Down+Up)/2;
			else if(k == 1) Up = (Up+Down)/2;
			else { Up = (Up+Down)/2; Down = Up; }
		}
		InitLong(&C);
		Mul(B, (Up+Down)/2, &C);
		if(More_Shift(Ost, &C, 0) == 0) 
			Sub_Shift(Ost, &C, sp);
		else { 
			Sub_Shift(&C, Ost, sp); 
			*Ost = C; 
		}
		Res->lm[sp] = (Up+Down)/2;
		sp--;
	}
	Res->sign = A->sign * B->sign;
	Ost->sign = A->sign;
}

void OstLong(LDig *A, LDig *Ost, LDig *P){
	LDig Res;
	InitLong(&Res);
	LongDivLong(A, P, &Res, Ost);
	if((Ost->sign < 0) && !IsNulLong(Ost)) 
		SumLongA(Ost, P);
}

void OstLongA(LDig *A, LDig *P){
	LDig Ost;
	InitLong(&Ost);
	OstLong(A, &Ost, P);
	*A = Ost;
}

// ============ ФУНКЦИИ ДЛЯ ЭЛЛИПТИЧЕСКОЙ КРИВОЙ ============

char ps[] = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f";
int a_coef = 0;
int b_coef = 7;
char xGs[] = "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798";
char yGs[] = "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8";

// Расширенный алгоритм Евклида
void LongEnhEvklid(LDig *A, LDig *B, LDig *t, LDig *nod){
	LDig r1, r2, t1, t2, r, q, tt, C;
	InitLong(&r1); InitLong(&r2);
	InitLong(&t1); InitLong(&t2);
	InitLong(&q); InitLong(&r);
	InitLong(&tt); InitLong(&C);
	
	r1 = *A; 
	r2 = *B;
	DigToArray(0, &t1);
	DigToArray(1, &t2);
	
	while(!IsNulLong(&r2)){
		LongDivLong(&r1, &r2, &q, &r);
		r1 = r2; 
		r2 = r;
		MulTwoLong(&q, &t2, &C);
		SubLong(&t1, &C, &tt);
		t1 = t2; 
		t2 = tt;
	}
	*nod = r1;
	*t = t1;
}

void invA(LDig *A, LDig *T, LDig *P){
	LDig t, nod, Ed;
	InitLong(&t); 
	InitLong(&nod); 
	InitLong(&Ed);
	Ed.lm[0] = 1;
	Ed.len = 1;
	LongEnhEvklid(P, A, &t, &nod);
	if(!Eq(&nod, &Ed)) 
		printf("Ошибка: нет обратного элемента\n");
	*T = t;
}

// Сложение двух точек
void AddPoint(LDig *xP, LDig *yP, LDig *xQ, LDig *yQ, LDig *xR, LDig *yR, LDig *p){
	LDig m, s1, s2, C1, C2, C3;
	InitLong(&m); InitLong(&s1); InitLong(&s2);
	InitLong(&C1); InitLong(&C2); InitLong(&C3);
	
	SubLong(xP, xQ, &C1);
	OstLongA(&C1, p);
	SubLong(yP, yQ, &C2);
	OstLongA(&C2, p);
	
	if(IsNulLong(xP) && IsNulLong(yP)){
		*xR = *xQ; *yR = *yQ;
		return;
	}
	if(IsNulLong(xQ) && IsNulLong(yQ)){
		*xR = *xP; *yR = *yP;
		return;
	}
	
	if(IsNulLong(&C1) && IsNulLong(&C2)){
		MulTwoLong(xP, xP, &C1);
		OstLongA(&C1, p);
		MulA(&C1, 3);
		DigToArray(a_coef, &C2);
		SumLongA(&C1, &C2);
		OstLong(&C1, &s1, p);
		
		Mul(yP, 2, &C1);
		OstLong(&C1, &C2, p);
		invA(&C2, &s2, p);
		OstLongA(&s2, p);
	} else {
		OstLong(&C2, &s1, p);
		OstLong(&C1, &C3, p);
		invA(&C3, &s2, p);
		OstLongA(&s2, p);
	}
	
	MulTwoLong(&s1, &s2, &m);
	OstLongA(&m, p);
	
	MulTwoLong(&m, &m, &C1);
	OstLongA(&C1, p);
	SumLong(xP, xQ, &C2);
	OstLongA(&C2, p);
	SubLong(&C1, &C2, xR);
	OstLongA(xR, p);
	
	SubLong(xR, xP, &C1);
	OstLongA(&C1, p);
	MulTwoLong(&C1, &m, &C2);
	OstLongA(&C2, p);
	SumLong(yP, &C2, yR);
	OstLongA(yR, p);
	
	yR->sign = -yR->sign;
	OstLongA(yR, p);
}

// Умножение точки на число (алгоритм удвоения-сложения)
void ScalMulPoint(LDig *K, LDig *xP, LDig *yP, LDig *xR, LDig *yR, LDig *p){
	LDig Sx, Sy, xP1, yP1;
	LDig zero;
	InitLong(&Sx); InitLong(&Sy);
	InitLong(&xP1); InitLong(&yP1);
	InitLong(&zero);
	
	xP1 = *xP;
	yP1 = *yP;
	
	int first = 1;
	
	for(int i=0; i<K->len; i++){
		int m = K->lm[i];
		for(int j=0; j<mm; j++){
			if(i==0 && j==0){
				if(m & 1){
					Sx = xP1;
					Sy = yP1;
					first = 0;
				}
			} else {
				// Удвоение
				LDig x2, y2;
				InitLong(&x2); InitLong(&y2);
				AddPoint(&xP1, &yP1, &xP1, &yP1, &x2, &y2, p);
				xP1 = x2; yP1 = y2;
				
				if(m & 1){
					if(first){
						Sx = xP1;
						Sy = yP1;
						first = 0;
					} else {
						LDig x_new, y_new;
						InitLong(&x_new); InitLong(&y_new);
						AddPoint(&Sx, &Sy, &xP1, &yP1, &x_new, &y_new, p);
						Sx = x_new; Sy = y_new;
					}
				}
			}
			m = m / 2;
		}
	}
	*xR = Sx;
	*yR = Sy;
}

// ============ MAIN ============

int main() {
	LDig xG, yG, xR, yR;
	LDig p_mod;
	LDig three;
	
	printf("=== Задание №6: Умножение G на 3 (3G) ===\n\n");
	
	// Инициализация модуля p
	InitLong(&p_mod);
	Read16Long(&p_mod, ps);
	
	// Инициализация точки G
	InitLong(&xG);
	InitLong(&yG);
	Read16Long(&xG, xGs);
	Read16Long(&yG, yGs);
	
	printf("Параметры кривой:\n");
	printf("p = %s\n", ps);
	printf("a = %d\n", a_coef);
	printf("b = %d\n\n", b_coef);
	
	printf("Точка G:\n");
	printf("xG = "); ShowLongS(&xG);
	printf("yG = "); ShowLongS(&yG);
	printf("\n");
	
	// Число 3
	InitLong(&three);
	DigToArray(3, &three);
	
	// Вычисляем 3G
	InitLong(&xR);
	InitLong(&yR);
	ScalMulPoint(&three, &xG, &yG, &xR, &yR, &p_mod);
	
	printf("Результат 3G = G * 3:\n");
	printf("x = "); ShowLongS(&xR);
	printf("y = "); ShowLongS(&yR);
	
	return 0;
}