Google Git
Sign in
apache / incubator-milagro-crypto / bc000209c88d842a83ffb0d1950438a1d2e43602 / . / version3 / c / fp16.c
blob: e2579c98f73b70a1b875e6dc7758d534ea85a4e7 [file] [log] [blame]
/*
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements. See the NOTICE file
distributed with this work for additional information
regarding copyright ownership. The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied. See the License for the
specific language governing permissions and limitations
under the License.
*/
/* AMCL Fp^8 functions */
/* FP16 elements are of the form a+ib, where i is sqrt(sqrt(-1+sqrt(-1))) */
#include "fp16_YYY.h"
/* test x==0 ? */
int FP16_YYY_iszilch(FP16_YYY *x)
{
if (FP8_YYY_iszilch(&(x->a)) && FP8_YYY_iszilch(&(x->b))) return 1;
return 0;
}
/* test x==1 ? */
int FP16_YYY_isunity(FP16_YYY *x)
{
if (FP8_YYY_isunity(&(x->a)) && FP8_YYY_iszilch(&(x->b))) return 1;
return 0;
}
/* test is w real? That is in a+ib test b is zero */
int FP16_YYY_isreal(FP16_YYY *w)
{
return FP8_YYY_iszilch(&(w->b));
}
/* return 1 if x==y, else 0 */
int FP16_YYY_equals(FP16_YYY *x,FP16_YYY *y)
{
if (FP8_YYY_equals(&(x->a),&(y->a)) && FP8_YYY_equals(&(x->b),&(y->b)))
return 1;
return 0;
}
/* set FP16 from two FP8s */
void FP16_YYY_from_FP8s(FP16_YYY *w,FP8_YYY * x,FP8_YYY* y)
{
FP8_YYY_copy(&(w->a), x);
FP8_YYY_copy(&(w->b), y);
}
/* set FP16 from FP8 */
void FP16_YYY_from_FP8(FP16_YYY *w,FP8_YYY *x)
{
FP8_YYY_copy(&(w->a), x);
FP8_YYY_zero(&(w->b));
}
/* set high part of FP16 from FP8 */
void FP16_YYY_from_FP8H(FP16_YYY *w,FP8_YYY *x)
{
FP8_YYY_copy(&(w->b), x);
FP8_YYY_zero(&(w->a));
}
/* FP16 copy w=x */
void FP16_YYY_copy(FP16_YYY *w,FP16_YYY *x)
{
if (w==x) return;
FP8_YYY_copy(&(w->a), &(x->a));
FP8_YYY_copy(&(w->b), &(x->b));
}
/* FP16 w=0 */
void FP16_YYY_zero(FP16_YYY *w)
{
FP8_YYY_zero(&(w->a));
FP8_YYY_zero(&(w->b));
}
/* FP16 w=1 */
void FP16_YYY_one(FP16_YYY *w)
{
FP8_YYY_one(&(w->a));
FP8_YYY_zero(&(w->b));
}
/* Set w=-x */
void FP16_YYY_neg(FP16_YYY *w,FP16_YYY *x)
{
/* Just one field neg */
FP8_YYY m,t;
FP16_YYY_norm(x);
FP8_YYY_add(&m,&(x->a),&(x->b));
FP8_YYY_norm(&m);
FP8_YYY_neg(&m,&m);
FP8_YYY_add(&t,&m,&(x->b));
FP8_YYY_add(&(w->b),&m,&(x->a));
FP8_YYY_copy(&(w->a),&t);
FP16_YYY_norm(w);
}
/* Set w=conj(x) */
void FP16_YYY_conj(FP16_YYY *w,FP16_YYY *x)
{
FP8_YYY_copy(&(w->a), &(x->a));
FP8_YYY_neg(&(w->b), &(x->b));
FP16_YYY_norm(w);
}
/* Set w=-conj(x) */
void FP16_YYY_nconj(FP16_YYY *w,FP16_YYY *x)
{
FP8_YYY_copy(&(w->b),&(x->b));
FP8_YYY_neg(&(w->a), &(x->a));
FP16_YYY_norm(w);
}
/* Set w=x+y */
void FP16_YYY_add(FP16_YYY *w,FP16_YYY *x,FP16_YYY *y)
{
FP8_YYY_add(&(w->a), &(x->a), &(y->a));
FP8_YYY_add(&(w->b), &(x->b), &(y->b));
}
/* Set w=x-y */
/* Input y MUST be normed */
void FP16_YYY_sub(FP16_YYY *w,FP16_YYY *x,FP16_YYY *y)
{
FP16_YYY my;
FP16_YYY_neg(&my, y);
FP16_YYY_add(w, x, &my);
}
/* reduce all components of w mod Modulus */
void FP16_YYY_reduce(FP16_YYY *w)
{
FP8_YYY_reduce(&(w->a));
FP8_YYY_reduce(&(w->b));
}
/* normalise all elements of w */
void FP16_YYY_norm(FP16_YYY *w)
{
FP8_YYY_norm(&(w->a));
FP8_YYY_norm(&(w->b));
}
/* Set w=s*x, where s is FP8 */
void FP16_YYY_pmul(FP16_YYY *w,FP16_YYY *x,FP8_YYY *s)
{
FP8_YYY_mul(&(w->a),&(x->a),s);
FP8_YYY_mul(&(w->b),&(x->b),s);
}
/* Set w=s*x, where s is FP2 */
void FP16_YYY_qmul(FP16_YYY *w,FP16_YYY *x,FP2_YYY *s)
{
FP8_YYY_qmul(&(w->a),&(x->a),s);
FP8_YYY_qmul(&(w->b),&(x->b),s);
}
/* Set w=s*x, where s is int */
void FP16_YYY_imul(FP16_YYY *w,FP16_YYY *x,int s)
{
FP8_YYY_imul(&(w->a),&(x->a),s);
FP8_YYY_imul(&(w->b),&(x->b),s);
}
/* Set w=x^2 */
/* Input MUST be normed */
void FP16_YYY_sqr(FP16_YYY *w,FP16_YYY *x)
{
FP8_YYY t1,t2,t3;
FP8_YYY_mul(&t3,&(x->a),&(x->b)); /* norms x */
FP8_YYY_copy(&t2,&(x->b));
FP8_YYY_add(&t1,&(x->a),&(x->b));
FP8_YYY_times_i(&t2);
FP8_YYY_add(&t2,&(x->a),&t2);
FP8_YYY_norm(&t1); // 2
FP8_YYY_norm(&t2); // 2
FP8_YYY_mul(&(w->a),&t1,&t2);
FP8_YYY_copy(&t2,&t3);
FP8_YYY_times_i(&t2);
FP8_YYY_add(&t2,&t2,&t3);
FP8_YYY_norm(&t2); // 2
FP8_YYY_neg(&t2,&t2);
FP8_YYY_add(&(w->a),&(w->a),&t2); /* a=(a+b)(a+i^2.b)-i^2.ab-ab = a*a+ib*ib */
FP8_YYY_add(&(w->b),&t3,&t3); /* b=2ab */
FP16_YYY_norm(w);
}
/* Set w=x*y */
/* Inputs MUST be normed */
void FP16_YYY_mul(FP16_YYY *w,FP16_YYY *x,FP16_YYY *y)
{
FP8_YYY t1,t2,t3,t4;
FP8_YYY_mul(&t1,&(x->a),&(y->a));
FP8_YYY_mul(&t2,&(x->b),&(y->b));
FP8_YYY_add(&t3,&(y->b),&(y->a));
FP8_YYY_add(&t4,&(x->b),&(x->a));
FP8_YYY_norm(&t4); // 2
FP8_YYY_norm(&t3); // 2
FP8_YYY_mul(&t4,&t4,&t3); /* (xa+xb)(ya+yb) */
FP8_YYY_neg(&t3,&t1); // 1
FP8_YYY_add(&t4,&t4,&t3); //t4E=3
FP8_YYY_norm(&t4);
FP8_YYY_neg(&t3,&t2); // 1
FP8_YYY_add(&(w->b),&t4,&t3); //wbE=3
FP8_YYY_times_i(&t2);
FP8_YYY_add(&(w->a),&t2,&t1);
FP16_YYY_norm(w);
}
/* output FP16 in format [a,b] */
void FP16_YYY_output(FP16_YYY *w)
{
printf("[");
FP8_YYY_output(&(w->a));
printf(",");
FP8_YYY_output(&(w->b));
printf("]");
}
void FP16_YYY_rawoutput(FP16_YYY *w)
{
printf("[");
FP8_YYY_rawoutput(&(w->a));
printf(",");
FP8_YYY_rawoutput(&(w->b));
printf("]");
}
/* Set w=1/x */
void FP16_YYY_inv(FP16_YYY *w,FP16_YYY *x)
{
FP8_YYY t1,t2;
FP8_YYY_sqr(&t1,&(x->a));
FP8_YYY_sqr(&t2,&(x->b));
FP8_YYY_times_i(&t2);
FP8_YYY_norm(&t2);
FP8_YYY_sub(&t1,&t1,&t2);
FP8_YYY_norm(&t1);
FP8_YYY_inv(&t1,&t1);
FP8_YYY_mul(&(w->a),&t1,&(x->a));
FP8_YYY_neg(&t1,&t1);
FP8_YYY_norm(&t1);
FP8_YYY_mul(&(w->b),&t1,&(x->b));
}
/* w*=i where i = sqrt(sqrt(-1+sqrt(-1))) */
void FP16_YYY_times_i(FP16_YYY *w)
{
FP8_YYY s,t;
FP8_YYY_copy(&s,&(w->b));
FP8_YYY_copy(&t,&(w->a));
FP8_YYY_times_i(&s);
FP8_YYY_copy(&(w->a),&s);
FP8_YYY_copy(&(w->b),&t);
FP16_YYY_norm(w);
}
void FP16_YYY_times_i2(FP16_YYY *w)
{
FP8_YYY_times_i(&(w->a));
FP8_YYY_times_i(&(w->b));
}
void FP16_YYY_times_i4(FP16_YYY *w)
{
FP8_YYY_times_i2(&(w->a));
FP8_YYY_times_i2(&(w->b));
}
/* Set w=w^p using Frobenius */
void FP16_YYY_frob(FP16_YYY *w,FP2_YYY *f)
{ // f=(i+1)^(p-3)/8
FP2_YYY ff;
FP2_YYY_sqr(&ff,f); // (i+1)^(p-3)/4
FP2_YYY_norm(&ff);
FP8_YYY_frob(&(w->a),&ff);
FP8_YYY_frob(&(w->b),&ff);
FP8_YYY_qmul(&(w->b),&(w->b),f); // times (1+i)^(p-3)/8
FP8_YYY_times_i(&(w->b)); // (i+1)^(p-1)/8
}
/* Set r=a^b mod m */
void FP16_YYY_pow(FP16_YYY *r,FP16_YYY * a,BIG_XXX b)
{
FP16_YYY w;
BIG_XXX z,zilch;
int bt;
BIG_XXX_zero(zilch);
BIG_XXX_copy(z,b);
FP16_YYY_copy(&w,a);
FP16_YYY_one(r);
BIG_XXX_norm(z);
while(1)
{
bt=BIG_XXX_parity(z);
BIG_XXX_shr(z,1);
if (bt) FP16_YYY_mul(r,r,&w);
if (BIG_XXX_comp(z,zilch)==0) break;
FP16_YYY_sqr(&w,&w);
}
FP16_YYY_reduce(r);
}
/* Move b to a if d=1 */
void FP16_YYY_cmove(FP16_YYY *f,FP16_YYY *g,int d)
{
FP8_YYY_cmove(&(f->a),&(g->a),d);
FP8_YYY_cmove(&(f->b),&(g->b),d);
}
#if CURVE_SECURITY_ZZZ == 256
/* XTR xtr_a function */
void FP16_YYY_xtr_A(FP16_YYY *r,FP16_YYY *w,FP16_YYY *x,FP16_YYY *y,FP16_YYY *z)
{
FP16_YYY t1,t2;
FP16_YYY_copy(r,x);
FP16_YYY_sub(&t1,w,y);
FP16_YYY_norm(&t1);
FP16_YYY_pmul(&t1,&t1,&(r->a));
FP16_YYY_add(&t2,w,y);
FP16_YYY_norm(&t2);
FP16_YYY_pmul(&t2,&t2,&(r->b));
FP16_YYY_times_i(&t2);
FP16_YYY_add(r,&t1,&t2);
FP16_YYY_add(r,r,z);
FP16_YYY_reduce(r);
}
/* XTR xtr_d function */
void FP16_YYY_xtr_D(FP16_YYY *r,FP16_YYY *x)
{
FP16_YYY w;
FP16_YYY_copy(r,x);
FP16_YYY_conj(&w,r);
FP16_YYY_add(&w,&w,&w);
FP16_YYY_sqr(r,r);
FP16_YYY_norm(&w);
FP16_YYY_sub(r,r,&w);
FP16_YYY_reduce(r); /* reduce here as multiple calls trigger automatic reductions */
}
/* r=x^n using XTR method on traces of FP12s */
void FP16_YYY_xtr_pow(FP16_YYY *r,FP16_YYY *x,BIG_XXX n)
{
int i,par,nb;
BIG_XXX v;
FP2_YYY w2;
FP4_YYY w4;
FP8_YYY w8;
FP16_YYY t,a,b,c,sf;
BIG_XXX_zero(v);
BIG_XXX_inc(v,3);
BIG_XXX_norm(v);
FP2_YYY_from_BIG(&w2,v);
FP4_YYY_from_FP2(&w4,&w2);
FP8_YYY_from_FP4(&w8,&w4);
FP16_YYY_from_FP8(&a,&w8);
FP16_YYY_copy(&sf,x);
FP16_YYY_norm(&sf);
FP16_YYY_copy(&b,&sf);
FP16_YYY_xtr_D(&c,&sf);
par=BIG_XXX_parity(n);
BIG_XXX_copy(v,n);
BIG_XXX_norm(v);
BIG_XXX_shr(v,1);
if (par==0)
{
BIG_XXX_dec(v,1);
BIG_XXX_norm(v);
}
nb=BIG_XXX_nbits(v);
for (i=nb-1; i>=0; i--)
{
if (!BIG_XXX_bit(v,i))
{
FP16_YYY_copy(&t,&b);
FP16_YYY_conj(&sf,&sf);
FP16_YYY_conj(&c,&c);
FP16_YYY_xtr_A(&b,&a,&b,&sf,&c);
FP16_YYY_conj(&sf,&sf);
FP16_YYY_xtr_D(&c,&t);
FP16_YYY_xtr_D(&a,&a);
}
else
{
FP16_YYY_conj(&t,&a);
FP16_YYY_xtr_D(&a,&b);
FP16_YYY_xtr_A(&b,&c,&b,&sf,&t);
FP16_YYY_xtr_D(&c,&c);
}
}
if (par==0) FP16_YYY_copy(r,&c);
else FP16_YYY_copy(r,&b);
FP16_YYY_reduce(r);
}
/* r=ck^a.cl^n using XTR double exponentiation method on traces of FP12s. See Stam thesis. */
void FP16_YYY_xtr_pow2(FP16_YYY *r,FP16_YYY *ck,FP16_YYY *cl,FP16_YYY *ckml,FP16_YYY *ckm2l,BIG_XXX a,BIG_XXX b)
{
int i,f2;
BIG_XXX d,e,w;
FP16_YYY t,cu,cv,cumv,cum2v;
BIG_XXX_copy(e,a);
BIG_XXX_copy(d,b);
BIG_XXX_norm(d);
BIG_XXX_norm(e);
FP16_YYY_copy(&cu,ck);
FP16_YYY_copy(&cv,cl);
FP16_YYY_copy(&cumv,ckml);
FP16_YYY_copy(&cum2v,ckm2l);
f2=0;
while (BIG_XXX_parity(d)==0 && BIG_XXX_parity(e)==0)
{
BIG_XXX_shr(d,1);
BIG_XXX_shr(e,1);
f2++;
}
while (BIG_XXX_comp(d,e)!=0)
{
if (BIG_XXX_comp(d,e)>0)
{
BIG_XXX_imul(w,e,4);
BIG_XXX_norm(w);
if (BIG_XXX_comp(d,w)<=0)
{
BIG_XXX_copy(w,d);
BIG_XXX_copy(d,e);
BIG_XXX_sub(e,w,e);
BIG_XXX_norm(e);
FP16_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v);
FP16_YYY_conj(&cum2v,&cumv);
FP16_YYY_copy(&cumv,&cv);
FP16_YYY_copy(&cv,&cu);
FP16_YYY_copy(&cu,&t);
}
else if (BIG_XXX_parity(d)==0)
{
BIG_XXX_shr(d,1);
FP16_YYY_conj(r,&cum2v);
FP16_YYY_xtr_A(&t,&cu,&cumv,&cv,r);
FP16_YYY_xtr_D(&cum2v,&cumv);
FP16_YYY_copy(&cumv,&t);
FP16_YYY_xtr_D(&cu,&cu);
}
else if (BIG_XXX_parity(e)==1)
{
BIG_XXX_sub(d,d,e);
BIG_XXX_norm(d);
BIG_XXX_shr(d,1);
FP16_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v);
FP16_YYY_xtr_D(&cu,&cu);
FP16_YYY_xtr_D(&cum2v,&cv);
FP16_YYY_conj(&cum2v,&cum2v);
FP16_YYY_copy(&cv,&t);
}
else
{
BIG_XXX_copy(w,d);
BIG_XXX_copy(d,e);
BIG_XXX_shr(d,1);
BIG_XXX_copy(e,w);
FP16_YYY_xtr_D(&t,&cumv);
FP16_YYY_conj(&cumv,&cum2v);
FP16_YYY_conj(&cum2v,&t);
FP16_YYY_xtr_D(&t,&cv);
FP16_YYY_copy(&cv,&cu);
FP16_YYY_copy(&cu,&t);
}
}
if (BIG_XXX_comp(d,e)<0)
{
BIG_XXX_imul(w,d,4);
BIG_XXX_norm(w);
if (BIG_XXX_comp(e,w)<=0)
{
BIG_XXX_sub(e,e,d);
BIG_XXX_norm(e);
FP16_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v);
FP16_YYY_copy(&cum2v,&cumv);
FP16_YYY_copy(&cumv,&cu);
FP16_YYY_copy(&cu,&t);
}
else if (BIG_XXX_parity(e)==0)
{
BIG_XXX_copy(w,d);
BIG_XXX_copy(d,e);
BIG_XXX_shr(d,1);
BIG_XXX_copy(e,w);
FP16_YYY_xtr_D(&t,&cumv);
FP16_YYY_conj(&cumv,&cum2v);
FP16_YYY_conj(&cum2v,&t);
FP16_YYY_xtr_D(&t,&cv);
FP16_YYY_copy(&cv,&cu);
FP16_YYY_copy(&cu,&t);
}
else if (BIG_XXX_parity(d)==1)
{
BIG_XXX_copy(w,e);
BIG_XXX_copy(e,d);
BIG_XXX_sub(w,w,d);
BIG_XXX_norm(w);
BIG_XXX_copy(d,w);
BIG_XXX_shr(d,1);
FP16_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v);
FP16_YYY_conj(&cumv,&cumv);
FP16_YYY_xtr_D(&cum2v,&cu);
FP16_YYY_conj(&cum2v,&cum2v);
FP16_YYY_xtr_D(&cu,&cv);
FP16_YYY_copy(&cv,&t);
}
else
{
BIG_XXX_shr(d,1);
FP16_YYY_conj(r,&cum2v);
FP16_YYY_xtr_A(&t,&cu,&cumv,&cv,r);
FP16_YYY_xtr_D(&cum2v,&cumv);
FP16_YYY_copy(&cumv,&t);
FP16_YYY_xtr_D(&cu,&cu);
}
}
}
FP16_YYY_xtr_A(r,&cu,&cv,&cumv,&cum2v);
for (i=0; i<f2; i++) FP16_YYY_xtr_D(r,r);
FP16_YYY_xtr_pow(r,r,d);
}
#endif