include/ff.h.in - incubator-milagro-crypto-c - 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.
 */

 /**
  * @file ff_WWW.h
  * @author Mike Scott
  * @brief FF Header File
  *
  */

 #ifndef FF_WWW_H
 #define FF_WWW_H

 #include "big_XXX.h"
 #include "config_ff_WWW.h"

 #define HFLEN_WWW (FFLEN_WWW/2) /**< Useful for half-size RSA private key operations */
 #define P_MBITS_WWW (MODBYTES_XXX*8) /**< Number of bits in modulus */
 #define P_TBITS_WWW (P_MBITS_WWW%BASEBITS_XXX) /**< TODO  */
 #define P_EXCESS_WWW(a) (((a[NLEN_XXX-1])>>(P_TBITS_WWW))+1) /**< TODO */
 #define P_FEXCESS_WWW ((chunk)1<<(BASEBITS_XXX*NLEN_XXX-P_MBITS_WWW-1)) /**< TODO */


 /* Finite Field Prototypes */
 /**	@brief Copy one FF element of given length to another
  *
 	@param x FF instance to be copied to, on exit = y
 	@param y FF instance to be copied from
 	@param n size of FF in BIGs

  */
 extern void FF_WWW_copy(BIG_XXX *x,BIG_XXX *y,int n);
 /**	@brief Initialize an FF element of given length from a 32-bit integer m
  *
 	@param x FF instance to be copied to, on exit = m
 	@param m integer
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_init(BIG_XXX *x,sign32 m,int n);
 /**	@brief Set FF element of given size to zero
  *
 	@param x FF instance to be set to zero
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_zero(BIG_XXX *x,int n);
 /**	@brief Tests for FF element equal to zero
  *
 	@param x FF number to be tested
 	@param n size of FF in BIGs
 	@return 1 if zero, else returns 0
  */
 extern int FF_WWW_iszilch(BIG_XXX *x,int n);
 /**	@brief Tests for FF element equal to one
  *
 	@param x FF number to be tested
 	@param n size of FF in BIGs
 	@return 1 if unity, else returns 0
  */
 extern int FF_WWW_isunity(BIG_XXX *x,int n);
 /**	@brief  return parity of an FF, that is the least significant bit
  *
 	@param x FF number
 	@return 0 or 1
  */
 extern int FF_WWW_parity(BIG_XXX *x);
 /**	@brief  return least significant m bits of an FF
  *
 	@param x FF number
 	@param m number of bits to return. Assumed to be less than BASEBITS.
 	@return least significant n bits as an integer
  */
 extern int FF_WWW_lastbits(BIG_XXX *x,int m);
 /**	@brief Set FF element of given size to unity
  *
 	@param x FF instance to be set to unity
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_one(BIG_XXX *x,int n);
 /**	@brief Compares two FF numbers. Inputs must be normalised externally
  *
 	@param x first FF number to be compared
 	@param y second FF number to be compared
 	@param n size of FF in BIGs
 	@return -1 is x<y, 0 if x=y, 1 if x>y
  */
 extern int FF_WWW_comp(BIG_XXX *x,BIG_XXX *y,int n);
 /**	@brief addition of two FFs
  *
 	@param x FF instance, on exit = y+z
 	@param y FF instance
 	@param z FF instance
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_add(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n);
 /**	@brief subtraction of two FFs
  *
 	@param x FF instance, on exit = y-z
 	@param y FF instance
 	@param z FF instance
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_sub(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n);
 /**	@brief increment an FF by an integer,and normalise
  *
 	@param x FF instance, on exit = x+m
 	@param m an integer to be added to x
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_inc(BIG_XXX *x,int m,int n);
 /**	@brief Decrement an FF by an integer,and normalise
  *
 	@param x FF instance, on exit = x-m
 	@param m an integer to be subtracted from x
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_dec(BIG_XXX *x,int m,int n);
 /**	@brief Normalises the components of an FF
  *
 	@param x FF instance to be normalised
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_norm(BIG_XXX *x,int n);
 /**	@brief Shift left an FF by 1 bit
  *
 	@param x FF instance to be shifted left
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_shl(BIG_XXX *x,int n);
 /**	@brief Shift right an FF by 1 bit
  *
 	@param x FF instance to be shifted right
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_shr(BIG_XXX *x,int n);
 /**	@brief Formats and outputs an FF to the console
  *
 	@param x FF instance to be printed
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_output(BIG_XXX *x,int n);
 /**	@brief Formats and outputs an FF to the console, in raw form
  *
  	@param x FF instance to be printed
  	@param n size of FF in BIGs
  */
 extern void FF_WWW_rawoutput(BIG_XXX *x,int n);
 /**	@brief Formats and outputs an FF instance to an octet string
  *
 	Converts an FF to big-endian base 256 form.
 	@param S output octet string
 	@param x FF instance to be converted to an octet string
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_toOctet(octet *S,BIG_XXX *x,int n);
 /**	@brief Populates an FF instance from an octet string
  *
 	Creates FF from big-endian base 256 form.
 	@param x FF instance to be created from an octet string
 	@param S input octet string
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_fromOctet(BIG_XXX *x,octet *S,int n);
 /**	@brief Multiplication of two FFs
  *
 	Uses Karatsuba method internally
 	@param x FF instance, on exit = y*z
 	@param y FF instance
 	@param z FF instance
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_mul(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n);
 /**	@brief Reduce FF mod a modulus - leaks log2(p)-log2(n)
  *
 	This is slow
 	@param x FF instance to be reduced mod p - on exit = x mod p
 	@param p FF modulus
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_mod(BIG_XXX *x,BIG_XXX *p,int n);
 /**	@brief Square an FF
  *
 	Uses Karatsuba method internally
 	@param x FF instance, on exit = y^2
 	@param y FF instance to be squared
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_sqr(BIG_XXX *x,BIG_XXX *y,int n);
 /**	@brief Reduces a double-length FF with respect to a given modulus - leaks log2(y)-log2(z)
  *
 	This is slow
 	@param x FF instance, on exit = y mod z
 	@param y FF instance, of double length 2*n
 	@param z FF modulus
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_dmod(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n);
 /**	@brief Invert an FF mod a prime modulus
  *
 	@param x FF instance, on exit = 1/y mod z
 	@param y FF instance
 	@param z FF prime modulus
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_invmodp(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n);
 /** @brief Invert an FF mod 2^(n*BIGBITS)
  *
  * @param U FF instance, on exit 1/a mod 2^(n*BIGBITS)
  * @param a FF instance
  * @param n size of FF in BIGs
  */
 extern void FF_WWW_invmod2m(BIG_XXX U[],BIG_XXX a[],int n);
 /**	@brief Create an FF from a random number generator
  *
 	@param x FF instance, on exit x is a random number of length n BIGs with most significant bit a 1
 	@param R an instance of a Cryptographically Secure Random Number Generator
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_random(BIG_XXX *x,csprng *R,int n);
 /**	@brief Create a random FF less than a given modulus from a random number generator - leaks log2(y)
  *
 	@param x FF instance, on exit x is a random number < y
 	@param y FF instance, the modulus
 	@param R an instance of a Cryptographically Secure Random Number Generator
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_randomnum(BIG_XXX *x,BIG_XXX *y,csprng *R,int n);
 /**	@brief Precomputation step for the 2^w-ary method
  *  Given bases X = {x1,...xk}, fill the precomputation table T
  *  for the given window size w.
  *  T must have size 2^(w*k)
  *
 	@param X     FF instances, the base(s) for the multiple exponent
 	@param T     FF instances, the resulting precomputation table
 	@param k     size of X, the number of bases in the multiple exponent
 	@param w     window size
 	@param p     FF instance, modulus for the exponent
 	@param ND    FF instance, p^-1 mod 2^|p| for operations in Montgomery form
 	@param plen  size of p in BIGS
  */
 extern void FF_WWW_2w_precompute(BIG_XXX *X[], BIG_XXX *T[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen);
 /**	@brief Constant time evaluation step for the 2^w-ary method
  *  Given precomputation table T and exponents E = {e1,...ek}, compute the
  *  multiple exponent.
  *  Side channel resistant.
  *
  *  Remark. This function assumes that the window size divides the number
  *  of bits in a BIG_XXX
  *
 	@param r     FF instance, on exit the computed power
 	@param T     FF instances, the precomputed table
 	@param E     FF instance, exponent(s) for the multiple exponent
 	@param k     size of E, the number of exponents in the multiple exponent
 	@param w     window size
 	@param p     FF instance, modulus for the exponent
 	@param ND    FF instance, p^-1 mod 2^|p| for operations in Montgomery form
 	@param plen  size of p in BIGS
 	@param elen  size of exponents in BIGS
  */
 extern void FF_WWW_ct_2w_pow(BIG_XXX r[], BIG_XXX *T[], BIG_XXX *E[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen, int elen);
 /**	@brief Non constant time evaluation step for the 2^w-ary method
  *  Given precomputation table T and exponents E = {e1,...ek}, compute the
  *  multiple exponent.
  *  NOT Side channel resistant, but slightly faster
  *
  *  Remark. This function assumes that the window size divides the number
  *  of bits in a BIG_XXX
  *
 	@param r     FF instance, on exit the computed power
 	@param T     FF instances, the precomputed table
 	@param E     FF instance, exponent(s) for the multiple exponent
 	@param k     size of E, the number of exponents in the multiple exponent
 	@param w     window size
 	@param p     FF instance, modulus for the exponent
 	@param ND    FF instance, p^-1 mod 2^|p| for operations in Montgomery form
 	@param plen  size of p in BIGS
 	@param elen  size of exponents in BIGS
  */
 extern void FF_WWW_nt_2w_pow(BIG_XXX r[], BIG_XXX *T[], BIG_XXX *E[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen, int elen);
 /**	@brief Precomputation step for the Basic Interleaving method
  *  Given bases X = {x1,...xk}, fill the precomputation table T
  *  for the given window size w.
  *  T must have size k * 2^(w-1)
  *
 	@param X     FF instances, the base(s) for the multiple exponent
 	@param T     FF instances, the resulting precomputation table
 	@param k     size of X, the number of bases in the multiple exponent
 	@param w     window size
 	@param p     FF instance, modulus for the exponent
 	@param ND    FF instance, p^-1 mod 2^|p| for operations in Montgomery form
 	@param plen  size of p in BIGS
  */
 extern void FF_WWW_bi_precompute(BIG_XXX *X[], BIG_XXX *T[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen);
 /**	@brief Non constant time evaluation step for the basic interleaving method
  *  Given precomputation table T and exponents E = {e1,...ek}, compute the
  *  multiple exponent.
  *  NOT Side channel resistant.
  *
 	@param r     FF instance, on exit the computed power
 	@param T     FF instances, the precomputed table
 	@param E     FF instance, exponent(s) for the multiple exponent
 	@param k     size of E, the number of exponents in the multiple exponent
 	@param w     window size
 	@param p     FF instance, modulus for the exponent
 	@param ND    FF instance, p^-1 mod 2^|p| for operations in Montgomery form
 	@param plen  size of p in BIGS
 	@param elen  size of exponents in BIGS
  */
 extern void FF_WWW_bi_pow(BIG_XXX r[], BIG_XXX *T[], BIG_XXX *E[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen, int elen);
 /**	@brief Calculate r=x^e mod p, side channel resistant
  *
 	@param r FF instance, on exit = x^e mod p
 	@param x FF instance
 	@param e FF exponent
 	@param p FF modulus
 	@param n size of FF in BIGs
 	@param en size of the exponent in BIGs
  */
 extern void FF_WWW_ct_pow(BIG_XXX *r,BIG_XXX *x,BIG_XXX * e,BIG_XXX *p,int n, int en);
 /**	@brief Calculate r=x^e mod p, side channel resistant
  *
 	For short BIG exponent
 	@param r FF instance, on exit = x^e mod p
 	@param x FF instance
 	@param e BIG exponent
 	@param p FF modulus
 	@param n size of FF in BIGs
  */
 extern void FF_WWW_ct_pow_big(BIG_XXX *r,BIG_XXX *x,BIG_XXX e,BIG_XXX *p,int n);
 /**	@brief Calculate r=x^e.y^f mod p for FF e and f, side channel resistant
  *
 	@param r  FF instance, on exit = x^e.y^f mod p
 	@param x  FF instance
 	@param e  FF exponent
 	@param y  FF instance
 	@param f  FF exponent
 	@param p  FF modulus
 	@param n  size of FF in BIGs
 	@param en size of the exponent in BIGs
  */
 extern void FF_WWW_ct_pow_2(BIG_XXX *r,BIG_XXX *x, BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *p, int n, int en);
 /**	@brief Calculate r=x^e.y^f.z^g mod p for FF e, f and g, side channel resistant
  *
 	@param r  FF instance, on exit = x^e.y^f.z^g mod p
 	@param x  FF instance
 	@param e  FF exponent
 	@param y  FF instance
 	@param f  FF exponent
 	@param z  FF instance
 	@param g  FF exponent
 	@param p  FF modulus
 	@param n  size of FF in BIGs
 	@param en size of the exponent in BIGs
  */
 extern void FF_WWW_ct_pow_3(BIG_XXX *r,BIG_XXX *x, BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *p, int n, int en);
 /**	@brief Calculate r=x^e mod p. Faster but not constant time
  *
 	For very short integer exponent
 	@param r  FF instance, on exit = x^e mod p
 	@param x  FF instance
 	@param e  integer exponent
 	@param p  FF modulus
 	@param n  size of FF in BIGs
  */
 extern void FF_WWW_nt_pow_int(BIG_XXX *r,BIG_XXX *x,int e,BIG_XXX *p,int n);
 /**	@brief Calculate r=x^e mod p
  *
 	@param r  FF instance, on exit = x^e mod p
 	@param x  FF instance
 	@param e  FF exponent
 	@param p  FF modulus
 	@param n  size of base in BIGs
 	@param en size of exponent in BIGs
  */
 extern void FF_WWW_nt_pow(BIG_XXX *r, BIG_XXX *x, BIG_XXX *e, BIG_XXX *p, int n, int en);
 /**	@brief Calculate r=x^e.y^f mod p. Faster but non constant time
  *
 	@param r  FF instance, on exit = x^e.y^f mod p
 	@param x  FF instance
 	@param e  BIG exponent
 	@param y  FF instance
 	@param f  BIG exponent
 	@param p  FF modulus
 	@param n   size of FF in BIGs
 	@param en size of exponent in BIGs
  */
 void FF_WWW_nt_pow_2(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *p,int n, int en);
 /**	@brief Calculate r=x^e.y^f.z^g mod p. Faster but non constant time
  *
 	@param r  FF instance, on exit = x^e.y^f.z^g mod p
 	@param x  FF instance
 	@param e  BIG exponent
 	@param y  FF instance
 	@param f  BIG exponent
 	@param z  FF instance
 	@param g  BIG exponent
 	@param p  FF modulus
 	@param n  size of FF in BIGs
 	@param en size of exponent in BIGs
  */
 void FF_WWW_nt_pow_3(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *p, int n, int en);
 /**	@brief Calculate r=x^e.y^f.z^g.w^h mod p. Faster but non constant time
  *
 	@param r  FF instance, on exit = x^e.y^f.z^g.w^h mod p
 	@param x  FF instance
 	@param e  BIG exponent
 	@param y  FF instance
 	@param f  BIG exponent
 	@param z  FF instance
 	@param g  BIG exponent
 	@param w  FF instance
 	@param h  BIG exponent
 	@param p  FF modulus
 	@param n  size of FF in BIGs
 	@param en size of exponent in BIGs
  */
 extern void FF_WWW_nt_pow_4(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *w, BIG_XXX *h, BIG_XXX *p, int n, int en);
 /**	@brief Test if an FF has factor in common with integer s
  *
 	@param x FF instance to be tested
 	@param s the supplied integer
 	@param n size of FF in BIGs
 	@return 1 if gcd(x,s)!=1, else return 0
  */
 extern int FF_WWW_cfactor(BIG_XXX *x,sign32 s,int n);
 /**	@brief Test if an FF is prime
  *
 	Uses Miller-Rabin Method
 	@param x FF instance to be tested
 	@param R an instance of a Cryptographically Secure Random Number Generator
 	@param n size of FF in BIGs
 	@return 1 if x is (almost certainly) prime, else return 0
  */
 extern int FF_WWW_prime(BIG_XXX *x,csprng *R,int n);
 /**	@brief Combine rp and rq using the Chinese Remainder Theorem
  *
 	@param r     FF instance, on exit the solution of the system
 	@param rp    FF instance, solution modulo p
 	@param rq    FF instance, solution modulo q
 	@param p     FF instance, MUST be coprime with q
 	@param invpq FF instance, p^(-1) mod q
 	@param pq    FF instance, p*q
 	@param n     size of p in BIGs
  */
 extern void FF_WWW_crt(BIG_XXX *r, BIG_XXX *rp, BIG_XXX *rq, BIG_XXX *p, BIG_XXX *invpq, BIG_XXX *pq, int n);

 #endif
	/*
	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.
	*/

	/**
	* @file ff_WWW.h
	* @author Mike Scott
	* @brief FF Header File
	*
	*/

	#ifndef FF_WWW_H
	#define FF_WWW_H

	#include "big_XXX.h"
	#include "config_ff_WWW.h"

	#define HFLEN_WWW (FFLEN_WWW/2) /*< Useful for half-size RSA private key operations /
	#define P_MBITS_WWW (MODBYTES_XXX8) /< Number of bits in modulus /
	#define P_TBITS_WWW (P_MBITS_WWW%BASEBITS_XXX) /*< TODO /
	#define P_EXCESS_WWW(a) (((a[NLEN_XXX-1])>>(P_TBITS_WWW))+1) /*< TODO /
	#define P_FEXCESS_WWW ((chunk)1<<(BASEBITS_XXXNLEN_XXX-P_MBITS_WWW-1)) /< TODO /


	/* Finite Field Prototypes */
	/** @brief Copy one FF element of given length to another
	*
	@param x FF instance to be copied to, on exit = y
	@param y FF instance to be copied from
	@param n size of FF in BIGs

	*/
	extern void FF_WWW_copy(BIG_XXX x,BIG_XXX y,int n);
	/** @brief Initialize an FF element of given length from a 32-bit integer m
	*
	@param x FF instance to be copied to, on exit = m
	@param m integer
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_init(BIG_XXX *x,sign32 m,int n);
	/** @brief Set FF element of given size to zero
	*
	@param x FF instance to be set to zero
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_zero(BIG_XXX *x,int n);
	/** @brief Tests for FF element equal to zero
	*
	@param x FF number to be tested
	@param n size of FF in BIGs
	@return 1 if zero, else returns 0
	*/
	extern int FF_WWW_iszilch(BIG_XXX *x,int n);
	/** @brief Tests for FF element equal to one
	*
	@param x FF number to be tested
	@param n size of FF in BIGs
	@return 1 if unity, else returns 0
	*/
	extern int FF_WWW_isunity(BIG_XXX *x,int n);
	/** @brief return parity of an FF, that is the least significant bit
	*
	@param x FF number
	@return 0 or 1
	*/
	extern int FF_WWW_parity(BIG_XXX *x);
	/** @brief return least significant m bits of an FF
	*
	@param x FF number
	@param m number of bits to return. Assumed to be less than BASEBITS.
	@return least significant n bits as an integer
	*/
	extern int FF_WWW_lastbits(BIG_XXX *x,int m);
	/** @brief Set FF element of given size to unity
	*
	@param x FF instance to be set to unity
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_one(BIG_XXX *x,int n);
	/** @brief Compares two FF numbers. Inputs must be normalised externally
	*
	@param x first FF number to be compared
	@param y second FF number to be compared
	@param n size of FF in BIGs
	@return -1 is x<y, 0 if x=y, 1 if x>y
	*/
	extern int FF_WWW_comp(BIG_XXX x,BIG_XXX y,int n);
	/** @brief addition of two FFs
	*
	@param x FF instance, on exit = y+z
	@param y FF instance
	@param z FF instance
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_add(BIG_XXX x,BIG_XXX y,BIG_XXX *z,int n);
	/** @brief subtraction of two FFs
	*
	@param x FF instance, on exit = y-z
	@param y FF instance
	@param z FF instance
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_sub(BIG_XXX x,BIG_XXX y,BIG_XXX *z,int n);
	/** @brief increment an FF by an integer,and normalise
	*
	@param x FF instance, on exit = x+m
	@param m an integer to be added to x
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_inc(BIG_XXX *x,int m,int n);
	/** @brief Decrement an FF by an integer,and normalise
	*
	@param x FF instance, on exit = x-m
	@param m an integer to be subtracted from x
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_dec(BIG_XXX *x,int m,int n);
	/** @brief Normalises the components of an FF
	*
	@param x FF instance to be normalised
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_norm(BIG_XXX *x,int n);
	/** @brief Shift left an FF by 1 bit
	*
	@param x FF instance to be shifted left
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_shl(BIG_XXX *x,int n);
	/** @brief Shift right an FF by 1 bit
	*
	@param x FF instance to be shifted right
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_shr(BIG_XXX *x,int n);
	/** @brief Formats and outputs an FF to the console
	*
	@param x FF instance to be printed
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_output(BIG_XXX *x,int n);
	/** @brief Formats and outputs an FF to the console, in raw form
	*
	@param x FF instance to be printed
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_rawoutput(BIG_XXX *x,int n);
	/** @brief Formats and outputs an FF instance to an octet string
	*
	Converts an FF to big-endian base 256 form.
	@param S output octet string
	@param x FF instance to be converted to an octet string
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_toOctet(octet S,BIG_XXX x,int n);
	/** @brief Populates an FF instance from an octet string
	*
	Creates FF from big-endian base 256 form.
	@param x FF instance to be created from an octet string
	@param S input octet string
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_fromOctet(BIG_XXX x,octet S,int n);
	/** @brief Multiplication of two FFs
	*
	Uses Karatsuba method internally
	@param x FF instance, on exit = y*z
	@param y FF instance
	@param z FF instance
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_mul(BIG_XXX x,BIG_XXX y,BIG_XXX *z,int n);
	/** @brief Reduce FF mod a modulus - leaks log2(p)-log2(n)
	*
	This is slow
	@param x FF instance to be reduced mod p - on exit = x mod p
	@param p FF modulus
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_mod(BIG_XXX x,BIG_XXX p,int n);
	/** @brief Square an FF
	*
	Uses Karatsuba method internally
	@param x FF instance, on exit = y^2
	@param y FF instance to be squared
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_sqr(BIG_XXX x,BIG_XXX y,int n);
	/** @brief Reduces a double-length FF with respect to a given modulus - leaks log2(y)-log2(z)
	*
	This is slow
	@param x FF instance, on exit = y mod z
	@param y FF instance, of double length 2*n
	@param z FF modulus
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_dmod(BIG_XXX x,BIG_XXX y,BIG_XXX *z,int n);
	/** @brief Invert an FF mod a prime modulus
	*
	@param x FF instance, on exit = 1/y mod z
	@param y FF instance
	@param z FF prime modulus
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_invmodp(BIG_XXX x,BIG_XXX y,BIG_XXX *z,int n);
	/** @brief Invert an FF mod 2^(n*BIGBITS)
	*
	* @param U FF instance, on exit 1/a mod 2^(n*BIGBITS)
	* @param a FF instance
	* @param n size of FF in BIGs
	*/
	extern void FF_WWW_invmod2m(BIG_XXX U[],BIG_XXX a[],int n);
	/** @brief Create an FF from a random number generator
	*
	@param x FF instance, on exit x is a random number of length n BIGs with most significant bit a 1
	@param R an instance of a Cryptographically Secure Random Number Generator
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_random(BIG_XXX x,csprng R,int n);
	/** @brief Create a random FF less than a given modulus from a random number generator - leaks log2(y)
	*
	@param x FF instance, on exit x is a random number < y
	@param y FF instance, the modulus
	@param R an instance of a Cryptographically Secure Random Number Generator
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_randomnum(BIG_XXX x,BIG_XXX y,csprng *R,int n);
	/** @brief Precomputation step for the 2^w-ary method
	* Given bases X = {x1,...xk}, fill the precomputation table T
	* for the given window size w.
	* T must have size 2^(w*k)
	*
	@param X FF instances, the base(s) for the multiple exponent
	@param T FF instances, the resulting precomputation table
	@param k size of X, the number of bases in the multiple exponent
	@param w window size
	@param p FF instance, modulus for the exponent
	@param ND FF instance, p^-1 mod 2^\|p\| for operations in Montgomery form
	@param plen size of p in BIGS
	*/
	extern void FF_WWW_2w_precompute(BIG_XXX X[], BIG_XXX T[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen);
	/** @brief Constant time evaluation step for the 2^w-ary method
	* Given precomputation table T and exponents E = {e1,...ek}, compute the
	* multiple exponent.
	* Side channel resistant.
	*
	* Remark. This function assumes that the window size divides the number
	* of bits in a BIG_XXX
	*
	@param r FF instance, on exit the computed power
	@param T FF instances, the precomputed table
	@param E FF instance, exponent(s) for the multiple exponent
	@param k size of E, the number of exponents in the multiple exponent
	@param w window size
	@param p FF instance, modulus for the exponent
	@param ND FF instance, p^-1 mod 2^\|p\| for operations in Montgomery form
	@param plen size of p in BIGS
	@param elen size of exponents in BIGS
	*/
	extern void FF_WWW_ct_2w_pow(BIG_XXX r[], BIG_XXX T[], BIG_XXX E[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen, int elen);
	/** @brief Non constant time evaluation step for the 2^w-ary method
	* Given precomputation table T and exponents E = {e1,...ek}, compute the
	* multiple exponent.
	* NOT Side channel resistant, but slightly faster
	*
	* Remark. This function assumes that the window size divides the number
	* of bits in a BIG_XXX
	*
	@param r FF instance, on exit the computed power
	@param T FF instances, the precomputed table
	@param E FF instance, exponent(s) for the multiple exponent
	@param k size of E, the number of exponents in the multiple exponent
	@param w window size
	@param p FF instance, modulus for the exponent
	@param ND FF instance, p^-1 mod 2^\|p\| for operations in Montgomery form
	@param plen size of p in BIGS
	@param elen size of exponents in BIGS
	*/
	extern void FF_WWW_nt_2w_pow(BIG_XXX r[], BIG_XXX T[], BIG_XXX E[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen, int elen);
	/** @brief Precomputation step for the Basic Interleaving method
	* Given bases X = {x1,...xk}, fill the precomputation table T
	* for the given window size w.
	* T must have size k * 2^(w-1)
	*
	@param X FF instances, the base(s) for the multiple exponent
	@param T FF instances, the resulting precomputation table
	@param k size of X, the number of bases in the multiple exponent
	@param w window size
	@param p FF instance, modulus for the exponent
	@param ND FF instance, p^-1 mod 2^\|p\| for operations in Montgomery form
	@param plen size of p in BIGS
	*/
	extern void FF_WWW_bi_precompute(BIG_XXX X[], BIG_XXX T[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen);
	/** @brief Non constant time evaluation step for the basic interleaving method
	* Given precomputation table T and exponents E = {e1,...ek}, compute the
	* multiple exponent.
	* NOT Side channel resistant.
	*
	@param r FF instance, on exit the computed power
	@param T FF instances, the precomputed table
	@param E FF instance, exponent(s) for the multiple exponent
	@param k size of E, the number of exponents in the multiple exponent
	@param w window size
	@param p FF instance, modulus for the exponent
	@param ND FF instance, p^-1 mod 2^\|p\| for operations in Montgomery form
	@param plen size of p in BIGS
	@param elen size of exponents in BIGS
	*/
	extern void FF_WWW_bi_pow(BIG_XXX r[], BIG_XXX T[], BIG_XXX E[], int k, int w, BIG_XXX p[], BIG_XXX ND[], int plen, int elen);
	/** @brief Calculate r=x^e mod p, side channel resistant
	*
	@param r FF instance, on exit = x^e mod p
	@param x FF instance
	@param e FF exponent
	@param p FF modulus
	@param n size of FF in BIGs
	@param en size of the exponent in BIGs
	*/
	extern void FF_WWW_ct_pow(BIG_XXX r,BIG_XXX x,BIG_XXX * e,BIG_XXX *p,int n, int en);
	/** @brief Calculate r=x^e mod p, side channel resistant
	*
	For short BIG exponent
	@param r FF instance, on exit = x^e mod p
	@param x FF instance
	@param e BIG exponent
	@param p FF modulus
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_ct_pow_big(BIG_XXX r,BIG_XXX x,BIG_XXX e,BIG_XXX *p,int n);
	/** @brief Calculate r=x^e.y^f mod p for FF e and f, side channel resistant
	*
	@param r FF instance, on exit = x^e.y^f mod p
	@param x FF instance
	@param e FF exponent
	@param y FF instance
	@param f FF exponent
	@param p FF modulus
	@param n size of FF in BIGs
	@param en size of the exponent in BIGs
	*/
	extern void FF_WWW_ct_pow_2(BIG_XXX r,BIG_XXX x, BIG_XXX e, BIG_XXX y, BIG_XXX f, BIG_XXX p, int n, int en);
	/** @brief Calculate r=x^e.y^f.z^g mod p for FF e, f and g, side channel resistant
	*
	@param r FF instance, on exit = x^e.y^f.z^g mod p
	@param x FF instance
	@param e FF exponent
	@param y FF instance
	@param f FF exponent
	@param z FF instance
	@param g FF exponent
	@param p FF modulus
	@param n size of FF in BIGs
	@param en size of the exponent in BIGs
	*/
	extern void FF_WWW_ct_pow_3(BIG_XXX r,BIG_XXX x, BIG_XXX e, BIG_XXX y, BIG_XXX f, BIG_XXX z, BIG_XXX g, BIG_XXX p, int n, int en);
	/** @brief Calculate r=x^e mod p. Faster but not constant time
	*
	For very short integer exponent
	@param r FF instance, on exit = x^e mod p
	@param x FF instance
	@param e integer exponent
	@param p FF modulus
	@param n size of FF in BIGs
	*/
	extern void FF_WWW_nt_pow_int(BIG_XXX r,BIG_XXX x,int e,BIG_XXX *p,int n);
	/** @brief Calculate r=x^e mod p
	*
	@param r FF instance, on exit = x^e mod p
	@param x FF instance
	@param e FF exponent
	@param p FF modulus
	@param n size of base in BIGs
	@param en size of exponent in BIGs
	*/
	extern void FF_WWW_nt_pow(BIG_XXX r, BIG_XXX x, BIG_XXX e, BIG_XXX p, int n, int en);
	/** @brief Calculate r=x^e.y^f mod p. Faster but non constant time
	*
	@param r FF instance, on exit = x^e.y^f mod p
	@param x FF instance
	@param e BIG exponent
	@param y FF instance
	@param f BIG exponent
	@param p FF modulus
	@param n size of FF in BIGs
	@param en size of exponent in BIGs
	*/
	void FF_WWW_nt_pow_2(BIG_XXX r,BIG_XXX x,BIG_XXX e, BIG_XXX y, BIG_XXX f, BIG_XXX p,int n, int en);
	/** @brief Calculate r=x^e.y^f.z^g mod p. Faster but non constant time
	*
	@param r FF instance, on exit = x^e.y^f.z^g mod p
	@param x FF instance
	@param e BIG exponent
	@param y FF instance
	@param f BIG exponent
	@param z FF instance
	@param g BIG exponent
	@param p FF modulus
	@param n size of FF in BIGs
	@param en size of exponent in BIGs
	*/
	void FF_WWW_nt_pow_3(BIG_XXX r,BIG_XXX x,BIG_XXX e, BIG_XXX y, BIG_XXX f, BIG_XXX z, BIG_XXX g, BIG_XXX p, int n, int en);
	/** @brief Calculate r=x^e.y^f.z^g.w^h mod p. Faster but non constant time
	*
	@param r FF instance, on exit = x^e.y^f.z^g.w^h mod p
	@param x FF instance
	@param e BIG exponent
	@param y FF instance
	@param f BIG exponent
	@param z FF instance
	@param g BIG exponent
	@param w FF instance
	@param h BIG exponent
	@param p FF modulus
	@param n size of FF in BIGs
	@param en size of exponent in BIGs
	*/
	extern void FF_WWW_nt_pow_4(BIG_XXX r,BIG_XXX x,BIG_XXX e, BIG_XXX y, BIG_XXX f, BIG_XXX z, BIG_XXX g, BIG_XXX w, BIG_XXX h, BIG_XXX p, int n, int en);
	/** @brief Test if an FF has factor in common with integer s
	*
	@param x FF instance to be tested
	@param s the supplied integer
	@param n size of FF in BIGs
	@return 1 if gcd(x,s)!=1, else return 0
	*/
	extern int FF_WWW_cfactor(BIG_XXX *x,sign32 s,int n);
	/** @brief Test if an FF is prime
	*
	Uses Miller-Rabin Method
	@param x FF instance to be tested
	@param R an instance of a Cryptographically Secure Random Number Generator
	@param n size of FF in BIGs
	@return 1 if x is (almost certainly) prime, else return 0
	*/
	extern int FF_WWW_prime(BIG_XXX x,csprng R,int n);
	/** @brief Combine rp and rq using the Chinese Remainder Theorem
	*
	@param r FF instance, on exit the solution of the system
	@param rp FF instance, solution modulo p
	@param rq FF instance, solution modulo q
	@param p FF instance, MUST be coprime with q
	@param invpq FF instance, p^(-1) mod q
	@param pq FF instance, p*q
	@param n size of p in BIGs
	*/
	extern void FF_WWW_crt(BIG_XXX r, BIG_XXX rp, BIG_XXX rq, BIG_XXX p, BIG_XXX invpq, BIG_XXX pq, int n);

	#endif