---

Файл:EllipLong.c
//циклическая группа (скалярное произведение удвоение-сложение Num*(xP,yP))
#include <stdio.h>
#include <math.h>
#include "larif16-2.c"
#include <string.h>
#include <stdlib.h>
#include <time.h>

//параметры области определения

//================================================================================
	//модуль
char	ps[] = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"; 
	//параметры эллиптической фукции
int	a = 0;
int	b = 7;
	//базовая точка
char	xGs[] = "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798";
char	yGs[] = "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8";
	//порядок подгруппы
char	ns[] = "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141";
	//кофактор
int h=1;
//====================================================================================
/*
char	ps[] = "61"; 
	//параметры эллиптической фукции
int	a = 2;
int	b = 3;
//базовая точка	

char	xGs[] = "3";
//char	xGs[] = "79be667ef9dcbbac55a06295ce870b00029bfcdb2dce28d959f2815b16f81798";
char	yGs[] = "6";
	//порядок подгруппы
char	ns[] = "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141";
	//кофактор
int h=1;
*/
LDig P, xG, yG, n;

//инициализация параметров эллиптической кривой
void InitPar(){
	InitLong(&P);
	InitLong(&n);
	InitLong(&xG);
	InitLong(&yG);
	Read16Long(&P,ps);
	Read16Long(&n,ns);
	Read16Long(&xG,xGs);
	Read16Long(&yG,yGs);
	
	return;
}

//длинный остаток от деления (mod), результат в Ost
void OstLong(LDig *A, LDig *Ost){
	LDig Res;
	InitLong(&Res);
	LongDivLong(A, &P, &Res, Ost);
	//если остаток - отрицательный
	if ((Ost->sign<0)&&!IsNulLong(Ost)){
		SumLongA(Ost, &P);
	}

	return;
}

void OstLongMod(LDig *A, LDig *Ost, LDig *mod){
	LDig Res;
	InitLong(&Res);
	LongDivLong(A, mod, &Res, Ost);
	//если остаток - отрицательный
	if ((Ost->sign<0)&&!IsNulLong(Ost)){
		SumLongA(Ost, mod);
	}

	return;
}

//длинный остаток от деления (mod), результат в A
void OstLongA(LDig *A){
	LDig Ost;
	InitLong(&Ost);
	OstLong(A, &Ost);
	*A=Ost;
	return;
}

void OstLongAMod(LDig *A, LDig *mod){
	LDig Ost;
	InitLong(&Ost);
	OstLongMod(A, &Ost, mod);
	*A=Ost;
	return;
}

//расширенный алгоритм Евклида для длинных чисел без s, не используется
void  LongEnhEvklid(LDig *A, LDig *B, LDig *t, LDig *nod){
	LDig *r1, *r2, *t1, *t2, *r, *q, *tt,  *C;
	int i=0;
	char s1[256];
	r1=malloc(sizeof(LDig));
	r2=malloc(sizeof(LDig));
	t1=malloc(sizeof(LDig));
	t2=malloc(sizeof(LDig));	
	r=malloc(sizeof(LDig));
	q=malloc(sizeof(LDig));
	tt=malloc(sizeof(LDig));
	C=malloc(sizeof(LDig));
	InitLong(r1); 	InitLong(r2);
	InitLong(t1); 	InitLong(t2);	
	InitLong(q); 	InitLong(r);
	InitLong(tt);
	InitLong(C); 	
//ShowLongS(A);

	//начальные присвоения
	*r1=*A;	*r2=*B;
	t1->lm[0]=0;	t2->lm[0]=1;
	Dig16Str(i, s1);
//	printf("s1=%s\n",s1);
//	WriteInFile(r2,s1);
	while(!IsNulLong(r2)){
		i++;
		InitLong(q); 	InitLong(r);
		if (i==0x7f){
//		WriteInFile(r2,"r2");	
//		WriteInFile(r1,"r1");
		}
		LongDivLong(r1,r2,q,r);
		*r1=*r2;	*r2=*r;
		InitLong(C); 
		InitLong(tt);		
		MulTwoLong(q, t2, C);
		SubLong(t1,C,tt);
		*t1=*t2;	*t2=*tt;

	Dig16Str(i, s1);
//	printf("s1=%s\n",s1);
//	WriteInFile(r2,s1);
	}
//	printf("i=%d\n",i);
	*nod=*r1;
	*t=*t1;
	free(r1);	free(r2);	
	free(t1);	free(t2);	
	free(r);		free(q);	
	free(tt);	free(C);

	return;
}

	//Мультипликативная инверсия A*T=1 ищем T
void invA(LDig *A, LDig *T){
	LDig t, nod,	Ed;
	InitLong(&t);
	InitLong(&nod);
	InitLong(&Ed);
	Ed.lm[0]=1;
//	ShowLongS(A);	
	LongEnhEvklid(&P, A, &t, &nod);
	if(!Eq(&nod, &Ed)) printf("err\n");
//	ShowLongS(&nod);
	*T=t;

	return;
}

	//Мультипликативная инверсия по модулю A*T=1 mod n ищем T
void invAMod(LDig *A, LDig *T, LDig *n){
	LDig t, nod,	Ed;
	InitLong(&t);
	InitLong(&nod);
	InitLong(&Ed);
	Ed.lm[0]=1;
//	ShowLongS(A);	
	LongEnhEvklid(n, A, &t, &nod);
	if(!Eq(&nod, &Ed)) printf("err\n");
//	ShowLongS(&nod);
	*T=t;

	return;
}

//сложение двух точек P+Q=R, результат в R
void AddPoint(LDig *xP, LDig *yP, LDig *xQ, LDig *yQ, LDig *xR, LDig *yR){
	LDig *m, *s1, *s2, *C1, *C2, *C3;
	m=malloc(sizeof(LDig));
	s1=malloc(sizeof(LDig));
	s2=malloc(sizeof(LDig));		
	C1=malloc(sizeof(LDig));
	C2=malloc(sizeof(LDig));
	C3=malloc(sizeof(LDig));		

	InitLong(m);
	InitLong(s1);
	InitLong(s2);	
	InitLong(C1);	
	InitLong(C2);		
	InitLong(C3);		
	
	SubLong(xP, xQ, C1);	//C1=xP-xQ
	OstLongA(C1);
//	ShowLongS(C1);
	SubLong(yP, yQ, C2);	//C2=yP-yQ
	OstLongA(C2);
	
	//Проверка на особую точку
	//Если P=0, то P+Q=Q
	if(IsNulLong(xP)&&IsNulLong(yP)){
		*xR=*xQ;
		*yR=*yQ;
		return;
	}
	//Если Q=0, то P+Q=P
	if(IsNulLong(xQ)&&IsNulLong(yQ)){
		*xR=*xP;
		*yR=*yP;
		return;
	}
	//Если P=-Q (xP=xQ и yP=-yQ) то R-особая точка
	if(IsNulLong(C1)){
		if (!IsNulLong(C2)){
			SumLong(yP,yQ,C3);
			OstLongA(C3);
			if(IsNulLong(C3)){
				InitLong(xR);
				InitLong(yR);
//				InitLong(C3);
				return;
			}
		}
	}
	
	if (IsNulLong(C1)&&IsNulLong(C2)){
		InitLong(C1);
		InitLong(C2);
		//s1=xP*xP*3+a (mod p)
		MulTwoLong(xP, xP, C1);	//C1=xP*xP
		OstLongA(C1);
		MulA(C1, 3);		//C1=C1*3
		DigToArray(a,C2);
		SumLongA(C1,C2);	//C1+a
		OstLong(C1, s1);	//s1=C1%p
		InitLong(C1);
		InitLong(C2);
		//s2=(2*yP)^-1
		Mul(yP, 2, C1);	//C1=yP*2
		OstLong(C1,C2);
		if(IsNulLong(C2)) printf("null\n");
		invA(C2, s2);		//s2=C1^-1
		OstLongA(s2);
	}
	else{
		//s1=yP-yQ
		OstLong(C2, s1);		//s1=C2%p
		//s2=xP-xQ
		OstLong(C1,C3);
		if(IsNulLong(C3)) printf("null\n");
//		if ((i==0)&&(j==13))	WriteInFile(C3, "C3");
		
		invA(C3, s2);					//s2=C1^-1
		OstLongA(s2);
	}
	InitLong(C1);						//C1=0
	InitLong(C2);						//C2=0

	//xR=m*m-(xP+xQ)
	MulTwoLong(s1, s2, m);		//m=s1*s2
	OstLongA(m);			//m=C1%p
	MulTwoLong(m, m, C1);	//C1=m*m
	OstLongA(C1);
	SumLong(xP, xQ, C2);			//C2=xP+xQ
	OstLongA(C2);
	SubLong(C1, C2, xR);		//xR=C1-C2
	OstLongA(xR);			//xR=C3%p
	InitLong(C1);						//C1=0
	InitLong(C2);						//C2=0
	
	//yR=yP+m(xR-xP)
	SubLong(xR, xP, C1);			//C1=xR-xP
	OstLongA(C1);

	MulTwoLong(C1, m, C2);	//C2=C1*m	
	OstLongA(C2);
	SumLong(yP, C2, yR);		//C3=yP+C2
	OstLongA(yR);

	//меняем знак yR=-yR
	yR->sign=-yR->sign;			//C1=-C1
	OstLongA(yR);			//yR=C1%p
//			ShowLongS(yR);
	free(m); free(s1);	free(s2); free(C1);	free(C2); free(C3);

	return;
}

//сложение двух точек P+Q, результат в P
void AddPointP(LDig *xP, LDig *yP, LDig *xQ, LDig *yQ){
	LDig *xR, *yR;
	xR=malloc(sizeof(LDig));
	yR=malloc(sizeof(LDig));		
		
	InitLong(xR);		
	InitLong(yR);		
	
	AddPoint(xP, yP, xQ, yQ, xR, yR);
	*xP=*xR;
	*yP=*yR;
	free(xR); free(yR);
	return;
}

//скалярное произведение (алгоритм удвоения-сложения)
void ScalMulPoint(LDig *K, LDig *xP, LDig *yP, LDig *xR, LDig *yR){
	int i,j,m;
	LDig Sx, Sy, xP1, yP1;
	InitLong(&Sx);
	InitLong(&Sy);
	xP1=*xP;
	yP1=*yP;
//	printf("len=%d\n",K->len);
	for (i=0;i<K->len;i++){	//цикл по байтам
		m=K->lm[i];
//		printf("m=%x i=%d\n", m,i);
		for (j=0;j<mm;j++){	//цикл по разрядам внутри байта
			if ((i==0)&&(j==0)){
				if((m%2)==1) 	{Sx=*xP;	Sy=*yP;}	//AddPointP(&Sx, &Sy,  xP, yP); 	
			}
			else{			
				AddPointP(&xP1, &yP1, &xP1, &yP1);	//удвоение
				if((m%2)==1) 	AddPointP(&Sx, &Sy,  &xP1, &yP1); 	//сложение
				if ((j==13)&&(i==0)) ShowLongS(&Sy);
//				printf("		%d\n",j);
			}
			m=m/2;
		}
	}
	*xR=Sx;
	*yR=Sy;
	
	return;
}

//случайное длинное от 1 до n-1
void LongRand(LDig *M){
	int i, len;
	len=n.len;
	srand(time(NULL));
	do{
		for (i=0; i<len;i++){
			M->lm[i]=(unsigned char)rand();
//			printf("%x",M->lm[i]);
		}
		M->len=len;
//		printf("%d \n",len);
	}while (More_Eq(M, &n));
	return ;
}