| /* |
| 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(); |
| } |
| */ |