version22/rust/src/fp.rs - incubator-milagro-crypto - Git at Google

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