http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/ecp2.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/ecp2.rs b/version22/rust/src/ecp2.rs new file mode 100644 index 0000000..cee55a6 --- /dev/null +++ b/version22/rust/src/ecp2.rs @@ -0,0 +1,677 @@ +/* +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. +*/ + +use std::fmt; +use std::str::SplitWhitespace; + +#[derive(Copy, Clone)] +pub struct ECP2 { + x:FP2, + y:FP2, + z:FP2, + inf: bool +} + + +use rom; +use rom::BIG_HEX_STRING_LEN; +//mod fp2; +use fp2::FP2; +//mod fp; +//use fp::FP; +//mod big; +use big::BIG; +//mod dbig; +//use dbig::DBIG; +//mod rand; +//mod hash256; +//mod rom; + +impl fmt::Display for ECP2 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "ECP2: [ {}, {}, {}, {} ]", self.inf, self.x, self.y, self.z) + } +} + +impl fmt::Debug for ECP2 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "ECP2: [ {}, {}, {}, {} ]", self.inf, self.x, self.y, self.z) + } +} + +impl PartialEq for ECP2 { + fn eq(&self, other: &ECP2) -> bool { + return (self.inf == other.inf) && + (self.x == other.x) && + (self.y == other.y) && + (self.z == other.z); + } +} + +#[allow(non_snake_case)] +impl ECP2 { + + pub fn new() -> ECP2 { + ECP2 { + x: FP2::new(), + y: FP2::new(), + z: FP2::new(), + inf: true + } + } +#[allow(non_snake_case)] +/* construct this from (x,y) - but set to O if not on curve */ + pub fn new_fp2s(ix:&FP2,iy:&FP2) -> ECP2 { + let mut E=ECP2::new(); + E.x.copy(&ix); + E.y.copy(&iy); + E.z.one(); + + let mut rhs=ECP2::rhs(&mut E.x); + let mut y2=FP2::new_copy(&E.y); + y2.sqr(); + if y2.equals(&mut rhs) { + E.inf=false; + } else {E.x.zero();E.inf=true} + return E; +} + +/* construct this from x - but set to O if not on curve */ + pub fn new_fp2(ix:&FP2) -> ECP2 { + let mut E=ECP2::new(); + E.x.copy(&ix); + E.y.one(); + E.z.one(); + + let mut rhs=ECP2::rhs(&mut E.x); + if rhs.sqrt() { + E.y.copy(&rhs); + E.inf=false; + } else {E.x.zero();E.inf=true} + return E; + } + +/* Test this=O? */ + pub fn is_infinity(&mut self) -> bool { + return self.inf; + } + +/* copy self=P */ + pub fn copy(&mut self,P: &ECP2) { + self.x.copy(&P.x); + self.y.copy(&P.y); + self.z.copy(&P.z); + self.inf=P.inf; + } + +/* set self=O */ + pub fn inf(&mut self) { + self.inf=true; + self.x.zero(); + self.y.zero(); + self.z.zero(); + } + +/* set self=-self */ + pub fn neg(&mut self) { + if self.is_infinity() {return} + self.y.neg(); self.y.reduce(); + } + +/* Conditional move of Q to self dependant on d */ + pub fn cmove(&mut self,Q: &ECP2,d: isize) { + self.x.cmove(&Q.x,d); + self.y.cmove(&Q.y,d); + self.z.cmove(&Q.z,d); + + let bd:bool; + if d==0 {bd=false} + else {bd=true} + + self.inf=self.inf!=(self.inf!=Q.inf)&&bd; + } + +/* return 1 if b==c, no branching */ + fn teq(b: i32,c: i32) -> isize { + let mut x=b^c; + x-=1; // if x=0, x now -1 + return ((x>>31)&1) as isize; + } + +/* Constant time select from pre-computed table */ + pub fn selector(&mut self,W: &[ECP2],b: i32) { + let mut MP=ECP2::new(); + let m=b>>31; + let mut babs=(b^m)-m; + + babs=(babs-1)/2; + + self.cmove(&W[0],ECP2::teq(babs,0)); // conditional move + self.cmove(&W[1],ECP2::teq(babs,1)); + self.cmove(&W[2],ECP2::teq(babs,2)); + self.cmove(&W[3],ECP2::teq(babs,3)); + self.cmove(&W[4],ECP2::teq(babs,4)); + self.cmove(&W[5],ECP2::teq(babs,5)); + self.cmove(&W[6],ECP2::teq(babs,6)); + self.cmove(&W[7],ECP2::teq(babs,7)); + + MP.copy(self); + MP.neg(); + self.cmove(&MP,(m&1) as isize); + } + +/* Test if P == Q */ + pub fn equals(&mut self,Q :&mut ECP2) -> bool { + if self.is_infinity() && Q.is_infinity() {return true} + if self.is_infinity() || Q.is_infinity() {return false} + + let mut zs2=FP2::new_copy(&self.z); zs2.sqr(); + let mut zo2=FP2::new_copy(&Q.z); zo2.sqr(); + let mut zs3=FP2::new_copy(&zs2); zs3.mul(&mut self.z); + let mut zo3=FP2::new_copy(&zo2); zo3.mul(&mut Q.z); + zs2.mul(&mut Q.x); + zo2.mul(&mut self.x); + if !zs2.equals(&mut zo2) {return false} + zs3.mul(&mut Q.y); + zo3.mul(&mut self.y); + if !zs3.equals(&mut zo3) {return false} + + return true; + } + +/* set to Affine - (x,y,z) to (x,y) */ + pub fn affine(&mut self) { + if self.is_infinity() {return} + let mut one=FP2::new_int(1); + if self.z.equals(&mut one) {return} + self.z.inverse(); + + let mut z2=FP2::new_copy(&self.z); + z2.sqr(); + self.x.mul(&mut z2); self.x.reduce(); + self.y.mul(&mut z2); + self.y.mul(&mut self.z); self.y.reduce(); + self.z.copy(&one); + } + +/* extract affine x as FP2 */ + pub fn getx(&mut self) -> FP2 { + self.affine(); + return FP2::new_copy(&self.x); + } + +/* extract affine y as FP2 */ + pub fn gety(&mut self) -> FP2 { + self.affine(); + return FP2::new_copy(&self.y); + } + +/* extract projective x */ + pub fn getpx(&mut self) -> FP2 { + return FP2::new_copy(&self.x); + } +/* extract projective y */ + pub fn getpy(&mut self) -> FP2 { + return FP2::new_copy(&self.y); + } +/* extract projective z */ + pub fn getpz(&mut self) -> FP2 { + return FP2::new_copy(&self.z); + } + +/* convert to byte array */ + pub fn tobytes(&mut self,b: &mut [u8]) { + let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + let mb=rom::MODBYTES as usize; + + self.affine(); + self.x.geta().tobytes(&mut t); + for i in 0..mb { b[i]=t[i]} + self.x.getb().tobytes(&mut t); + for i in 0..mb { b[i+mb]=t[i]} + + self.y.geta().tobytes(&mut t); + for i in 0..mb {b[i+2*mb]=t[i]} + self.y.getb().tobytes(&mut t); + for i in 0..mb {b[i+3*mb]=t[i]} + } + +/* convert from byte array to point */ + pub fn frombytes(b: &[u8]) -> ECP2 { + let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + let mb=rom::MODBYTES as usize; + + for i in 0..mb {t[i]=b[i]} + let mut ra=BIG::frombytes(&t); + for i in 0..mb {t[i]=b[i+mb]} + let mut rb=BIG::frombytes(&t); + let rx=FP2::new_bigs(&ra,&rb); + + for i in 0..mb {t[i]=b[i+2*mb]} + ra.copy(&BIG::frombytes(&t)); + for i in 0..mb {t[i]=b[i+3*mb]} + rb.copy(&BIG::frombytes(&t)); + let ry=FP2::new_bigs(&ra,&rb); + + return ECP2::new_fp2s(&rx,&ry); + } + +/* convert this to hex string */ + pub fn tostring(&mut self) -> String { + if self.is_infinity() {return String::from("infinity")} + self.affine(); + return format!("({},{})",self.x.tostring(),self.y.tostring()); +} + + pub fn to_hex(&self) -> String { + let mut ret: String = String::with_capacity(7 * BIG_HEX_STRING_LEN); + ret.push_str(&format!("{} {} {} {}", self.inf, self.x.to_hex(), self.y.to_hex(), self.z.to_hex())); + return ret; + } + + pub fn from_hex_iter(iter: &mut SplitWhitespace) -> ECP2 { + let mut ret:ECP2 = ECP2::new(); + if let Some(x) = iter.next() { + ret.inf = x == "true"; + ret.x = FP2::from_hex_iter(iter); + ret.y = FP2::from_hex_iter(iter); + ret.z = FP2::from_hex_iter(iter); + } + return ret; + } + + pub fn from_hex(val: String) -> ECP2 { + let mut iter = val.split_whitespace(); + return ECP2::from_hex_iter(&mut iter); + } + +/* Calculate RHS of twisted curve equation x^3+B/i */ + pub fn rhs(x:&mut FP2) -> FP2 { + x.norm(); + let mut r=FP2::new_copy(x); + r.sqr(); + let mut b=FP2::new_big(&BIG::new_ints(&rom::CURVE_B)); + b.div_ip(); + r.mul(x); + r.add(&b); + + r.reduce(); + return r; + } + +/* self+=self */ + pub fn dbl(&mut self) -> isize { + if self.inf {return -1} + if self.y.iszilch() { + self.inf(); + return -1 + } + + let mut w1=FP2::new_copy(&self.x); + let mut w2=FP2::new(); + let mut w3=FP2::new_copy(&self.x); + let mut w8=FP2::new_copy(&self.x); + + w1.sqr(); + w8.copy(&w1); + w8.imul(3); + + w2.copy(&self.y); w2.sqr(); + w3.copy(&self.x); w3.mul(&mut w2); + w3.imul(4); + w1.copy(&w3); w1.neg(); + w1.norm(); + + self.x.copy(&w8); self.x.sqr(); + self.x.add(&w1); + self.x.add(&w1); + self.x.norm(); + + self.z.mul(&mut self.y); + self.z.dbl(); + + w2.dbl(); + w2.sqr(); + w2.dbl(); + w3.sub(&self.x); + self.y.copy(&w8); self.y.mul(&mut w3); + w2.norm(); + self.y.sub(&w2); + + self.y.norm(); + self.z.norm(); + + return 1; + } + +/* self+=Q - return 0 for add, 1 for double, -1 for O */ + pub fn add(&mut self,Q:&mut ECP2) -> isize { + if self.inf { + self.copy(Q); + return -1; + } + if Q.inf {return -1} + + let mut aff=false; + + if Q.z.isunity() {aff=true} + + let mut a=FP2::new(); + let mut c=FP2::new(); + let mut b=FP2::new_copy(&self.z); + let mut d=FP2::new_copy(&self.z); + + if !aff { + a.copy(&Q.z); + c.copy(&Q.z); + + a.sqr(); b.sqr(); + c.mul(&mut a); d.mul(&mut b); + + a.mul(&mut self.x); + c.mul(&mut self.y); + } else { + a.copy(&self.x); + c.copy(&self.y); + + b.sqr(); + d.mul(&mut b); + } + + b.mul(&mut Q.x); b.sub(&a); + d.mul(&mut Q.y); d.sub(&c); + + if b.iszilch() { + if d.iszilch() { + self.dbl(); + return 1; + } else { + self.inf=true; + return -1; + } + } + + if !aff {self.z.mul(&mut Q.z)} + self.z.mul(&mut b); + + let mut e=FP2::new_copy(&b); e.sqr(); + b.mul(&mut e); + a.mul(&mut e); + + e.copy(&a); + e.add(&a); e.add(&b); + self.x.copy(&d); self.x.sqr(); self.x.sub(&e); + + a.sub(&self.x); + self.y.copy(&a); self.y.mul(&mut d); + c.mul(&mut b); self.y.sub(&c); + + self.x.norm(); + self.y.norm(); + self.z.norm(); + + return 0; + } + +/* set this-=Q */ + pub fn sub(&mut self,Q :&mut ECP2) -> isize { + Q.neg(); + let d=self.add(Q); + Q.neg(); + return d; + } + +/* set this*=q, where q is Modulus, using Frobenius */ + pub fn frob(&mut self,x:&mut FP2) { + if self.inf {return} + let mut x2=FP2::new_copy(x); + x2.sqr(); + self.x.conj(); + self.y.conj(); + self.z.conj(); + self.z.reduce(); + self.x.mul(&mut x2); + self.y.mul(&mut x2); + self.y.mul(x); + } + +/* normalises m-array of ECP2 points. Requires work vector of m FP2s */ + + pub fn multiaffine(P: &mut [ECP2]) { + let mut t1=FP2::new(); + let mut t2=FP2::new(); + + let mut work:[FP2;8]=[FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new()]; + let m=8; + + work[0].one(); + work[1].copy(&P[0].z); + + for i in 2..m { + t1.copy(&work[i-1]); + work[i].copy(&t1); + work[i].mul(&mut P[i-1].z) + } + + t1.copy(&work[m-1]); + t1.mul(&mut P[m-1].z); + t1.inverse(); + t2.copy(&P[m-1].z); + work[m-1].mul(&mut t1); + + let mut i=m-2; + + loop { + if i==0 { + work[0].copy(&t1); + work[0].mul(&mut t2); + break; + } + work[i].mul(&mut t2); + work[i].mul(&mut t1); + t2.mul(&mut P[i].z); + i-=1; + } +/* now work[] contains inverses of all Z coordinates */ + + for i in 0..m { + P[i].z.one(); + t1.copy(&work[i]); t1.sqr(); + P[i].x.mul(&mut t1); + t1.mul(&mut work[i]); + P[i].y.mul(&mut t1); + } + } + +/* self*=e */ + pub fn mul(&mut self,e: &BIG) -> ECP2 { +/* fixed size windows */ + let mut mt=BIG::new(); + let mut t=BIG::new(); + let mut P=ECP2::new(); + let mut Q=ECP2::new(); + let mut C=ECP2::new(); + + if self.is_infinity() {return P} + + let mut W:[ECP2;8]=[ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new()]; + + const CT:usize=1+(rom::NLEN*(rom::BASEBITS as usize)+3)/4; + let mut w:[i8;CT]=[0;CT]; + + self.affine(); + +/* precompute table */ + Q.copy(&self); + Q.dbl(); + + W[0].copy(&self); + + for i in 1..8 { + C.copy(&W[i-1]); + W[i].copy(&C); + W[i].add(&mut Q); + } + +/* convert the table to affine */ + + ECP2::multiaffine(&mut W); + +/* make exponent odd - add 2P if even, P if odd */ + t.copy(&e); + let s=t.parity(); + t.inc(1); t.norm(); let ns=t.parity(); mt.copy(&t); mt.inc(1); mt.norm(); + t.cmove(&mt,s); + Q.cmove(&self,ns); + C.copy(&Q); + + let nb=1+(t.nbits()+3)/4; + +/* convert exponent to signed 4-bit window */ + for i in 0..nb { + w[i]=(t.lastbits(5)-16) as i8; + t.dec(w[i] as isize); t.norm(); + t.fshr(4); + } + w[nb]=(t.lastbits(5)) as i8; + + P.copy(&W[((w[nb] as usize) -1)/2]); + for i in (0..nb).rev() { + Q.selector(&W,w[i] as i32); + P.dbl(); + P.dbl(); + P.dbl(); + P.dbl(); + P.add(&mut Q); + } + P.sub(&mut C); + P.affine(); + return P; + } + +/* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */ + pub fn mul4(Q: &mut [ECP2],u: &[BIG]) -> ECP2 { + let mut a:[i8;4]=[0;4]; + let mut T=ECP2::new(); + let mut C=ECP2::new(); + let mut P=ECP2::new(); + + let mut W:[ECP2;8]=[ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new()]; + + let mut mt=BIG::new(); + + let mut t:[BIG;4]=[BIG::new_copy(&u[0]),BIG::new_copy(&u[1]),BIG::new_copy(&u[2]),BIG::new_copy(&u[3])]; + + const CT:usize=1+rom::NLEN*(rom::BASEBITS as usize); + let mut w:[i8;CT]=[0;CT]; + + for i in 0..4 { + Q[i].affine(); + } + +/* precompute table */ + + W[0].copy(&Q[0]); W[0].sub(&mut Q[1]); + C.copy(&W[0]); W[1].copy(&C); + W[2].copy(&C); + W[3].copy(&C); + W[4].copy(&Q[0]); W[4].add(&mut Q[1]); + C.copy(&W[4]); W[5].copy(&C); + W[6].copy(&C); + W[7].copy(&C); + + T.copy(&Q[2]); T.sub(&mut Q[3]); + W[1].sub(&mut T); + W[2].add(&mut T); + W[5].sub(&mut T); + W[6].add(&mut T); + T.copy(&Q[2]); T.add(&mut Q[3]); + W[0].sub(&mut T); + W[3].add(&mut T); + W[4].sub(&mut T); + W[7].add(&mut T); + + ECP2::multiaffine(&mut W); + +/* if multiplier is even add 1 to multiplier, and add P to correction */ + mt.zero(); C.inf(); + for i in 0..4 { + if t[i].parity()==0 { + t[i].inc(1); t[i].norm(); + C.add(&mut Q[i]); + } + mt.add(&t[i]); mt.norm(); + } + + let nb=1+mt.nbits(); + +/* convert exponent to signed 1-bit window */ + for j in 0..nb { + for i in 0..4 { + a[i]=(t[i].lastbits(2)-2) as i8; + t[i].dec(a[i] as isize); t[i].norm(); + t[i].fshr(1); + } + w[j]=8*a[0]+4*a[1]+2*a[2]+a[3]; + } + w[nb]=(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2)) as i8; + + P.copy(&W[((w[nb] as usize)-1)/2]); + for i in (0..nb).rev() { + T.selector(&W,w[i] as i32); + P.dbl(); + P.add(&mut T); + } + P.sub(&mut C); /* apply correction */ + + P.affine(); + return P; + } + +} +/* +fn main() +{ + let mut r=BIG::new_ints(&rom::MODULUS); + + let pxa=BIG::new_ints(&rom::CURVE_PXA); + let pxb=BIG::new_ints(&rom::CURVE_PXB); + let pya=BIG::new_ints(&rom::CURVE_PYA); + let pyb=BIG::new_ints(&rom::CURVE_PYB); + + let fra=BIG::new_ints(&rom::CURVE_FRA); + let frb=BIG::new_ints(&rom::CURVE_FRB); + + let mut f=FP2::new_bigs(&fra,&frb); + + let px=FP2::new_bigs(&pxa,&pxb); + let py=FP2::new_bigs(&pya,&pyb); + + let mut P=ECP2::new_fp2s(&px,&py); + + println!("P= {}",P.tostring()); + + P=P.mul(&mut r); + println!("P= {}",P.tostring()); + + let mut Q=ECP2::new_fp2s(&px,&py); + Q.frob(&mut f); + println!("Q= {}",Q.tostring()); +} +*/
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/ff.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/ff.rs b/version22/rust/src/ff.rs new file mode 100644 index 0000000..d59525f --- /dev/null +++ b/version22/rust/src/ff.rs @@ -0,0 +1,944 @@ +/* +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 +if debug {println!("sf2= {}",self.tostring())} + 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. +*/ + +//#[derive(Copy, Clone)] +pub struct FF { + v:Vec<BIG>, + length:usize +} + +//mod big; +use big::BIG; +//mod dbig; +//use dbig::DBIG; +//mod rom; +use rom; +use rom::Chunk; +//mod rand; +use rand::RAND; +//mod hash256; +//use std::process; + + +//static mut debug:bool=false; + +impl FF { + +/* Constructors */ + pub fn new_int(n:usize) -> FF { + let mut f=FF{v:Vec::new(),length:0}; + for _ in 0..n { + f.v.push(BIG::new()); + } + f.length=n; + return f; + } +/* + pub fn new_ints(x: &[&[i32];rom::NLEN],n: usize) -> FF { + let mut f=FF{v:Vec::new(),length:0}; + for i in 0..n { + f.v.push(BIG::new_ints(x[i])); + } + f.length=n; + return f; + } +*/ + pub fn zero(&mut self) { + for i in 0..self.length { + self.v[i].zero(); + } + } + + pub fn getlen(&self) -> usize { + return self.length; + } + +/* set to integer */ + pub fn set(&mut self,m:isize) { + self.zero(); + self.v[0].set(0,m as Chunk); + } + +/* copy from FF b */ + pub fn copy(&mut self,b: &FF) { + for i in 0..self.length { + self.v[i].copy(&b.v[i]); + } + } + +/* x=y<<n */ + pub fn dsucopy(&mut self,b: &FF) { + for i in 0..b.length { + self.v[b.length+i].copy(&b.v[i]); + self.v[i].zero(); + } + } + +/* x=y */ + pub fn dscopy(&mut self,b: &FF) { + for i in 0..b.length { + self.v[i].copy(&b.v[i]); + self.v[b.length+i].zero(); + } + } + +/* x=y>>n */ + pub fn sducopy(&mut self,b: &FF) { + for i in 0..self.length { + self.v[i].copy(&b.v[self.length+i]); + } + } + + pub fn one(&mut self) { + self.v[0].one(); + for i in 1..self.length { + self.v[i].zero(); + } + } + +/* test equals 0 */ + pub fn iszilch(&mut self) -> bool { + for i in 0..self.length { + if !self.v[i].iszilch() {return false} + } + return true; + } + +/* shift right by BIGBITS-bit words */ + pub fn shrw(&mut self,n: usize) { + let mut t= BIG::new(); + for i in 0..n { + t.copy(&self.v[i+n]); + self.v[i].copy(&t); + self.v[i+n].zero(); + } + } + +/* shift left by BIGBITS-bit words */ + pub fn shlw(&mut self,n: usize) { + let mut t= BIG::new(); + for i in 0..n { + t.copy(&self.v[i]); + self.v[n+i].copy(&t); + self.v[i].zero(); + } + } + +/* extract last bit */ + pub fn parity(&self) -> isize { + return self.v[0].parity(); + } + + pub fn lastbits(&mut self,m: usize) -> isize { + return self.v[0].lastbits(m); + } + +/* compare x and y - must be normalised, and of same length */ + pub fn comp(a: &FF,b: &FF) -> isize { + let mut i=a.length-1; + + loop { + let j=BIG::comp(&a.v[i],&b.v[i]); + if j!=0 {return j} + if i==0 {break;} + i-=1; + } + return 0; + } + +/* recursive add */ + pub fn radd(&mut self,vp: usize,x: &FF,xp: usize,y: &FF,yp: usize,n: usize) { + for i in 0..n { + self.v[vp+i].copy(&x.v[xp+i]); + self.v[vp+i].add(&y.v[yp+i]); + } + } + +/* recursive inc */ + pub fn rinc(&mut self,vp: usize,y: &FF,yp: usize,n: usize) { + for i in 0..n { + self.v[vp+i].add(&y.v[yp+i]); + } + } + + pub fn rsinc(&mut self,n: usize) { + let mut t=BIG::new(); + for i in 0..n { + t.copy(&self.v[i]); + self.v[n+i].add(&t); + } + } + +/* recursive sub */ + pub fn rsub(&mut self,vp: usize,x: &FF,xp: usize,y: &FF,yp: usize,n: usize) { + for i in 0..n { + self.v[vp+i].copy(&x.v[xp+i]); + self.v[vp+i].sub(&y.v[yp+i]); + } + } + +/* recursive dec */ + pub fn rdec(&mut self,vp: usize,y: &FF,yp: usize,n: usize) { + for i in 0..n { + self.v[vp+i].sub(&y.v[yp+i]); + } + } + +/* simple add */ + pub fn add(&mut self,b: &FF) { + for i in 0..self.length { + self.v[i].add(&b.v[i]); + } + } + +/* simple sub */ + pub fn sub(&mut self,b: &FF) { + for i in 0..self.length { + self.v[i].sub(&b.v[i]); + } + } + +/* reverse sub */ + pub fn revsub(&mut self,b: &FF) { + for i in 0..self.length { + self.v[i].rsub(&b.v[i]); + } + } + +/* normalise - but hold any overflow in top part unless n<0 */ + pub fn rnorm(&mut self,vp: usize,n: isize) { + let mut trunc=false; + let mut carry:Chunk; + let mut nn:usize=n as usize; + if n<0 { /* -v n signals to do truncation */ + nn=(-n) as usize; + trunc=true; + } + for i in 0..nn-1 { + carry=self.v[vp+i].norm(); + self.v[vp+i].xortop(carry<<rom::P_TBITS); + self.v[vp+i+1].w[0]+=carry; //incl(carry); + } + carry=self.v[vp+nn-1].norm(); + if trunc { + self.v[vp+nn-1].xortop(carry<<rom::P_TBITS); + } + } + + pub fn norm(&mut self) { + let n:isize=self.length as isize; + self.rnorm(0,n); + } + +/* increment/decrement by a small integer */ + pub fn inc(&mut self,m: isize) { + self.v[0].inc(m); + self.norm(); + } + + pub fn dec(&mut self,m: isize) { + self.v[0].dec(m); + self.norm(); + } + +/* shift left by one bit */ + pub fn shl(&mut self) { + let mut delay_carry:isize=0; + for i in 0..self.length-1 { + let carry=self.v[i].fshl(1); + self.v[i].inc(delay_carry); + self.v[i].xortop((carry as Chunk)<<rom::P_TBITS); + delay_carry=carry; + } + self.v[self.length-1].fshl(1); + self.v[self.length-1].inc(delay_carry); + } + +/* shift right by one bit */ + + pub fn shr(&mut self) { + let mut i=self.length-1; + while i>0 { + let carry=self.v[i].fshr(1); + self.v[i-1].xortop((carry as Chunk)<<rom::P_TBITS); + i-=1; + } + self.v[0].fshr(1); + } + +/* Convert to Hex String */ + pub fn tostring(&mut self) -> String { + self.norm(); + let mut s = String::new(); + let mut i:usize=self.length-1; + loop { + s=s+self.v[i].tostring().as_ref(); + if i==0 {break} + i-=1; + } + return s; + } + +/* Convert to Hex String + pub fn tostr(&mut self,n:usize) -> String { + let mut t=FF::new_int(n); + for i in 0..n { + t.v[i].copy(&self.v[i]); + } + t.norm(); + let mut s = String::new(); + let mut i:usize=t.length-1; + loop { + s=s+t.v[i].tostring().as_ref(); + if i==0 {break} + i-=1; + } + return s; + }*/ + +/* Convert FFs to/from byte arrays */ + pub fn tobytes(&mut self,b: &mut [u8]) { + for i in 0..self.length { + self.v[i].tobytearray(b,(self.length-i-1)*(rom::MODBYTES as usize)) + } + } + + pub fn frombytes(x: &mut FF,b: &[u8]) { + for i in 0..x.length { + x.v[i]=BIG::frombytearray(b,(x.length-i-1)*(rom::MODBYTES as usize)) + } + } + +/* in-place swapping using xor - side channel resistant - lengths must be the same */ + pub fn cswap(a: &mut FF,b: &mut FF,d: isize) { + for i in 0..a.length { + a.v[i].cswap(&mut b.v[i],d); + } + } + +/* z=x*y, t is workspace */ + fn karmul(&mut self,vp: usize,x: &FF,xp: usize,y: &FF,yp: usize,t: *mut FF,tp: usize,n: usize) { + if n==1 { + let mut d=BIG::mul(&x.v[xp],&y.v[yp]); + self.v[vp+1]=d.split(8*rom::MODBYTES); + self.v[vp].dcopy(&d); + return; + } + let nd2=n/2; + self.radd(vp,x,xp,x,xp+nd2,nd2); + self.rnorm(vp,nd2 as isize); /* Important - required for 32-bit build */ + self.radd(vp+nd2,y,yp,y,yp+nd2,nd2); + self.rnorm(vp+nd2,nd2 as isize); /* Important - required for 32-bit build */ + unsafe{ + (*t).karmul(tp,self,vp,self,vp+nd2,t,tp+n,nd2); + } + self.karmul(vp,x,xp,y,yp,t,tp+n,nd2); + self.karmul(vp+n,x,xp+nd2,y,yp+nd2,t,tp+n,nd2); + unsafe { + (*t).rdec(tp,self,vp,n); + (*t).rdec(tp,self,vp+n,n); + self.rinc(vp+nd2,&(*t),tp,n); + } + self.rnorm(vp,(2*n) as isize); + } + + fn karsqr(&mut self,vp: usize,x: &FF,xp: usize,t: *mut FF,tp: usize,n: usize) { + if n==1 { + let mut d=BIG::sqr(&x.v[xp]); + self.v[vp+1].copy(&d.split(8*rom::MODBYTES)); + self.v[vp].dcopy(&d); + return; + } + + let nd2=n/2; + self.karsqr(vp,x,xp,t,tp+n,nd2); + self.karsqr(vp+n,x,xp+nd2,t,tp+n,nd2); + unsafe { + (*t).karmul(tp,x,xp,x,xp+nd2,t,tp+n,nd2); + self.rinc(vp+nd2,&(*t),tp,n); + self.rinc(vp+nd2,&(*t),tp,n); + } + self.rnorm(vp+nd2,n as isize); + } + +/* Calculates Least Significant bottom half of x*y */ + fn karmul_lower(&mut self,vp: usize,x: &FF,xp: usize,y: &FF,yp: usize,t: *mut FF,tp: usize,n: usize) { + if n==1 { /* only calculate bottom half of product */ + self.v[vp].copy(&BIG::smul(&x.v[xp],&y.v[yp])); + return; + } + let nd2=n/2; + + self.karmul(vp,x,xp,y,yp,t,tp+n,nd2); + unsafe { + (*t).karmul_lower(tp,x,xp+nd2,y,yp,t,tp+n,nd2); + self.rinc(vp+nd2,&(*t),tp,nd2); + (*t).karmul_lower(tp,x,xp,y,yp+nd2,t,tp+n,nd2); + self.rinc(vp+nd2,&(*t),tp,nd2); + } + let sn:isize=nd2 as isize; + self.rnorm(vp+nd2,-sn); /* truncate it */ + } + +/* Calculates Most Significant upper half of x*y, given lower part */ + fn karmul_upper(&mut self,x: &FF,y: &FF,t: *mut FF,n: usize) { + let nd2=n/2; + self.radd(n,x,0,x,nd2,nd2); + self.radd(n+nd2,y,0,y,nd2,nd2); + self.rnorm(n,nd2 as isize); + self.rnorm(n+nd2,nd2 as isize); + + unsafe { + (*t).karmul(0,self,n+nd2,self,n,t,n,nd2); /* t = (a0+a1)(b0+b1) */ + + } + self.karmul(n,x,nd2,y,nd2,t,n,nd2); /* z[n]= a1*b1 */ + /* z[0-nd2]=l(a0b0) z[nd2-n]= h(a0b0)+l(t)-l(a0b0)-l(a1b1) */ + unsafe { + (*t).rdec(0,self,n,n); /* t=t-a1b1 */ + self.rsinc(nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ + self.rdec(nd2,&(*t),0,nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ + } + + let sn:isize=n as isize; + self.rnorm(0,-sn); /* a0b0 now in z - truncate it */ + unsafe { + (*t).rdec(0,self,0,n); /* (a0+a1)(b0+b1) - a0b0 */ + self.rinc(nd2,&(*t),0,n); + } + self.rnorm(nd2,sn); + } + +/* z=x*y. Assumes x and y are of same length. */ + pub fn mul(x: &FF,y: &FF) -> FF { + let n=x.length; + let mut z=FF::new_int(2*n); + let mut t=FF::new_int(2*n); + // x.norm(); y.norm(); + z.karmul(0,&x,0,&y,0,&mut t,0,n); + return z; + } + +/* return low part of product this*y */ + pub fn lmul(&mut self,y: &FF) { + let n=self.length; + let mut t=FF::new_int(2*n); + let mut x=FF::new_int(n); x.copy(&self); + // x.norm(); y.norm(); + self.karmul_lower(0,&x,0,&y,0,&mut t,0,n); + } + +/* Set b=b mod c */ + pub fn rmod(&mut self,m: &FF) { + let mut k=1; + let n=m.length; + let mut c=FF::new_int(n); c.copy(m); + + self.norm(); + if FF::comp(&self,&c)<0 {return} + + c.shl(); + while FF::comp(&self,&c)>=0 { + c.shl(); + k+=1; + } + + while k>0 { + c.shr(); + if FF::comp(&self,&c)>=0 { + self.sub(&c); + self.norm(); + } + k-=1; + } + } + +/* z=x^2 */ + pub fn sqr(x: &FF) -> FF { + let n=x.length; + let mut z=FF::new_int(2*n); + let mut t=FF::new_int(2*n); + // x.norm(); + z.karsqr(0,&x,0,&mut t,0,n); + return z; + } + +/* return This mod modulus, ms is modulus, md is Montgomery Constant */ + pub fn reduce(&mut self,ms: &FF,md: &FF) -> FF { /* fast karatsuba Montgomery reduction */ + let n=ms.length; + let mut t=FF::new_int(2*n); + let mut r=FF::new_int(n); + let mut m=FF::new_int(n); + + r.sducopy(&self); + m.karmul_lower(0,&self,0,&md,0,&mut t,0,n); + self.karmul_upper(&ms,&m,&mut t,n); + + m.sducopy(self); + r.add(&ms); + r.sub(&m); + r.norm(); + + return r; + } + +/* Set r=this mod b */ +/* this is of length - 2*n */ +/* r,b is of length - n */ + pub fn dmod(&mut self,b: &FF) -> FF { + let n=b.length; + let mut m=FF::new_int(2*n); + let mut x=FF::new_int(2*n); + let mut r=FF::new_int(n); + + x.copy(&self); + x.norm(); + m.dsucopy(&b); let mut k=rom::BIGBITS*n; + + while FF::comp(&x,&m)>=0 { + x.sub(&m); + x.norm(); + } + + while k>0 { + m.shr(); + + if FF::comp(&x,&m)>=0 { + x.sub(&m); + x.norm(); + } + k-=1; + } + + r.copy(&x); + r.rmod(b); + return r; + } + +/* Set return=1/this mod p. Binary method - a<p on entry */ + + pub fn invmodp(&mut self,p: &FF) { + let n=p.length; + + let mut u=FF::new_int(n); + let mut v=FF::new_int(n); + let mut x1=FF::new_int(n); + let mut x2=FF::new_int(n); + let mut t=FF::new_int(n); + let mut one=FF::new_int(n); + + one.one(); + u.copy(&self); + v.copy(&p); + x1.copy(&one); + x2.zero(); + + // reduce n in here as well! + while FF::comp(&u,&one)!=0 && FF::comp(&v,&one)!=0 { + while u.parity()==0 { + u.shr(); + if x1.parity()!=0 { + x1.add(&p); + x1.norm(); + } + x1.shr(); + } + while v.parity()==0 { + v.shr(); + if x2.parity()!=0 { + x2.add(&p); + x2.norm(); + } + x2.shr(); + } + if FF::comp(&u,&v)>=0 { + u.sub(&v); + u.norm(); + if FF::comp(&x1,&x2)>=0 { + x1.sub(&x2); + } else { + t.copy(&p); + t.sub(&x2); + x1.add(&t); + } + x1.norm(); + } else { + v.sub(&u); + v.norm(); + if FF::comp(&x2,&x1)>=0 { + x2.sub(&x1); + } else { + t.copy(&p); + t.sub(&x1); + x2.add(&t); + } + x2.norm(); + } + } + if FF::comp(&u,&one)==0 { + self.copy(&x1); + } else { + self.copy(&x2); + } + } + +/* nresidue mod m */ + pub fn nres(&mut self,m: &FF) { + let n=m.length; + let mut d=FF::new_int(2*n); + d.dsucopy(&self); + self.copy(&d.dmod(m)); + } + + pub fn redc(&mut self,m: &FF,md: &FF) { + let n=m.length; + let mut d=FF::new_int(2*n); + self.rmod(m); + d.dscopy(&self); + self.copy(&d.reduce(&m,&md)); + self.rmod(m); + } + + pub fn mod2m(&mut self,m: usize) { + for i in m..self.length { + self.v[i].zero() + } + } + +/* U=1/a mod 2^m - Arazi & Qi */ + pub fn invmod2m(&self) -> FF { + let n=self.length; + + let mut b=FF::new_int(n); + let mut c=FF::new_int(n); + let mut u=FF::new_int(n); + + u.zero(); + u.v[0].copy(&self.v[0]); + u.v[0].invmod2m(); + + let mut i=1; + while i<n { + b.copy(&self); b.mod2m(i); + let mut t=FF::mul(&u,&b); t.shrw(i); b.copy(&t); + c.copy(&self); c.shrw(i); c.mod2m(i); + c.lmul(&u); c.mod2m(i); + + b.add(&c); b.norm(); + b.lmul(&u); b.mod2m(i); + + c.one(); c.shlw(i); b.revsub(&c); b.norm(); + b.shlw(i); + u.add(&b); + i<<=1; + } + u.norm(); + return u; + } + + pub fn random(&mut self,rng: &mut RAND) { + let n=self.length; + for i in 0..n { + self.v[i].copy(&BIG::random(rng)) + } + /* make sure top bit is 1 */ + while self.v[n-1].nbits()<(rom::MODBYTES as usize)*8 { + self.v[n-1].copy(&BIG::random(rng)); + } + } + +/* generate random x less than p */ + pub fn randomnum(&mut self,p: &FF,rng: &mut RAND) { + let n=self.length; + let mut d=FF::new_int(2*n); + + for i in 0..2*n { + d.v[i].copy(&BIG::random(rng)); + } + self.copy(&d.dmod(p)); + } + +/* this*=y mod p */ + pub fn modmul(&mut self,y: &FF,p: &FF,nd: &FF) { + if BIG::ff_pexceed(&self.v[self.length-1],&y.v[y.length-1]) { + self.rmod(p) + } + let mut d=FF::mul(&self,y); + self.copy(&d.reduce(p,nd)); + } + +/* this*=y mod p */ + pub fn modsqr(&mut self,p: &FF,nd: &FF) { + if BIG::ff_sexceed(&self.v[self.length-1]) { + self.rmod(p); + } + let mut d=FF::sqr(&self); + d.norm(); + self.copy(&d.reduce(p,nd)); + } + +/* this=this^e mod p using side-channel resistant Montgomery Ladder, for large e */ + pub fn skpow(&mut self,e: &FF,p: &FF) { + let n=p.length; + let mut r0=FF::new_int(n); + let mut r1=FF::new_int(n); + let nd=p.invmod2m(); + + self.rmod(p); + r0.one(); + r1.copy(&self); + r0.nres(p); + r1.nres(p); + + let mut i=8*(rom::MODBYTES as usize)*n-1; + loop { + let b=(e.v[i/(rom::BIGBITS as usize)]).bit(i%(rom::BIGBITS as usize)) as isize; + self.copy(&r0); + self.modmul(&r1,p,&nd); + + FF::cswap(&mut r0,&mut r1,b); + r0.modsqr(p,&nd); + + r1.copy(&self); + FF::cswap(&mut r0,&mut r1,b); + if i==0 {break} + i-=1; + } + self.copy(&r0); + self.redc(p,&nd); + } + +/* this =this^e mod p using side-channel resistant Montgomery Ladder, for short e */ + pub fn skpows(&mut self,e: &BIG,p: &FF) { + let n=p.length; + let mut r0=FF::new_int(n); + let mut r1=FF::new_int(n); + let nd=p.invmod2m(); + + self.rmod(p); + r0.one(); + r1.copy(&self); + r0.nres(p); + r1.nres(p); + + let mut i=8*(rom::MODBYTES as usize)-1; + loop { + let b=e.bit(i); + self.copy(&r0); + self.modmul(&r1,p,&nd); + + FF::cswap(&mut r0,&mut r1,b); + r0.modsqr(p,&nd); + + r1.copy(&self); + FF::cswap(&mut r0,&mut r1,b); + if i==0 {break} + i-=1; + } + self.copy(&r0); + self.redc(p,&nd); + } + + + + +/* raise to an integer power - right-to-left method */ + pub fn power(&mut self,e: isize,p: &FF) { + let n=p.length; + let mut w=FF::new_int(n); + let nd=p.invmod2m(); + let mut f=true; + let mut ee=e; + + w.copy(&self); + w.nres(p); + + if ee==2 { + self.copy(&w); + self.modsqr(p,&nd); + } else { + loop { + if ee%2==1 { + if f { + self.copy(&w); + } else {self.modmul(&w,p,&nd)} + f=false; + } + ee>>=1; + if ee==0 {break} + w.modsqr(p,&nd); + } + } + + self.redc(p,&nd); + } + +/* this=this^e mod p, faster but not side channel resistant */ + pub fn pow(&mut self,e: &FF,p: &FF) { + let n=p.length; + let mut w=FF::new_int(n); + let nd=p.invmod2m(); + + w.copy(&self); + self.one(); + self.nres(p); + w.nres(p); + let mut i=8*(rom::MODBYTES as usize)*n-1; + loop { + self.modsqr(p,&nd); + let b=(e.v[i/(rom::BIGBITS as usize)]).bit(i%(rom::BIGBITS as usize)) as isize; + if b==1 {self.modmul(&w,p,&nd)} + if i==0 {break} + i-=1; + } + self.redc(p,&nd); + } + +/* double exponentiation r=x^e.y^f mod p */ + pub fn pow2(&mut self,e: &BIG,y: &FF,f: &BIG,p: &FF) { + let n=p.length; + let mut xn=FF::new_int(n); + let mut yn=FF::new_int(n); + let mut xy=FF::new_int(n); + let nd=p.invmod2m(); + + xn.copy(&self); + yn.copy(y); + xn.nres(p); + yn.nres(p); + xy.copy(&xn); xy.modmul(&yn,p,&nd); + self.one(); + self.nres(p); + + let mut i=8*(rom::MODBYTES as usize)-1; + loop { + let eb=e.bit(i); + let fb=f.bit(i); + self.modsqr(p,&nd); + if eb==1 { + if fb==1 { + self.modmul(&xy,p,&nd); + } else {self.modmul(&xn,p,&nd)} + } else { + if fb==1 {self.modmul(&yn,p,&nd)} + } + if i==0 {break} + i-=1; + } + self.redc(p,&nd); + } + + pub fn igcd(x: isize,y: isize) -> isize { /* integer GCD, returns GCD of x and y */ + + if y==0 {return x} + let mut xx=x; + let mut yy=y; + loop { + let r=xx%yy; + if r==0 {break} + xx=yy;yy=r; + } + return yy; + } + +/* quick and dirty check for common factor with n */ + pub fn cfactor(&self,s: isize) -> bool { + let n=self.length; + + let mut x=FF::new_int(n); + let mut y=FF::new_int(n); + + y.set(s); + x.copy(&self); + x.norm(); + + x.sub(&y); + x.norm(); + + while !x.iszilch() && x.parity()==0 {x.shr()} + + while FF::comp(&x,&y)>0 { + x.sub(&y); + x.norm(); + while !x.iszilch() && x.parity()==0 {x.shr()} + } + + let g=x.v[0].get(0) as isize; + let r=FF::igcd(s,g); + if r>1 {return true} + return false + } + +/* Miller-Rabin test for primality. Slow. */ + pub fn prime(pp: &FF,rng: &mut RAND) -> bool { + let mut s=0; + let n=pp.length; + let mut d=FF::new_int(n); + let mut x=FF::new_int(n); + let mut unity=FF::new_int(n); + let mut nm1=FF::new_int(n); + let mut p=FF::new_int(n); p.copy(pp); + + let sf=4849845; /* 3*5*.. *19 */ + p.norm(); + + if p.cfactor(sf) {return false} + unity.one(); + nm1.copy(&p); + nm1.sub(&unity); + nm1.norm(); + d.copy(&nm1); + + while d.parity()==0 { + d.shr(); + s+=1; + } + if s==0 {return false} + for _ in 0..10 { + x.randomnum(&p,rng); + + x.pow(&d,&p); + + if FF::comp(&x,&unity)==0 || FF::comp(&x,&nm1)==0 {continue} + let mut looper=false; + for _ in 1..s { + x.power(2,&p); + if FF::comp(&x,&unity)==0 {return false} + if FF::comp(&x,&nm1)==0 {looper=true; break} + } + if looper {continue} + return false; + } + + return true; + } + +} +/* +fn main() +{ + let mut x=FF::new_int(4); + let mut y=FF::new_int(4); + + x.one(); y.one(); + let mut z=FF::mul(&mut x,&mut y); + + println!("z= {}",z.tostring()); +} +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/fp.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/fp.rs b/version22/rust/src/fp.rs new file mode 100644 index 0000000..d924753 --- /dev/null +++ b/version22/rust/src/fp.rs @@ -0,0 +1,349 @@ +/* +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. +*/ + +use std::fmt; + +#[derive(Copy, Clone)] +pub struct FP { + x:BIG +} + +use big::BIG; +use dbig::DBIG; +use rom; +use rom::{Chunk, BIG_HEX_STRING_LEN}; + +impl fmt::Display for FP { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP: [ {} ]", self.x) + } +} + +impl fmt::Debug for FP { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP: [ {} ]", self.x) + } +} + +impl PartialEq for FP { + fn eq(&self, other: &FP) -> bool { + return self.x == other.x; + } +} + +impl FP { + +/* Constructors */ + pub fn new() -> FP { + FP { + x: BIG::new() + } + } + + pub fn new_int(a:isize) -> FP { + let mut f=FP::new(); + f.x.inc(a); + f.nres(); + return f; + } + + pub fn new_copy(y:&FP) -> FP { + let mut f=FP::new(); + f.x.copy(&(y.x)); + return f; + } + + pub fn new_big(y:&BIG) -> FP { + let mut f=FP::new(); + f.x.copy(y); + f.nres(); + return f; + } + + pub fn nres(&mut self) { + if rom::MODTYPE != rom::PSEUDO_MERSENNE && rom::MODTYPE != rom::GENERALISED_MERSENNE { + let p = BIG::new_ints(&rom::MODULUS); + let mut d=DBIG::new_scopy(&(self.x)); + d.shl(rom::NLEN*(rom::BASEBITS as usize)); + self.x.copy(&d.dmod(&p)); + } + } + +/* convert back to regular form */ + pub fn redc(&mut self) -> BIG { + if rom::MODTYPE != rom::PSEUDO_MERSENNE && rom::MODTYPE != rom::GENERALISED_MERSENNE { + let mut d=DBIG::new_scopy(&(self.x)); + return BIG::modulo(&mut d); + } else { + let r=BIG::new_copy(&(self.x)); + return r; + } + } + + /* convert to string */ + pub fn tostring(&mut self) -> String { + let s=self.redc().tostring(); + return s; + } + + pub fn to_hex(&self) -> String { + let mut ret: String = String::with_capacity(2 * BIG_HEX_STRING_LEN); + let mut x = self.x; + ret.push_str(&format!("{}", x.to_hex())); + return ret; + } + + pub fn from_hex(val: String) -> FP { + return FP { + x: BIG::from_hex(val) + } + } + +/* reduce this mod Modulus */ + pub fn reduce(&mut self) { + let p = BIG::new_ints(&rom::MODULUS); + self.x.rmod(&p) + } + +/* test this=0? */ + pub fn iszilch(&mut self) -> bool { + self.reduce(); + return self.x.iszilch(); + } + +/* copy from FP b */ + pub fn copy(&mut self,b: &FP) { + self.x.copy(&(b.x)); + } + +/* copy from BIG b */ + pub fn bcopy(&mut self,b: &BIG) { + self.x.copy(&b); + self.nres(); + } + +/* set this=0 */ + pub fn zero(&mut self) { + self.x.zero(); + } + +/* set this=1 */ + pub fn one(&mut self) { + self.x.one(); self.nres() + } + +/* normalise this */ + pub fn norm(&mut self) { + self.x.norm(); + } +/* swap FPs depending on d */ + pub fn cswap(&mut self,b: &mut FP,d: isize) { + self.x.cswap(&mut (b.x),d); + } + +/* copy FPs depending on d */ + pub fn cmove(&mut self,b: &FP,d: isize) { + self.x.cmove(&(b.x),d); + } + +/* this*=b mod Modulus */ + pub fn mul(&mut self,b: &mut FP) + { + self.norm(); + b.norm(); + if BIG::pexceed(&(self.x),&(b.x)) {self.reduce()} + + let mut d=BIG::mul(&(self.x),&(b.x)); + self.x.copy(&BIG::modulo(&mut d)) + } + + fn logb2(w: u32) -> usize { + let mut v=w; + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + + v = v - ((v >> 1) & 0x55555555); + v = (v & 0x33333333) + ((v >> 2) & 0x33333333); + let r= (( ((v + (v >> 4)) & 0xF0F0F0F).wrapping_mul(0x1010101)) >> 24) as usize; + return r+1; + } + +/* this = -this mod Modulus */ + pub fn neg(&mut self) { + let mut p = BIG::new_ints(&rom::MODULUS); + + self.norm(); + + let sb=FP::logb2(BIG::excess(&(self.x)) as u32); + + // let mut ov=BIG::excess(&(self.x)); + // let mut sb=1; while ov != 0 {sb += 1;ov>>=1} + + p.fshl(sb); + self.x.rsub(&p); + + if BIG::excess(&(self.x))>=rom::FEXCESS {self.reduce()} + } + + /* this*=c mod Modulus, where c is a small int */ + pub fn imul(&mut self,c: isize) { + let mut cc=c; + self.norm(); + let mut s=false; + if cc<0 { + cc = -cc; + s=true; + } + let afx=(BIG::excess(&(self.x))+1)*((cc as Chunk)+1)+1; + if cc<rom::NEXCESS && afx<rom::FEXCESS { + self.x.imul(cc); + } else { + if afx<rom::FEXCESS { + self.x.pmul(cc); + } else { + let p = BIG::new_ints(&rom::MODULUS); + let mut d=self.x.pxmul(cc); + self.x.copy(&d.dmod(&p)); + } + } + if s {self.neg()} + self.norm(); + } + +/* self*=self mod Modulus */ + pub fn sqr(&mut self) { + self.norm(); + if BIG::sexceed(&(self.x)) {self.reduce()} + + let mut d=BIG::sqr(&(self.x)); + self.x.copy(&BIG::modulo(&mut d)) + } + +/* self+=b */ + pub fn add(&mut self,b: &FP) { + self.x.add(&(b.x)); + if BIG::excess(&(self.x))+2>=rom::FEXCESS {self.reduce()} + } + +/* self+=self */ + pub fn dbl(&mut self) { + self.x.dbl(); + if BIG::excess(&(self.x))+2>=rom::FEXCESS {self.reduce()} + } + +/* self-=b */ + pub fn sub(&mut self,b: &FP) + { + let mut n=FP::new_copy(b); + n.neg(); + self.add(&n); + } + +/* self/=2 mod Modulus */ + pub fn div2(&mut self) { + self.x.norm(); + if self.x.parity()==0 { + self.x.fshr(1); + } else { + let p = BIG::new_ints(&rom::MODULUS); + self.x.add(&p); + self.x.norm(); + self.x.fshr(1); + } + } +/* self=1/self mod Modulus */ + pub fn inverse(&mut self) { + let mut p = BIG::new_ints(&rom::MODULUS); + let mut r=self.redc(); + r.invmodp(&mut p); + self.x.copy(&r); + self.nres(); + } + +/* return TRUE if self==a */ + pub fn equals(&mut self,a: &mut FP) -> bool { + a.reduce(); + self.reduce(); + if BIG::comp(&(a.x),(&self.x))==0 {return true} + return false; + } + +/* return self^e mod Modulus */ + pub fn pow(&mut self,e: &mut BIG) -> FP { + let p = BIG::new_ints(&rom::MODULUS); + let mut r=FP::new_int(1); + e.norm(); + self.x.norm(); + let mut m=FP::new_copy(self); + loop { + let bt=e.parity(); + e.fshr(1); + if bt==1 {r.mul(&mut m)} + if e.iszilch() {break} + m.sqr(); + } + r.x.rmod(&p); + return r; + } + +/* return sqrt(this) mod Modulus */ + pub fn sqrt(&mut self) -> FP { + self.reduce(); + let mut p = BIG::new_ints(&rom::MODULUS); + if rom::MOD8==5 { + p.dec(5); p.norm(); p.shr(3); + let mut i=FP::new_copy(self); i.x.shl(1); + let mut v=i.pow(&mut p); + i.mul(&mut v); i.mul(&mut v); + i.x.dec(1); + let mut r=FP::new_copy(self); + r.mul(&mut v); r.mul(&mut i); + r.reduce(); + return r; + } + else + { + p.inc(1); p.norm(); p.shr(2); + return self.pow(&mut p); + } + } +/* return jacobi symbol (this/Modulus) */ + pub fn jacobi(&mut self) -> isize + { + let mut p = BIG::new_ints(&rom::MODULUS); + let mut w=self.redc(); + return w.jacobi(&mut p); + } + +} +/* +fn main() { + let p = BIG::new_ints(&rom::MODULUS); + let mut e = BIG::new_copy(&p); + e.dec(1); + + let mut x = FP::new_int(3); + let mut s=x.pow(&mut e); + + println!("s= {}",s.tostring()); +} +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/fp12.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/fp12.rs b/version22/rust/src/fp12.rs new file mode 100644 index 0000000..4610e67 --- /dev/null +++ b/version22/rust/src/fp12.rs @@ -0,0 +1,628 @@ +/* +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. +*/ + +use std::fmt; +use std::str::SplitWhitespace; + +#[derive(Copy, Clone)] +pub struct FP12 { + a:FP4, + b:FP4, + c:FP4 +} + +use rom::BIG_HEX_STRING_LEN; + +//mod fp; +//use fp::FP; +//mod fp2; +use fp2::FP2; +//mod fp4; +use fp4::FP4; +//mod big; +use big::BIG; +//mod dbig; +//use dbig::DBIG; +//mod rand; +//mod hash256; +//mod rom; +use rom; + +impl PartialEq for FP12 { + fn eq(&self, other: &FP12) -> bool { + return (self.a == other.a) && + (self.b == other.b) && + (self.c == other.c); + } +} + +impl fmt::Display for FP12 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP12: [ {}, {}, {} ]", self.a, self.b, self.c) + } +} + +impl fmt::Debug for FP12 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP12: [ {}, {}, {} ]", self.a, self.b, self.c) + } +} + +impl FP12 { + + pub fn new() -> FP12 { + FP12 { + a: FP4::new(), + b: FP4::new(), + c: FP4::new() + } + } + + pub fn new_int(a: isize) -> FP12 { + let mut f=FP12::new(); + f.a.copy(&FP4::new_int(a)); + f.b.zero(); + f.c.zero(); + return f; + } + + pub fn new_copy(x: &FP12) -> FP12 { + let mut f=FP12::new(); + f.a.copy(&x.a); + f.b.copy(&x.b); + f.c.copy(&x.c); + return f; + } + + pub fn new_fp4s(d: &FP4,e: &FP4,f: &FP4) -> FP12 { + let mut g=FP12::new(); + g.a.copy(d); + g.b.copy(e); + g.c.copy(f); + return g; + } + + pub fn new_fp4(d: &FP4) -> FP12 { + let mut g=FP12::new(); + g.a.copy(d); + g.b.zero(); + g.c.zero(); + return g; + } + +/* reduce components mod Modulus */ + pub fn reduce(&mut self) { + self.a.reduce(); + self.b.reduce(); + self.c.reduce(); + } + +/* normalise components of w */ + pub fn norm(&mut self) { + self.a.norm(); + self.b.norm(); + self.c.norm(); + } + +/* test self=0 ? */ + pub fn iszilch(&mut self) -> bool { + self.reduce(); + return self.a.iszilch() && self.b.iszilch() && self.c.iszilch(); + } + +/* test self=1 ? */ + pub fn isunity(&mut self) -> bool { + let mut one=FP4::new_int(1); + return self.a.equals(&mut one) && self.b.iszilch() && self.c.iszilch(); + } + +/* test self=x */ + pub fn equals(&mut self,x:&mut FP12) -> bool { + return self.a.equals(&mut x.a) && self.b.equals(&mut x.b) && self.c.equals(&mut x.c); + } + + pub fn geta(&mut self) -> FP4 { + let f=FP4::new_copy(&self.a); + return f; + } + + pub fn getb(&mut self) -> FP4 { + let f=FP4::new_copy(&self.b); + return f; + } + + pub fn getc(&mut self) -> FP4 { + let f=FP4::new_copy(&self.c); + return f; + } + +/* copy self=x */ + pub fn copy(&mut self,x :&FP12) { + self.a.copy(&x.a); + self.b.copy(&x.b); + self.c.copy(&x.c); + } + +/* set self=1 */ + pub fn one(&mut self) { + self.a.one(); + self.b.zero(); + self.c.zero(); + } + +/* this=conj(this) */ + pub fn conj(&mut self) { + self.a.conj(); + self.b.nconj(); + self.c.conj(); + } + +/* Granger-Scott Unitary Squaring */ + pub fn usqr(&mut self) { + let mut a=FP4::new_copy(&self.a); + let mut b=FP4::new_copy(&self.c); + let mut c=FP4::new_copy(&self.b); + let mut d=FP4::new(); + + self.a.sqr(); + d.copy(&self.a); d.add(&self.a); + self.a.add(&d); + + self.a.norm(); + a.nconj(); + + a.dbl(); + self.a.add(&a); + b.sqr(); + b.times_i(); + + d.copy(&b); d.add(&b); + b.add(&d); + b.norm(); + + c.sqr(); + d.copy(&c); d.add(&c); + c.add(&d); + c.norm(); + + self.b.conj(); + self.b.dbl(); + self.c.nconj(); + + self.c.dbl(); + self.b.add(&b); + self.c.add(&c); + self.reduce(); + + } + +/* Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ + pub fn sqr(&mut self) { + let mut a=FP4::new_copy(&self.a); + let mut b=FP4::new_copy(&self.b); + let mut c=FP4::new_copy(&self.c); + let mut d=FP4::new_copy(&self.a); + + a.sqr(); + b.mul(&mut self.c); + b.dbl(); + c.sqr(); + d.mul(&mut self.b); + d.dbl(); + + self.c.add(&self.a); + self.c.add(&self.b); + self.c.sqr(); + + self.a.copy(&a); + a.add(&b); + a.norm(); + a.add(&c); + a.add(&d); + a.norm(); + + a.neg(); + b.times_i(); + c.times_i(); + + self.a.add(&b); + + self.b.copy(&c); self.b.add(&d); + self.c.add(&a); + self.norm(); + } + + +/* FP12 full multiplication self=self*y */ + pub fn mul(&mut self,y: &mut FP12) { + let mut z0=FP4::new_copy(&self.a); + let mut z1=FP4::new(); + let mut z2=FP4::new_copy(&mut self.b); + let mut z3=FP4::new(); + let mut t0=FP4::new_copy(&self.a); + let mut t1=FP4::new_copy(&y.a); + + z0.mul(&mut y.a); + z2.mul(&mut y.b); + + t0.add(&self.b); + t1.add(&y.b); + + z1.copy(&t0); z1.mul(&mut t1); + t0.copy(&self.b); t0.add(&self.c); + + t1.copy(&y.b); t1.add(&y.c); + z3.copy(&t0); z3.mul(&mut t1); + + t0.copy(&z0); t0.neg(); + t1.copy(&z2); t1.neg(); + + z1.add(&t0); + z1.norm(); + self.b.copy(&z1); self.b.add(&t1); + + z3.add(&t1); + z2.add(&t0); + + t0.copy(&self.a); t0.add(&self.c); + t1.copy(&y.a); t1.add(&y.c); + t0.mul(&mut t1); + z2.add(&t0); + + t0.copy(&self.c); t0.mul(&mut y.c); + t1.copy(&t0); t1.neg(); + + z2.norm(); + z3.norm(); + self.b.norm(); + + self.c.copy(&z2); self.c.add(&t1); + z3.add(&t1); + t0.times_i(); + self.b.add(&t0); + + z3.times_i(); + self.a.copy(&z0); self.a.add(&z3); + self.norm(); + } + +/* Special case of multiplication arises from special form of ATE pairing line function */ + pub fn smul(&mut self,y: &mut FP12) { + let mut z0=FP4::new_copy(&self.a); + let mut z2=FP4::new_copy(&self.b); + let mut z3=FP4::new_copy(&self.b); + let mut t0=FP4::new(); + let mut t1=FP4::new_copy(&y.a); + + z0.mul(&mut y.a); + z2.pmul(&mut y.b.real()); + self.b.add(&self.a); + t1.padd(&y.b.real()); + + self.b.mul(&mut t1); + z3.add(&self.c); + z3.pmul(&mut y.b.real()); + + t0.copy(&z0); t0.neg(); + t1.copy(&z2); t1.neg(); + + self.b.add(&t0); + self.b.norm(); + + self.b.add(&t1); + z3.add(&t1); + z2.add(&t0); + + t0.copy(&self.a); t0.add(&self.c); + t0.mul(&mut y.a); + self.c.copy(&z2); self.c.add(&t0); + + z3.times_i(); + self.a.copy(&z0); self.a.add(&z3); + + self.norm(); + } + +/* self=1/self */ + pub fn inverse(&mut self) { + let mut f0=FP4::new_copy(&self.a); + let mut f1=FP4::new_copy(&self.b); + let mut f2=FP4::new_copy(&self.a); + let mut f3=FP4::new(); + + self.norm(); + f0.sqr(); + f1.mul(&mut self.c); + f1.times_i(); + f0.sub(&f1); + + f1.copy(&self.c); f1.sqr(); + f1.times_i(); + f2.mul(&mut self.b); + f1.sub(&f2); + + f2.copy(&self.b); f2.sqr(); + f3.copy(&self.a); f3.mul(&mut self.c); + f2.sub(&f3); + + f3.copy(&self.b); f3.mul(&mut f2); + f3.times_i(); + self.a.mul(&mut f0); + f3.add(&self.a); + self.c.mul(&mut f1); + self.c.times_i(); + + f3.add(&self.c); + f3.inverse(); + self.a.copy(&f0); self.a.mul(&mut f3); + self.b.copy(&f1); self.b.mul(&mut f3); + self.c.copy(&f2); self.c.mul(&mut f3); + } + +/* self=self^p using Frobenius */ + pub fn frob(&mut self,f: &mut FP2) { + let mut f2=FP2::new_copy(f); + let mut f3=FP2::new_copy(f); + + f2.sqr(); + f3.mul(&mut f2); + + self.a.frob(&mut f3); + self.b.frob(&mut f3); + self.c.frob(&mut f3); + + self.b.pmul(f); + self.c.pmul(&mut f2); + } + +/* trace function */ + pub fn trace(&mut self) -> FP4 { + let mut t=FP4::new(); + t.copy(&self.a); + t.imul(3); + t.reduce(); + return t; + } + +/* convert from byte array to FP12 */ + pub fn frombytes(w: &[u8]) -> FP12 { + let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + let mb=rom::MODBYTES as usize; + + for i in 0..mb {t[i]=w[i]} + let mut a=BIG::frombytes(&t); + for i in 0..mb {t[i]=w[i+mb]} + let mut b=BIG::frombytes(&t); + let mut c=FP2::new_bigs(&a,&b); + + for i in 0..mb {t[i]=w[i+2*mb]} + a=BIG::frombytes(&t); + for i in 0..mb {t[i]=w[i+3*mb]} + b=BIG::frombytes(&t); + let mut d=FP2::new_bigs(&a,&b); + + let e=FP4::new_fp2s(&c,&d); + + + for i in 0..mb {t[i]=w[i+4*mb]} + a=BIG::frombytes(&t); + for i in 0..mb {t[i]=w[i+5*mb]} + b=BIG::frombytes(&t); + c=FP2::new_bigs(&a,&b); + + for i in 0..mb {t[i]=w[i+6*mb]} + a=BIG::frombytes(&t); + for i in 0..mb {t[i]=w[i+7*mb]} + b=BIG::frombytes(&t); + d=FP2::new_bigs(&a,&b); + + let f=FP4::new_fp2s(&c,&d); + + + for i in 0..mb {t[i]=w[i+8*mb]} + a=BIG::frombytes(&t); + for i in 0..mb {t[i]=w[i+9*mb]} + b=BIG::frombytes(&t); + + c=FP2::new_bigs(&a,&b); + + for i in 0..mb {t[i]=w[i+10*mb]} + a=BIG::frombytes(&t); + for i in 0..mb {t[i]=w[i+11*mb]} + b=BIG::frombytes(&t); + d=FP2::new_bigs(&a,&b); + + let g=FP4::new_fp2s(&c,&d); + + return FP12::new_fp4s(&e,&f,&g); + } + +/* convert this to byte array */ + pub fn tobytes(&mut self,w: &mut [u8]) { + let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + let mb=rom::MODBYTES as usize; + + self.a.geta().geta().tobytes(&mut t); + for i in 0..mb {w[i]=t[i]} + self.a.geta().getb().tobytes(&mut t); + for i in 0..mb {w[i+mb]=t[i]} + self.a.getb().geta().tobytes(&mut t); + for i in 0..mb {w[i+2*mb]=t[i]} + self.a.getb().getb().tobytes(&mut t); + for i in 0..mb {w[i+3*mb]=t[i]} + + self.b.geta().geta().tobytes(&mut t); + for i in 0..mb {w[i+4*mb]=t[i]} + self.b.geta().getb().tobytes(&mut t); + for i in 0..mb {w[i+5*mb]=t[i]} + self.b.getb().geta().tobytes(&mut t); + for i in 0..mb {w[i+6*mb]=t[i]} + self.b.getb().getb().tobytes(&mut t); + for i in 0..mb {w[i+7*mb]=t[i]} + + self.c.geta().geta().tobytes(&mut t); + for i in 0..mb {w[i+8*mb]=t[i]} + self.c.geta().getb().tobytes(&mut t); + for i in 0..mb {w[i+9*mb]=t[i]} + self.c.getb().geta().tobytes(&mut t); + for i in 0..mb {w[i+10*mb]=t[i]} + self.c.getb().getb().tobytes(&mut t); + for i in 0..mb {w[i+11*mb]=t[i]} + } + +/* output to hex string */ + pub fn tostring(&mut self) -> String { + return format!("[{},{},{}]",self.a.tostring(),self.b.tostring(),self.c.tostring()); + } + + pub fn to_hex(&self) -> String { + let mut ret: String = String::with_capacity(12 * BIG_HEX_STRING_LEN); + ret.push_str(&format!("{} {} {}", self.a.to_hex(), self.b.to_hex(), self.c.to_hex())); + return ret; + } + + pub fn from_hex_iter(iter: &mut SplitWhitespace) -> FP12 { + let mut ret:FP12 = FP12::new(); + ret.a = FP4::from_hex_iter(iter); + ret.b = FP4::from_hex_iter(iter); + ret.c = FP4::from_hex_iter(iter); + return ret; + } + + pub fn from_hex(val: String) -> FP12 { + let mut iter = val.split_whitespace(); + return FP12::from_hex_iter(&mut iter); + } + +/* self=self^e */ + pub fn pow(&mut self,e: &mut BIG) -> FP12 { + self.norm(); + e.norm(); + let mut w=FP12::new_copy(self); + let mut z=BIG::new_copy(&e); + let mut r=FP12::new_int(1); + loop { + let bt=z.parity(); + z.fshr(1); + if bt==1 {r.mul(&mut w)}; + if z.iszilch() {break} + w.usqr(); + } + r.reduce(); + return r; + } + +/* constant time powering by small integer of max length bts */ + pub fn pinpow(&mut self,e: i32,bts: i32) { + let mut r:[FP12;2]=[FP12::new_int(1),FP12::new_copy(self)]; + let mut t=FP12::new(); + + for i in (0..bts).rev() { + let b:usize=((e>>i)&1) as usize; + t.copy(&r[b]); + r[1-b].mul(&mut t); + r[b].usqr(); + } + self.copy(&r[0]); + } + +/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ +/* Timing attack secure, but not cache attack secure */ + + pub fn pow4(q:&mut [FP12],u:&[BIG]) -> FP12 { + let mut a:[i8;4]=[0;4]; + let mut s:[FP12;2]=[FP12::new(),FP12::new()]; + let mut g:[FP12;8]=[FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new()]; + + let mut c=FP12::new_int(1); + let mut p=FP12::new(); + const CT:usize=1+rom::NLEN*(rom::BASEBITS as usize); + let mut w:[i8;CT]=[0;CT]; + + let mut mt=BIG::new(); + let mut t:[BIG;4]=[BIG::new_copy(&u[0]),BIG::new_copy(&u[1]),BIG::new_copy(&u[2]),BIG::new_copy(&u[3])]; + + g[0].copy(&q[0]); s[0].copy(&q[1]); s[0].conj(); g[0].mul(&mut s[0]); + p.copy(&g[0]); + g[1].copy(&p); + g[2].copy(&p); + g[3].copy(&p); + g[4].copy(&q[0]); g[4].mul(&mut q[1]); + p.copy(&g[4]); + g[5].copy(&p); + g[6].copy(&p); + g[7].copy(&p); + + + s[1].copy(&q[2]); s[0].copy(&q[3]); s[0].conj(); p.copy(&s[0]); s[1].mul(&mut p); + p.copy(&s[1]); s[0].copy(&p); s[0].conj(); g[1].mul(&mut s[0]); + g[2].mul(&mut s[1]); + g[5].mul(&mut s[0]); + g[6].mul(&mut s[1]); + s[1].copy(&q[2]); s[1].mul(&mut q[3]); + p.copy(&s[1]); s[0].copy(&p); s[0].conj(); g[0].mul(&mut s[0]); + g[3].mul(&mut s[1]); + g[4].mul(&mut s[0]); + g[7].mul(&mut s[1]); + +/* if power is even add 1 to power, and add q to correction */ + + for i in 0..4 { + if t[i].parity()==0 { + t[i].inc(1); t[i].norm(); + c.mul(&mut q[i]); + } + mt.add(&t[i]); mt.norm(); + } + c.conj(); + let nb=1+mt.nbits(); + +/* convert exponent to signed 1-bit window */ + for j in 0..nb { + for i in 0..4 { + a[i]=(t[i].lastbits(2)-2) as i8; + t[i].dec(a[i] as isize); t[i].norm(); + t[i].fshr(1); + } + w[j]=8*a[0]+4*a[1]+2*a[2]+a[3]; + } + w[nb]=(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2)) as i8; + p.copy(&g[((w[nb] as usize)-1)/2]); + + for i in (0..nb).rev() { + let m=w[i]>>7; + let mut j=((w[i]^m)-m) as usize; /* j=abs(w[i]) */ + j=(j-1)/2; + s[0].copy(&g[j]); s[1].copy(&g[j]); s[1].conj(); + p.usqr(); + p.mul(&mut s[(m&1) as usize]); + } + p.mul(&mut c); /* apply correction */ + p.reduce(); + return p; + } + + +} +/* +fn main() +{ + let mut w=FP12::new(); +} +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/fp2.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/fp2.rs b/version22/rust/src/fp2.rs new file mode 100644 index 0000000..0cf705c --- /dev/null +++ b/version22/rust/src/fp2.rs @@ -0,0 +1,366 @@ +/* +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. +*/ + +use std::fmt; +use std::str::SplitWhitespace; + +#[derive(Copy, Clone)] +pub struct FP2 { + a:FP, + b:FP, +} + +use rom::BIG_HEX_STRING_LEN; +//mod fp; +use fp::FP; +//mod big; +use big::BIG; +//mod dbig; +//use dbig::DBIG; +//mod rand; +//mod hash256; +//mod rom; +//use rom; + +impl fmt::Display for FP2 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP2: [ {}, {} ]", self.a, self.b) + } +} + +impl fmt::Debug for FP2 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP2: [ {}, {} ]", self.a, self.b) + } +} + +impl PartialEq for FP2 { + fn eq(&self, other: &FP2) -> bool { + return (self.a == other.a) && + (self.b == other.b); + } +} + +impl FP2 { + + pub fn new() -> FP2 { + FP2 { + a: FP::new(), + b: FP::new(), + } + } + + pub fn new_int(a: isize) -> FP2 { + let mut f=FP2::new(); + f.a.copy(&FP::new_int(a)); + f.b.zero(); + return f; + } + + pub fn new_copy(x: &FP2) -> FP2 { + let mut f=FP2::new(); + f.a.copy(&x.a); + f.b.copy(&x.b); + return f + } + + pub fn new_fps(c: &FP,d: &FP) -> FP2 { + let mut f=FP2::new(); + f.a.copy(c); + f.b.copy(d); + return f; + } + + pub fn new_bigs(c: &BIG,d: &BIG) -> FP2 { + let mut f=FP2::new(); + f.a.copy(&FP::new_big(c)); + f.b.copy(&FP::new_big(d)); + return f; + } + + pub fn new_fp(c: &FP) -> FP2 { + let mut f=FP2::new(); + f.a.copy(c); + f.b.zero(); + return f; + } + + pub fn new_big(c: &BIG) -> FP2 { + let mut f=FP2::new(); + f.a.copy(&FP::new_big(c)); + f.b.zero(); + return f; + } + +/* reduce components mod Modulus */ + pub fn reduce(&mut self) { + self.a.reduce(); + self.b.reduce(); + } + +/* normalise components of w */ + pub fn norm(&mut self) { + self.a.norm(); + self.b.norm(); + } + +/* test self=0 ? */ + pub fn iszilch(&mut self) -> bool { + self.reduce(); + return self.a.iszilch() && self.b.iszilch(); + } + + pub fn cmove(&mut self,g:&FP2,d: isize) { + self.a.cmove(&g.a,d); + self.b.cmove(&g.b,d); + } + +/* test self=1 ? */ + pub fn isunity(&mut self) -> bool { + let mut one=FP::new_int(1); + return self.a.equals(&mut one) && self.b.iszilch(); + } + +/* test self=x */ + pub fn equals(&mut self,x:&mut FP2) -> bool { + return self.a.equals(&mut x.a) && self.b.equals(&mut x.b); + } + +/* extract a */ + pub fn geta(&mut self) -> BIG { + return self.a.redc(); + } + +/* extract b */ + pub fn getb(&mut self) -> BIG { + return self.b.redc(); + } + +/* copy self=x */ + pub fn copy(&mut self,x :&FP2) { + self.a.copy(&x.a); + self.b.copy(&x.b); + } + +/* set self=0 */ + pub fn zero(&mut self) { + self.a.zero(); + self.b.zero(); + } + +/* set self=1 */ + pub fn one(&mut self) { + self.a.one(); + self.b.zero(); + } + +/* negate self mod Modulus */ + pub fn neg(&mut self) { + self.norm(); + let mut m=FP::new_copy(&self.a); + let mut t=FP::new(); + + m.add(&self.b); + m.neg(); + m.norm(); + t.copy(&m); t.add(&self.b); + self.b.copy(&m); + self.b.add(&self.a); + self.a.copy(&t); + } + +/* set to a-ib */ + pub fn conj(&mut self) { + self.b.neg(); + } + +/* self+=a */ + pub fn add(&mut self,x:&FP2) { + self.a.add(&x.a); + self.b.add(&x.b); + } + + pub fn dbl(&mut self) { + self.a.dbl(); + self.b.dbl(); + } + +/* self-=a */ + pub fn sub(&mut self,x:&FP2) { + let mut m=FP2::new_copy(x); + m.neg(); + self.add(&m); + } + +/* self*=s, where s is an FP */ + pub fn pmul(&mut self,s:&mut FP) { + self.a.mul(s); + self.b.mul(s); + } + +/* self*=i, where i is an int */ + pub fn imul(&mut self,c: isize) { + self.a.imul(c); + self.b.imul(c); + } + +/* self*=self */ + pub fn sqr(&mut self) { + self.norm(); + let mut w1=FP::new_copy(&self.a); + let mut w3=FP::new_copy(&self.a); + let mut mb=FP::new_copy(&self.b); + + w3.mul(&mut self.b); + w1.add(&self.b); + mb.neg(); + self.a.add(&mb); + self.a.mul(&mut w1); + self.b.copy(&w3); self.b.add(&w3); + + self.norm(); + } + +/* this*=y */ + pub fn mul(&mut self,y :&mut FP2) { + self.norm(); /* This is needed here as {a,b} is not normed before additions */ + + let mut w1=FP::new_copy(&self.a); + let mut w2=FP::new_copy(&self.b); + let mut w5=FP::new_copy(&self.a); + let mut mw=FP::new(); + + w1.mul(&mut y.a); // w1=a*y.a - this norms w1 and y.a, NOT a + w2.mul(&mut y.b); // w2=b*y.b - this norms w2 and y.b, NOT b + w5.add(&self.b); // w5=a+b + self.b.copy(&y.a); self.b.add(&y.b); // b=y.a+y.b + + self.b.mul(&mut w5); + mw.copy(&w1); mw.add(&w2); mw.neg(); + + self.b.add(&mw); mw.add(&w1); + self.a.copy(&w1); self.a.add(&mw); + + self.norm(); + } + +/* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2)) */ +/* returns true if this is QR */ + pub fn sqrt(&mut self) -> bool { + if self.iszilch() {return true} + let mut w1=FP::new_copy(&self.b); + let mut w2=FP::new_copy(&self.a); + w1.sqr(); w2.sqr(); w1.add(&w2); + if w1.jacobi()!=1 { self.zero(); return false } + w2.copy(&w1.sqrt()); w1.copy(&w2); + w2.copy(&self.a); w2.add(&w1); w2.div2(); + if w2.jacobi()!=1 { + w2.copy(&self.a); w2.sub(&w1); w2.div2(); + if w2.jacobi()!=1 { self.zero(); return false } + } + w1.copy(&w2.sqrt()); + self.a.copy(&w1); + w1.dbl(); + w1.inverse(); + self.b.mul(&mut w1); + return true; + } + +/* output to hex string */ + pub fn tostring(&mut self) -> String { + return format!("[{},{}]",self.a.tostring(),self.b.tostring()); + } + + pub fn to_hex(&self) -> String { + let mut ret: String = String::with_capacity(2 * BIG_HEX_STRING_LEN); + ret.push_str(&format!("{} {}", self.a.to_hex(), self.b.to_hex())); + return ret; + } + + pub fn from_hex_iter(iter: &mut SplitWhitespace) -> FP2 { + let mut ret:FP2 = FP2::new(); + ret.a = FP::from_hex(iter.next().unwrap_or("").to_string()); + ret.b = FP::from_hex(iter.next().unwrap_or("").to_string()); + return ret; + } + + pub fn from_hex(val: String) -> FP2 { + let mut iter = val.split_whitespace(); + return FP2::from_hex_iter(&mut iter); + } + +/* self=1/self */ + pub fn inverse(&mut self) { + self.norm(); + let mut w1=FP::new_copy(&self.a); + let mut w2=FP::new_copy(&self.b); + + w1.sqr(); + w2.sqr(); + w1.add(&w2); + w1.inverse(); + self.a.mul(&mut w1); + w1.neg(); + self.b.mul(&mut w1); + } + +/* self/=2 */ + pub fn div2(&mut self) { + self.a.div2(); + self.b.div2(); + } + +/* self*=sqrt(-1) */ + pub fn times_i(&mut self) { + // a.norm(); + let z=FP::new_copy(&self.a); + self.a.copy(&self.b); self.a.neg(); + self.b.copy(&z); + } + +/* w*=(1+sqrt(-1)) */ +/* where X*2-(1+sqrt(-1)) is irreducible for FP4, assumes p=3 mod 8 */ + pub fn mul_ip(&mut self) { + self.norm(); + let t=FP2::new_copy(self); + let z=FP::new_copy(&self.a); + self.a.copy(&self.b); + self.a.neg(); + self.b.copy(&z); + self.add(&t); + self.norm(); + } + +/* w/=(1+sqrt(-1)) */ + pub fn div_ip(&mut self) { + let mut t=FP2::new(); + self.norm(); + t.a.copy(&self.a); t.a.add(&self.b); + t.b.copy(&self.b); t.b.sub(&self.a); + self.copy(&t); + self.div2(); + } + +} +/* +fn main() +{ + let mut x=FP2::new(); +} +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/fp4.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/fp4.rs b/version22/rust/src/fp4.rs new file mode 100644 index 0000000..ea2806d --- /dev/null +++ b/version22/rust/src/fp4.rs @@ -0,0 +1,563 @@ +/* +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. +*/ + +use std::fmt; +use std::str::SplitWhitespace; + +#[derive(Copy, Clone)] +pub struct FP4 { + a:FP2, + b:FP2, +} + +use rom::BIG_HEX_STRING_LEN; +//mod fp; +//use fp::FP; +//mod fp2; +use fp2::FP2; +//mod big; +use big::BIG; +//mod dbig; +//use dbig::DBIG; +//mod rand; +//mod hash256; +//mod rom; +//use rom; + +impl PartialEq for FP4 { + fn eq(&self, other: &FP4) -> bool { + return (self.a == other.a) && + (self.b == other.b); + } +} + +impl fmt::Display for FP4 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP4: [ {}, {} ]", self.a, self.b) + } +} + +impl fmt::Debug for FP4 { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "FP4: [ {}, {} ]", self.a, self.b) + } +} + +impl FP4 { + + pub fn new() -> FP4 { + FP4 { + a: FP2::new(), + b: FP2::new(), + } + } + + pub fn new_int(a: isize) -> FP4 { + let mut f=FP4::new(); + f.a.copy(&FP2::new_int(a)); + f.b.zero(); + return f; + } + + pub fn new_copy(x: &FP4) -> FP4 { + let mut f=FP4::new(); + f.a.copy(&x.a); + f.b.copy(&x.b); + return f; + } + + pub fn new_fp2s(c: &FP2,d: &FP2) -> FP4 { + let mut f=FP4::new(); + f.a.copy(c); + f.b.copy(d); + return f; + } + + pub fn new_fp2(c: &FP2) -> FP4 { + let mut f=FP4::new(); + f.a.copy(c); + f.b.zero(); + return f; + } + +/* reduce components mod Modulus */ + pub fn reduce(&mut self) { + self.a.reduce(); + self.b.reduce(); + } + +/* normalise components of w */ + pub fn norm(&mut self) { + self.a.norm(); + self.b.norm(); + } + +/* test self=0 ? */ + pub fn iszilch(&mut self) -> bool { + self.reduce(); + return self.a.iszilch() && self.b.iszilch(); + } + +/* test self=1 ? */ + pub fn isunity(&mut self) -> bool { + let mut one=FP2::new_int(1); + return self.a.equals(&mut one) && self.b.iszilch(); + } + +/* test is w real? That is in a+ib test b is zero */ + pub fn isreal(&mut self) -> bool { + return self.b.iszilch(); + } +/* extract real part a */ + pub fn real(&mut self) -> FP2 { + let f=FP2::new_copy(&self.a); + return f; + } + + pub fn geta(&mut self) -> FP2 { + let f=FP2::new_copy(&self.a); + return f; + } +/* extract imaginary part b */ + pub fn getb(&mut self) -> FP2 { + let f=FP2::new_copy(&self.b); + return f; + } + +/* test self=x */ + pub fn equals(&mut self,x:&mut FP4) -> bool { + return self.a.equals(&mut x.a) && self.b.equals(&mut x.b); + } +/* copy self=x */ + pub fn copy(&mut self,x :&FP4) { + self.a.copy(&x.a); + self.b.copy(&x.b); + } + +/* set self=0 */ + pub fn zero(&mut self) { + self.a.zero(); + self.b.zero(); + } + +/* set self=1 */ + pub fn one(&mut self) { + self.a.one(); + self.b.zero(); + } + +/* negate self mod Modulus */ + pub fn neg(&mut self) { + self.norm(); + let mut m=FP2::new_copy(&self.a); + let mut t=FP2::new(); + + m.add(&self.b); + m.neg(); + m.norm(); + t.copy(&m); t.add(&self.b); + self.b.copy(&m); + self.b.add(&self.a); + self.a.copy(&t); + } + +/* set to a-ib */ + pub fn conj(&mut self) { + self.b.neg(); + self.b.norm(); + } + +/* self=-conjugate(self) */ + pub fn nconj(&mut self) { + self.a.neg(); self.a.norm(); + } + +/* self+=a */ + pub fn add(&mut self,x:&FP4) { + self.a.add(&x.a); + self.b.add(&x.b); + } + + pub fn padd(&mut self,x:&FP2) { + self.a.add(x); + } + + pub fn dbl(&mut self) { + self.a.dbl(); + self.b.dbl(); + } + +/* self-=a */ + pub fn sub(&mut self,x:&FP4) { + let mut m=FP4::new_copy(x); + m.neg(); + self.add(&m); + } + +/* self*=s, where s is an FP */ + pub fn pmul(&mut self,s:&mut FP2) { + self.a.mul(s); + self.b.mul(s); + } + +/* self*=i, where i is an int */ + pub fn imul(&mut self,c: isize) { + self.a.imul(c); + self.b.imul(c); + } + +/* self*=self */ + pub fn sqr(&mut self) { + self.norm(); + + let mut t1=FP2::new_copy(&self.a); + let mut t2=FP2::new_copy(&self.b); + let mut t3=FP2::new_copy(&self.a); + + + t3.mul(&mut self.b); + t1.add(&self.b); + t2.mul_ip(); + + t2.add(&mut self.a); + self.a.copy(&t1); + + self.a.mul(&mut t2); + + t2.copy(&t3); + t2.mul_ip(); + t2.add(&mut t3); + t2.neg(); + self.a.add(&t2); + + t3.dbl(); + self.b.copy(&t3); + + self.norm(); + } + +/* self*=y */ + pub fn mul(&mut self,y :&mut FP4) { + self.norm(); + + let mut t1=FP2::new_copy(&self.a); + let mut t2=FP2::new_copy(&self.b); + let mut t3=FP2::new(); + let mut t4=FP2::new_copy(&self.b); + + t1.mul(&mut y.a); + t2.mul(&mut y.b); + t3.copy(&y.b); + t3.add(&y.a); + t4.add(&self.a); + + t4.mul(&mut t3); + t4.sub(&t1); + t4.norm(); + + self.b.copy(&t4); + self.b.sub(&t2); + t2.mul_ip(); + self.a.copy(&t2); + self.a.add(&t1); + + self.norm(); + } + +/* output to hex string */ + pub fn tostring(&mut self) -> String { + return format!("[{},{}]",self.a.tostring(),self.b.tostring()); + } + + pub fn to_hex(&self) -> String { + let mut ret: String = String::with_capacity(4 * BIG_HEX_STRING_LEN); + ret.push_str(&format!("{} {}", self.a.to_hex(), self.b.to_hex())); + return ret; + } + + pub fn from_hex_iter(iter: &mut SplitWhitespace) -> FP4 { + let mut ret:FP4 = FP4::new(); + ret.a = FP2::from_hex_iter(iter); + ret.b = FP2::from_hex_iter(iter); + return ret; + } + + pub fn from_hex(val: String) -> FP4 { + let mut iter = val.split_whitespace(); + return FP4::from_hex_iter(&mut iter); + } + +/* self=1/self */ + pub fn inverse(&mut self) { + self.norm(); + + let mut t1=FP2::new_copy(&self.a); + let mut t2=FP2::new_copy(&self.b); + + t1.sqr(); + t2.sqr(); + t2.mul_ip(); + t1.sub(&t2); + t1.inverse(); + self.a.mul(&mut t1); + t1.neg(); + self.b.mul(&mut t1); + } + +/* self*=i where i = sqrt(-1+sqrt(-1)) */ + pub fn times_i(&mut self) { + self.norm(); + let mut s=FP2::new_copy(&self.b); + let mut t=FP2::new_copy(&self.b); + s.times_i(); + t.add(&s); + t.norm(); + self.b.copy(&self.a); + self.a.copy(&t); + } + +/* self=self^p using Frobenius */ + pub fn frob(&mut self,f: &mut FP2) { + self.a.conj(); + self.b.conj(); + self.b.mul(f); + } + +/* self=self^e */ + pub fn pow(&mut self,e: &mut BIG) -> FP4 { + self.norm(); + e.norm(); + let mut w=FP4::new_copy(self); + let mut z=BIG::new_copy(&e); + let mut r=FP4::new_int(1); + loop { + let bt=z.parity(); + z.fshr(1); + if bt==1 {r.mul(&mut w)}; + if z.iszilch() {break} + w.sqr(); + } + r.reduce(); + return r; + } + +/* XTR xtr_a function */ + pub fn xtr_a(&mut self,w:&FP4,y:&FP4,z:&FP4) { + let mut r=FP4::new_copy(w); + let mut t=FP4::new_copy(w); + r.sub(y); + r.pmul(&mut self.a); + t.add(y); + t.pmul(&mut self.b); + t.times_i(); + + self.copy(&r); + self.add(&t); + self.add(z); + + self.norm(); + } + +/* XTR xtr_d function */ + pub fn xtr_d(&mut self) { + let mut w=FP4::new_copy(self); + self.sqr(); w.conj(); + w.dbl(); + self.sub(&w); + self.reduce(); + } + +/* r=x^n using XTR method on traces of FP12s */ + pub fn xtr_pow(&mut self,n: &mut BIG) -> FP4 { + let mut a=FP4::new_int(3); + let mut b=FP4::new_copy(self); + let mut c=FP4::new_copy(&b); + c.xtr_d(); + let mut t=FP4::new(); + let mut r=FP4::new(); + + n.norm(); + let par=n.parity(); + let mut v=BIG::new_copy(n); v.fshr(1); + if par==0 {v.dec(1); v.norm(); } + + let nb=v.nbits(); + for i in (0..nb).rev() { + if v.bit(i)!=1 { + t.copy(&b); + self.conj(); + c.conj(); + b.xtr_a(&a,self,&c); + self.conj(); + c.copy(&t); + c.xtr_d(); + a.xtr_d(); + } else { + t.copy(&a); t.conj(); + a.copy(&b); + a.xtr_d(); + b.xtr_a(&c,self,&t); + c.xtr_d(); + } + } + if par==0 { + r.copy(&c) + } else {r.copy(&b)} + r.reduce(); + return r; + } + +/* r=ck^a.cl^n using XTR double exponentiation method on traces of FP12s. See Stam thesis. */ + pub fn xtr_pow2(&mut self,ck: &FP4,ckml: &FP4,ckm2l: &FP4,a: &mut BIG,b: &mut BIG) -> FP4 { + a.norm(); b.norm(); + let mut e=BIG::new_copy(a); + let mut d=BIG::new_copy(b); + let mut w=BIG::new(); + + let mut cu=FP4::new_copy(ck); // can probably be passed in w/o copying + let mut cv=FP4::new_copy(self); + let mut cumv=FP4::new_copy(ckml); + let mut cum2v=FP4::new_copy(ckm2l); + let mut r=FP4::new(); + let mut t=FP4::new(); + + let mut f2:usize=0; + while d.parity()==0 && e.parity()==0 { + d.fshr(1); + e.fshr(1); + f2+=1; + } + + while BIG::comp(&d,&e)!=0 { + if BIG::comp(&d,&e)>0 { + w.copy(&e); w.imul(4); w.norm(); + if BIG::comp(&d,&w)<=0 { + w.copy(&d); d.copy(&e); + e.rsub(&w); e.norm(); + + t.copy(&cv); + t.xtr_a(&cu,&cumv,&cum2v); + cum2v.copy(&cumv); + cum2v.conj(); + cumv.copy(&cv); + cv.copy(&cu); + cu.copy(&t); + } else { + if d.parity()==0 { + d.fshr(1); + r.copy(&cum2v); r.conj(); + t.copy(&cumv); + t.xtr_a(&cu,&cv,&r); + cum2v.copy(&cumv); + cum2v.xtr_d(); + cumv.copy(&t); + cu.xtr_d(); + } else { + if e.parity()==1 { + d.sub(&e); d.norm(); + d.fshr(1); + t.copy(&cv); + t.xtr_a(&cu,&cumv,&cum2v); + cu.xtr_d(); + cum2v.copy(&cv); + cum2v.xtr_d(); + cum2v.conj(); + cv.copy(&t); + } else { + w.copy(&d); + d.copy(&e); d.fshr(1); + e.copy(&w); + t.copy(&cumv); + t.xtr_d(); + cumv.copy(&cum2v); cumv.conj(); + cum2v.copy(&t); cum2v.conj(); + t.copy(&cv); + t.xtr_d(); + cv.copy(&cu); + cu.copy(&t); + } + } + } + } + if BIG::comp(&d,&e)<0 { + w.copy(&d); w.imul(4); w.norm(); + if BIG::comp(&e,&w)<=0 { + e.sub(&d); e.norm(); + t.copy(&cv); + t.xtr_a(&cu,&cumv,&cum2v); + cum2v.copy(&cumv); + cumv.copy(&cu); + cu.copy(&t); + } else { + if e.parity()==0 { + w.copy(&d); + d.copy(&e); d.fshr(1); + e.copy(&w); + t.copy(&cumv); + t.xtr_d(); + cumv.copy(&cum2v); cumv.conj(); + cum2v.copy(&t); cum2v.conj(); + t.copy(&cv); + t.xtr_d(); + cv.copy(&cu); + cu.copy(&t); + } else { + if d.parity()==1 { + w.copy(&e); + e.copy(&d); + w.sub(&d); w.norm(); + d.copy(&w); d.fshr(1); + t.copy(&cv); + t.xtr_a(&cu,&cumv,&cum2v); + cumv.conj(); + cum2v.copy(&cu); + cum2v.xtr_d(); + cum2v.conj(); + cu.copy(&cv); + cu.xtr_d(); + cv.copy(&t); + } else { + d.fshr(1); + r.copy(&cum2v); r.conj(); + t.copy(&cumv); + t.xtr_a(&cu,&cv,&r); + cum2v.copy(&cumv); + cum2v.xtr_d(); + cumv.copy(&t); + cu.xtr_d(); + } + } + } + } + } + r.copy(&cv); + r.xtr_a(&cu,&cumv,&cum2v); + for _ in 0..f2 {r.xtr_d()} + r=r.xtr_pow(&mut d); + return r; + } + + +} +/* +fn main() +{ + let mut w=FP4::new(); +} +*/
