binint.h 41.4 KB
Newer Older
Gerard Ryan's avatar
Gerard Ryan committed
1
/**
Gerard Ryan's avatar
Gerard Ryan committed
2
 * @file binint.h This file contains the main class for native integers.
Gerard Ryan's avatar
Gerard Ryan committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 * @author  TPOC: palisade@njit.edu
 *
 * @copyright Copyright (c) 2017, New Jersey Institute of Technology (NJIT)
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * 1. Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice, this
 * list of conditions and the following disclaimer in the documentation and/or other
 * materials provided with the distribution.
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */
 /*
Gerard Ryan's avatar
Gerard Ryan committed
27 28
 * This file contains the main class for native integers.
 * It implements the same methods as other mathematical backends.
Gerard Ryan's avatar
Gerard Ryan committed
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
 */

#ifndef LBCRYPTO_MATH_NATIVE_BININT_H
#define LBCRYPTO_MATH_NATIVE_BININT_H

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <string>
#include <type_traits>
#include <typeinfo>
#include <limits>
#include <fstream>
#include <stdexcept>
#include <functional>
#include <cstdlib>
Gerard Ryan's avatar
Gerard Ryan committed
46
#include <NTL/ZZ.h>
Gerard Ryan's avatar
Gerard Ryan committed
47
#include <memory>
Gerard Ryan's avatar
Gerard Ryan committed
48
#include "../interface.h"
Gerard Ryan's avatar
Gerard Ryan committed
49
#include "../../utils/inttypes.h"
Gerard Ryan's avatar
Gerard Ryan committed
50
#include "../../utils/serializable.h"
Gerard Ryan's avatar
Gerard Ryan committed
51 52
#include "../../utils/memory.h"
#include "../../utils/palisadebase64.h"
Gerard Ryan's avatar
Gerard Ryan committed
53
#include "../../utils/exception.h"
Gerard Ryan's avatar
Gerard Ryan committed
54
#include "../../utils/debug.h"
Gerard Ryan's avatar
Gerard Ryan committed
55 56
#include "../nbtheory.h"

Gerard Ryan's avatar
Gerard Ryan committed
57

Gerard Ryan's avatar
Gerard Ryan committed
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
namespace native_int {

/**
 * @brief Struct to determine a datatype that is twice as big(bitwise) as utype.
 * sets T as of type void for default case
 *
 * @tparam utype primitive integer data type.
 */
template<typename utype>
struct DoubleDataType{
	typedef void T;
};

/**
 * @brief Struct to determine a datatype that is twice as big(bitwise) as utype.
 * sets T as of type unsigned integer 64 bit if integral datatype is 32bit
 */
template<>
struct DoubleDataType<uint32_t>{
	typedef uint64_t T;
};

/**
* @brief Struct to determine a datatype that is twice as big(bitwise) as utype.
* sets T as of type unsigned integer 128 bit if integral datatype is 64bit
*/
template<>
struct DoubleDataType<uint64_t>{
	typedef unsigned __int128 T;
};

const double LOG2_10 = 3.32192809;	//!< @brief A pre-computed constant of Log base 2 of 10.
const usint BARRETT_LEVELS = 8;		//!< @brief The number of levels (precomputed values) used in the Barrett reductions.


/**
 * @brief Main class for big integers represented as an array of native (primitive) unsigned integers
 * @tparam uint_type native unsigned integer type
 * @tparam BITLENGTH maximum bitdwidth supported for big integers
 */
template<typename uint_type>
Gerard Ryan's avatar
Gerard Ryan committed
99
class NativeInteger : public lbcrypto::BigIntegerInterface<NativeInteger<uint_type>>
Gerard Ryan's avatar
Gerard Ryan committed
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
{

public:
	/**
	 * Default constructor.
	 */
	NativeInteger() : m_value(0) {}

	/**
	 * Basic constructor for specifying the integer.
	 *
	 * @param str is the initial integer represented as a string.
	 */
	NativeInteger(const std::string& str) {
		AssignVal(str);
	}

	/**
	 * Basic constructor for initializing from an unsigned integer.
	 *
	 * @param init is the initial integer.
	 */
	NativeInteger(const uint_type& init) : m_value(init) {}

	/**
	 * Basic constructor for copying 
	 *
	 * @param bigInteger is the integer to be copied.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
129
	NativeInteger(const NativeInteger& nInteger) : m_value(nInteger.m_value) {}
Gerard Ryan's avatar
Gerard Ryan committed
130

Gerard Ryan's avatar
Gerard Ryan committed
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
    /**
     * Constructors from smaller basic types
     * @param init
     */
	NativeInteger(int init) : NativeInteger( uint64_t(init) ) {}
	NativeInteger(uint32_t init) : NativeInteger( uint64_t(init) ) {}
	NativeInteger(long init) : NativeInteger( uint64_t(init) ) {}
	NativeInteger(long long init) : NativeInteger( uint64_t(init) ) {}

    /**
     * Constructor from double is not permitted
     * @param d
     */
	NativeInteger(double d) __attribute__ ((deprecated("Cannot construct from a double")));

    /**
Gerard Ryan's avatar
Gerard Ryan committed
147 148 149 150 151 152 153 154 155 156 157 158 159
	 * Assignment operator
	 *
	 * @param &rhs is the integer to be assigned from.
	 * @return assigned ref.
	 */
	const NativeInteger&  operator=(const NativeInteger &rhs) {
		this->m_value = rhs.m_value;
		return *this;
	}

	/**
	 * Assignment operator
	 *
Gerard Ryan's avatar
Gerard Ryan committed
160
	 * @param &rhs is the integer to be assigned from.
Gerard Ryan's avatar
Gerard Ryan committed
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
	 * @return assigned BigInteger ref.
	 */
	const NativeInteger&  operator=(const NativeInteger &&rhs) {
		this->m_value = rhs.m_value;
		return *this;
	}

	/**
	 * Assignment operator from unsigned integer
	 *
	 * @param val is the unsigned integer value that is assigned.
	 * @return the assigned BigInteger ref.
	 */
	const NativeInteger& operator=(const uint_type& val) {
		this->m_value = val;
		return *this;
	}

Gerard Ryan's avatar
Gerard Ryan committed
179 180 181 182
	vector<NativeInteger> GetInternalRepresentation() {
	  vector<NativeInteger> ret;
	  ret.push_back(m_value);
	  return ret;
Gerard Ryan's avatar
Gerard Ryan committed
183 184 185
	}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
186
	 * Basic set method for setting the value of an integer
Gerard Ryan's avatar
Gerard Ryan committed
187
	 *
Gerard Ryan's avatar
Gerard Ryan committed
188
	 * @param str is the string representation of the integer to be copied.
Gerard Ryan's avatar
Gerard Ryan committed
189 190 191 192 193 194
	 */
	void SetValue(const std::string& str) {
		AssignVal(str);
	}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
195
	 * Basic set method for setting the value of an integer
Gerard Ryan's avatar
Gerard Ryan committed
196 197 198 199 200 201 202 203 204 205 206 207 208
	 *
	 * @param a is the big binary integer representation of the big binary integer to be assigned.
	 */
	void SetValue(const NativeInteger& a) {
		m_value = a.m_value;
	}


	/**
	 * Returns the MSB location of the value.
	 *
	 * @return the index of the most significant bit.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
209
	usint GetMSB() const { return lbcrypto::GetMSB64(this->m_value); }
Gerard Ryan's avatar
Gerard Ryan committed
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228

	/**
	 * Converts the value to an int.
	 *
	 * @return the int representation of the value as usint.
	 */
	uint64_t ConvertToInt() const {
		return m_value;
	}

	/**
	 * Converts the value to an double.
	 *
	 * @return double representation of the value.
	 */
	double ConvertToDouble() const {
		return m_value;
	}

Gerard Ryan's avatar
Gerard Ryan committed
229
	//Arithmetic Operations
Gerard Ryan's avatar
Gerard Ryan committed
230 231 232 233 234 235 236 237 238 239

	/**
	 * Addition operation.
	 *
	 * @param b is the value to add of type BigInteger.
	 * @return result of the addition operation of type BigInteger.
	 */
	NativeInteger Plus(const NativeInteger& b) const {
		uint_type newv = m_value + b.m_value;
		if( newv < m_value || newv < b.m_value ) {
Gerard Ryan's avatar
Gerard Ryan committed
240
			PALISADE_THROW( lbcrypto::math_error, "Overflow");
Gerard Ryan's avatar
Gerard Ryan committed
241 242 243 244 245
		}
		return newv;
	}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
246
	 * Addition operation.
Gerard Ryan's avatar
Gerard Ryan committed
247
	 *
Gerard Ryan's avatar
Gerard Ryan committed
248
	 * @param b is the value to add of type BigInteger.
Gerard Ryan's avatar
Gerard Ryan committed
249 250
	 * @return result of the addition operation of type BigInteger.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
251
	const NativeInteger& PlusEq(const NativeInteger& b) {
Gerard Ryan's avatar
Gerard Ryan committed
252
		//uint_type oldv = m_value;
Gerard Ryan's avatar
Gerard Ryan committed
253
		m_value += b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
254 255 256
		//if( m_value < oldv ) {
		//	PALISADE_THROW( lbcrypto::math_error, "Overflow");
		//}
Gerard Ryan's avatar
Gerard Ryan committed
257 258 259 260 261 262 263 264 265 266
		return *this;
	}

	/**
	 * Subtraction operation.
	 *
	 * @param b is the value to subtract of type BigInteger.
	 * @return result of the subtraction operation of type BigInteger.
	 */
	NativeInteger Minus(const NativeInteger& b) const {
Gerard Ryan's avatar
Gerard Ryan committed
267 268
		return m_value - b.m_value;
//		return m_value <= b.m_value ? 0 : m_value - b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
269
	}
Gerard Ryan's avatar
Gerard Ryan committed
270

Gerard Ryan's avatar
Gerard Ryan committed
271
	/**
Gerard Ryan's avatar
Gerard Ryan committed
272
	 * Subtraction operation.
Gerard Ryan's avatar
Gerard Ryan committed
273
	 *
Gerard Ryan's avatar
Gerard Ryan committed
274 275
	 * @param b is the value to subtract of type BigInteger.
	 * @return result of the subtraction operation of type BigInteger.
Gerard Ryan's avatar
Gerard Ryan committed
276
	 */
Gerard Ryan's avatar
Gerard Ryan committed
277
	const NativeInteger& MinusEq(const NativeInteger& b) {
Gerard Ryan's avatar
Gerard Ryan committed
278
		m_value -= b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
279 280
		return *this;
	}
Gerard Ryan's avatar
Gerard Ryan committed
281

Gerard Ryan's avatar
Gerard Ryan committed
282 283 284 285 286 287 288 289 290
	/**
	 * Multiplication operation.
	 *
	 * @param b of type BigInteger is the value to multiply with.
	 * @return result of the multiplication operation.
	 */
	NativeInteger Times(const NativeInteger& b) const {
		uint_type prod = m_value * b.m_value;
		if( prod > 0 && (prod < m_value || prod < b.m_value) )
Gerard Ryan's avatar
Gerard Ryan committed
291
			PALISADE_THROW( lbcrypto::math_error, "Overflow");
Gerard Ryan's avatar
Gerard Ryan committed
292 293 294
		return prod;
	}

Gerard Ryan's avatar
Gerard Ryan committed
295 296 297 298 299 300 301 302 303 304 305 306 307 308
	/**
	 * Multiplication operation.
	 *
	 * @param b of type BigInteger is the value to multiply with.
	 * @return result of the multiplication operation.
	 */
	const NativeInteger& TimesEq(const NativeInteger& b) {
		uint_type oldval = m_value;
		m_value *= b.m_value;
		if( m_value < oldval )
			PALISADE_THROW( lbcrypto::math_error, "Overflow");
		return *this;
	}

Gerard Ryan's avatar
Gerard Ryan committed
309 310 311 312 313 314 315 316
	/**
	 * Division operation.
	 *
	 * @param b of type NativeInteger is the value to divide by.
	 * @return result of the division operation.
	 */
	NativeInteger DividedBy(const NativeInteger& b) const {
		if( b.m_value == 0 )
Gerard Ryan's avatar
Gerard Ryan committed
317
			PALISADE_THROW( lbcrypto::math_error, "Divide by zero");
Gerard Ryan's avatar
Gerard Ryan committed
318 319
		return this->m_value / b.m_value;
	}
Gerard Ryan's avatar
Gerard Ryan committed
320

Gerard Ryan's avatar
Gerard Ryan committed
321
	/**
Gerard Ryan's avatar
Gerard Ryan committed
322
	 * Division operation.
Gerard Ryan's avatar
Gerard Ryan committed
323
	 *
Gerard Ryan's avatar
Gerard Ryan committed
324 325
	 * @param b of type NativeInteger is the value to divide by.
	 * @return result of the division operation.
Gerard Ryan's avatar
Gerard Ryan committed
326
	 */
Gerard Ryan's avatar
Gerard Ryan committed
327 328 329 330
	const NativeInteger& DividedByEq(const NativeInteger& b) {
		if( b.m_value == 0 )
			PALISADE_THROW( lbcrypto::math_error, "Divide by zero");
		this->m_value /= b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
331 332 333 334 335 336
		return *this;
	}

	//modular arithmetic operations

	/**
Gerard Ryan's avatar
Gerard Ryan committed
337
	 * returns the modulus with respect to the input value
Gerard Ryan's avatar
Gerard Ryan committed
338
	 *
Gerard Ryan's avatar
Gerard Ryan committed
339
	 * @param modulus is value of the modulus to perform
Gerard Ryan's avatar
Gerard Ryan committed
340 341 342 343 344 345
	 * @return NativeInteger that is the result of the modulus operation.
	 */
	NativeInteger Mod(const NativeInteger& modulus) const {
		return m_value % modulus.m_value;
	}

Gerard Ryan's avatar
Gerard Ryan committed
346 347 348 349 350 351 352 353 354 355 356
	/**
	 * performs %=
	 *
	 * @param modulus is value of the modulus to perform
	 * @return NativeInteger that is the result of the modulus operation.
	 */
	const NativeInteger& ModEq(const NativeInteger& modulus) {
		m_value %= modulus.m_value;
		return *this;
	}

Gerard Ryan's avatar
Gerard Ryan committed
357 358
	/**
	 * returns the modulus with respect to the input value.
Gerard Ryan's avatar
Gerard Ryan committed
359
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
360 361 362 363 364 365 366 367 368 369 370
	 *
	 * @param modulus is the modulus to perform.
	 * @param mu is the Barrett value.
	 * @return is the result of the modulus operation.
	 */
	NativeInteger ModBarrett(const NativeInteger& modulus, const NativeInteger& mu) const {
		return this->m_value%modulus.m_value;
	}

	/**
	* returns the modulus with respect to the input value - In place version.
Gerard Ryan's avatar
Gerard Ryan committed
371
	* Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
372 373 374 375 376 377 378 379 380 381 382 383
	*
	* @param modulus is the modulus to perform.
	* @param mu is the Barrett value.
	* @return is the result of the modulus operation.
	*/
	void ModBarrettInPlace(const NativeInteger& modulus, const NativeInteger& mu) {
		this->m_value %= modulus.m_value;
		return;
	}

	/**
	 * returns the modulus with respect to the input value.
Gerard Ryan's avatar
Gerard Ryan committed
384
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448
	 *
	 * @param modulus is the modulus to perform operations with.
	 * @param mu_arr is an array of the Barrett values of length BARRETT_LEVELS.
	 * @return result of the modulus operation.
	 */
	NativeInteger ModBarrett(const NativeInteger& modulus, const NativeInteger mu_arr[BARRETT_LEVELS+1]) const {
		return this->m_value%modulus.m_value;
	}

	/**
	 * returns the modulus inverse with respect to the input value.
	 *
	 * @param modulus is the modulus to perform.
	 * @return result of the modulus inverse operation.
	 */
	NativeInteger ModInverse(const NativeInteger& mod) const {

		uint_type result = 0;
		uint_type modulus = mod.m_value;

		std::vector<uint_type> mods;
		std::vector<uint_type> quotient;
		mods.push_back(modulus);
		if (this->m_value > modulus)
			mods.push_back(this->m_value%modulus);
		else
			mods.push_back(this->m_value);

		uint_type first(mods[0]);
		uint_type second(mods[1]);
		if(mods[1]==1){
			result = 1;
			return result;
		}

		//Zero does not have a ModInverse
		if(second == 0) {
			throw std::logic_error("Zero does not have a ModInverse");
		}


		//NORTH ALGORITHM
		while(true){
			mods.push_back(first%second);
			quotient.push_back(first/second);
			if(mods.back()==1)
				break;
			if(mods.back()==0){
				std::string msg = std::to_string(m_value) + " does not have a ModInverse using " + std::to_string(modulus);
				throw std::logic_error(msg);
			}

			first = second;
			second = mods.back();
		}

		mods.clear();
		mods.push_back(0);
		mods.push_back(1);

		first = mods[0];
		second = mods[1];

		//SOUTH ALGORITHM
Gerard Ryan's avatar
Gerard Ryan committed
449
		for(int i=quotient.size()-1;i>=0;i--){
Gerard Ryan's avatar
Gerard Ryan committed
450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
			mods.push_back(quotient[i]*second + first);
			first = second;
			second = mods.back();
		}


		if(quotient.size()%2==1){
			result = (modulus - mods.back());
		}
		else{
			result = mods.back();
		}

		return result;
	}

	/**
	 * Scalar modular addition.
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus addition operation.
	 */
	NativeInteger ModAdd(const NativeInteger& b, const NativeInteger& modulus) const {
		Duint_type modsum = (Duint_type)m_value;
		modsum += b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
476 477
		if (modsum >= modulus.m_value)
			modsum %= modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
478 479 480
		return (uint_type)modsum;
	}

Gerard Ryan's avatar
Gerard Ryan committed
481 482 483 484 485 486 487 488 489 490
	/**
	 * Scalar modular addition.
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus addition operation.
	 */
	const NativeInteger& ModAddEq(const NativeInteger& b, const NativeInteger& modulus) {
		Duint_type modsum = (Duint_type)m_value;
		modsum += b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
491 492
		if (modsum >= modulus.m_value)
			modsum %= modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
493 494 495
		this->m_value = (uint_type)modsum;
		return *this;
	}
Gerard Ryan's avatar
Gerard Ryan committed
496

Gerard Ryan's avatar
Gerard Ryan committed
497 498 499 500 501 502 503
	/**
	 * Fast scalar modular addition. Minimizes the number of modulo reduction operations.
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus addition operation.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
504 505 506
	inline NativeInteger ModAddFast(const NativeInteger& b, const NativeInteger& modulus) const {
		Duint_type modsum = (Duint_type)m_value;
		modsum += b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
507 508
		if (modsum >= modulus.m_value)
			modsum %= modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
509 510 511
		return (uint_type)modsum;
	}

Gerard Ryan's avatar
Gerard Ryan committed
512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535
	/**
	 * In-place Fast scalar modular addition. Minimizes the number of modulo reduction operations.
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus addition operation.
	 */
	const NativeInteger& ModAddFastEq(const NativeInteger& b, const NativeInteger& modulus) {
		Duint_type modsum = (Duint_type)m_value;
		modsum += b.m_value;
		if (modsum >= modulus.m_value)
			modsum %= modulus.m_value;
		this->m_value = (uint_type)modsum;
		return *this;
	}

	/**
	 * Fast scalar modular addition. NTL-optimized version.
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus addition operation.
	 */
	NativeInteger ModAddFastOptimized(const NativeInteger& b, const NativeInteger& modulus) const {
Gerard Ryan's avatar
Gerard Ryan committed
536 537 538
#if NTL_BITS_PER_LONG==64
		return (uint_type)NTL::AddMod(this->m_value,b.m_value,modulus.m_value);
#else
Gerard Ryan's avatar
Gerard Ryan committed
539 540 541 542 543
		Duint_type modsum = (Duint_type)m_value;
		modsum += b.m_value;
		if (modsum >= modulus.m_value)
			modsum %= modulus.m_value;
		return (uint_type)modsum;
Gerard Ryan's avatar
Gerard Ryan committed
544
#endif
Gerard Ryan's avatar
Gerard Ryan committed
545 546 547 548 549 550 551 552 553 554
	}

	/**
	 * In-place fast scalar modular addition. NTL-optimized version.
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus addition operation.
	 */
	const NativeInteger& ModAddFastOptimizedEq(const NativeInteger& b, const NativeInteger& modulus) {
Gerard Ryan's avatar
Gerard Ryan committed
555 556 557
#if NTL_BITS_PER_LONG==64
		this->m_value = (uint_type)NTL::AddMod(this->m_value,b.m_value,modulus.m_value);
#else
Gerard Ryan's avatar
Gerard Ryan committed
558 559 560 561 562
		Duint_type modsum = (Duint_type)m_value;
		modsum += b.m_value;
		if (modsum >= modulus.m_value)
			modsum %= modulus.m_value;
		this->m_value = (uint_type)modsum;
Gerard Ryan's avatar
Gerard Ryan committed
563
#endif
Gerard Ryan's avatar
Gerard Ryan committed
564 565
		return *this;
	}
Gerard Ryan's avatar
Gerard Ryan committed
566 567 568

	/**
	 * Modular addition where Barrett modulo reduction is used.
Gerard Ryan's avatar
Gerard Ryan committed
569
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
570 571 572 573 574 575 576 577 578 579 580 581
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @param mu_arr is an array of the Barrett values of length BARRETT_LEVELS.
	 * @return is the result of the modulus addition operation.
	 */
	NativeInteger ModBarrettAdd(const NativeInteger& b, const NativeInteger& modulus,const NativeInteger mu_arr[BARRETT_LEVELS]) const {
		return this->Plus(b).ModBarrett(modulus,mu_arr);
	}

	/**
	 * Modular addition where Barrett modulo reduction is used.
Gerard Ryan's avatar
Gerard Ryan committed
582
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
	 *
	 * @param &b is the scalar to add.
	 * @param modulus is the modulus to perform operations with.
	 * @param mu is one precomputed Barrett value.
	 * @return is the result of the modulus addition operation.
	 */
	NativeInteger ModBarrettAdd(const NativeInteger& b, const NativeInteger& modulus,const NativeInteger& mu) const {
		return this->Plus(b).ModBarrett(modulus,mu);
	}

	/**
	 * Scalar modular subtraction.
	 *
	 * @param &b is the scalar to subtract.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus subtraction operation.
	 */
	NativeInteger ModSub(const NativeInteger& b, const NativeInteger& modulus) const {
Gerard Ryan's avatar
Gerard Ryan committed
601 602 603
		Duint_type av = m_value;
		Duint_type bv = b.m_value;
		Duint_type mod = modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
604 605

		//reduce this to a value lower than modulus
Gerard Ryan's avatar
Gerard Ryan committed
606
		if(av >= mod) {
Gerard Ryan's avatar
Gerard Ryan committed
607 608 609
			av %= mod;
		}
		//reduce b to a value lower than modulus
Gerard Ryan's avatar
Gerard Ryan committed
610
		if(bv >= mod){
Gerard Ryan's avatar
Gerard Ryan committed
611 612 613 614
			bv %= mod;
		}

		if(av >= bv){
Gerard Ryan's avatar
Gerard Ryan committed
615
			return uint_type((av - bv) % mod);
Gerard Ryan's avatar
Gerard Ryan committed
616 617
		}
		else{
Gerard Ryan's avatar
Gerard Ryan committed
618
			return uint_type((av + mod) - bv);
Gerard Ryan's avatar
Gerard Ryan committed
619 620
		}
	}
Gerard Ryan's avatar
Gerard Ryan committed
621 622 623 624 625 626 627 628 629

	/**
	 * Scalar modular subtraction.
	 *
	 * @param &b is the scalar to subtract.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus subtraction operation.
	 */
	const NativeInteger& ModSubEq(const NativeInteger& b, const NativeInteger& modulus) {
Gerard Ryan's avatar
Gerard Ryan committed
630 631
		Duint_type bv = b.m_value;
		Duint_type mod = modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
632 633

		//reduce this to a value lower than modulus
Gerard Ryan's avatar
Gerard Ryan committed
634
		if(m_value >= mod) {
Gerard Ryan's avatar
Gerard Ryan committed
635 636 637
			m_value %= mod;
		}
		//reduce b to a value lower than modulus
Gerard Ryan's avatar
Gerard Ryan committed
638
		if(bv >= mod){
Gerard Ryan's avatar
Gerard Ryan committed
639 640 641 642
			bv %= mod;
		}

		if(m_value >= bv){
Gerard Ryan's avatar
Gerard Ryan committed
643
			m_value = uint_type((m_value - bv) % mod);
Gerard Ryan's avatar
Gerard Ryan committed
644 645
		}
		else{
Gerard Ryan's avatar
Gerard Ryan committed
646
			m_value = uint_type((m_value + mod) - bv);
Gerard Ryan's avatar
Gerard Ryan committed
647 648 649 650 651 652
		}

		return *this;
	}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
653
	 * Fast scalar modular subtraction. Assumes both arguments are in [0,modulus-1].
Gerard Ryan's avatar
Gerard Ryan committed
654 655 656 657 658
	 *
	 * @param &b is the scalar to subtract.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus subtraction operation.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
659
	inline NativeInteger ModSubFast(const NativeInteger& b, const NativeInteger& modulus) const {
Gerard Ryan's avatar
Gerard Ryan committed
660 661
		if(m_value >= b.m_value){
			return uint_type(m_value - b.m_value);
Gerard Ryan's avatar
Gerard Ryan committed
662 663
		}
		else{
Gerard Ryan's avatar
Gerard Ryan committed
664
			return uint_type((m_value + modulus.m_value) - b.m_value);
Gerard Ryan's avatar
Gerard Ryan committed
665 666 667
		}
	}

Gerard Ryan's avatar
Gerard Ryan committed
668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683
	/**
	 * Scalar modular subtraction (in-place version). Assumes both arguments are in [0,modulus-1].
	 *
	 * @param &b is the scalar to subtract.
	 * @param modulus is the modulus to perform operations with.
	 * @return result of the modulus subtraction operation.
	 */
	const NativeInteger& ModSubFastEq(const NativeInteger& b, const NativeInteger& modulus) {
		if(m_value >= b.m_value){
			m_value -= b.m_value;
		}
		else{
			m_value += (modulus.m_value - b.m_value);
		}
		return *this;
	}
Gerard Ryan's avatar
Gerard Ryan committed
684 685 686

	/**
	 * Scalar modular subtraction where Barrett modular reduction is used.
Gerard Ryan's avatar
Gerard Ryan committed
687
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
688 689 690 691 692 693 694 695 696 697 698 699
	 *
	 * @param &b is the scalar to subtract.
	 * @param modulus is the modulus to perform operations with.
	 * @param mu is the Barrett value.
	 * @return is the result of the modulus subtraction operation.
	 */
	NativeInteger ModBarrettSub(const NativeInteger& b, const NativeInteger& modulus, const NativeInteger& mu) const {
		return this->ModSub(b,modulus);
	}

	/**
	 * Scalar modular subtraction where Barrett modular reduction is used.
Gerard Ryan's avatar
Gerard Ryan committed
700
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721
	 *
	 * @param b is the scalar to subtract.
	 * @param modulus is the modulus to perform operations with.
	 * @param mu_arr is an array of the Barrett values of length BARRETT_LEVELS.
	 * @return is the result of the modulus subtraction operation.
	 */
	NativeInteger ModBarrettSub(const NativeInteger& b, const NativeInteger& modulus,const NativeInteger mu_arr[BARRETT_LEVELS]) const {
		return this->ModSub(b,modulus);
	}

	/**
	 * Scalar modulus multiplication.
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus multiplication operation.
	 */
	NativeInteger ModMul(const NativeInteger& b, const NativeInteger& modulus) const {
		Duint_type av = m_value;
		Duint_type bv = b.m_value;

Gerard Ryan's avatar
Gerard Ryan committed
722 723
		if( av >= modulus.m_value ) av = av%modulus.m_value;
		if( bv >= modulus.m_value ) bv = bv%modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
724

Gerard Ryan's avatar
Gerard Ryan committed
725
		return uint_type((av*bv)%modulus.m_value);
Gerard Ryan's avatar
Gerard Ryan committed
726 727
	}

Gerard Ryan's avatar
Gerard Ryan committed
728 729 730 731 732 733 734 735
	/**
	 * Scalar modulus multiplication.
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus multiplication operation.
	 */
	const NativeInteger& ModMulEq(const NativeInteger& b, const NativeInteger& modulus) {
Gerard Ryan's avatar
Gerard Ryan committed
736
		Duint_type av = m_value;
Gerard Ryan's avatar
Gerard Ryan committed
737 738
		Duint_type bv = b.m_value;

Gerard Ryan's avatar
Gerard Ryan committed
739 740
		if( av >= modulus.m_value ) av = av%modulus.m_value;
		if( bv >= modulus.m_value ) bv = bv%modulus.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
741

Gerard Ryan's avatar
Gerard Ryan committed
742
		this->m_value = uint_type((av*=bv)%=modulus.m_value);
Gerard Ryan's avatar
Gerard Ryan committed
743 744 745 746

		return *this;
	}

Gerard Ryan's avatar
Gerard Ryan committed
747 748 749 750 751 752 753 754 755 756 757
	/**
	 * Scalar modulus multiplication. Fast version, assumes inputs are
	 * already < modulus. 
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus multiplication operation.
	 */
	NativeInteger ModMulFast(const NativeInteger& b, const NativeInteger& modulus) const {
		Duint_type av = m_value;
		Duint_type bv = b.m_value;
Gerard Ryan's avatar
Gerard Ryan committed
758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775

		return (uint_type)((av*bv)%modulus.m_value);
	}

	/**
	 * Scalar modulus multiplication. Optimized NTL version.
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus multiplication operation.
	 */
	NativeInteger ModMulFastOptimized(const NativeInteger& b, const NativeInteger& modulus) const {
#if NTL_BITS_PER_LONG==64
		return (uint_type)NTL::MulMod(this->m_value,b.m_value,modulus.m_value);
#else
		Duint_type av = m_value;
		Duint_type bv = b.m_value;

Gerard Ryan's avatar
Gerard Ryan committed
776
		return (uint_type)((av*bv)%modulus.m_value);
Gerard Ryan's avatar
Gerard Ryan committed
777 778
#endif

Gerard Ryan's avatar
Gerard Ryan committed
779 780
	}

Gerard Ryan's avatar
Gerard Ryan committed
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796
	/**
	 * Scalar modulus multiplication.
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus multiplication operation.
	 */
	const NativeInteger& ModMulFastEq(const NativeInteger& b, const NativeInteger& modulus) {
		Duint_type av = m_value;
		Duint_type bv = b.m_value;

		this->m_value = (uint_type)((av*=bv)%=modulus.m_value);

		return *this;
	}

Gerard Ryan's avatar
Gerard Ryan committed
797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870
	/**
	 * In-place scalar modulus multiplication. Optimized NTL version.
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus multiplication operation.
	 */
	const NativeInteger& ModMulFastEqOptimized(const NativeInteger& b, const NativeInteger& modulus) {
#if NTL_BITS_PER_LONG==64
		this->m_value = (uint_type)NTL::MulMod(this->m_value,b.m_value,modulus.m_value);
#else
		Duint_type av = m_value;
		Duint_type bv = b.m_value;

		this->m_value = (uint_type)((av*=bv)%=modulus.m_value);
#endif
		return *this;
	}

	/**
	 * NTL-optimized modular multiplication using a precomputation for the multiplicand
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @param &bInv NTL precomputation for b.
	 * @return is the result of the modulus multiplication operation.
	 */
	NativeInteger ModMulPreconOptimized(const NativeInteger& b, const NativeInteger& modulus, const NativeInteger& bInv) const {
#if NTL_BITS_PER_LONG==64
		return (uint_type)NTL::MulModPrecon(this->m_value,b.m_value,modulus.m_value,bInv.m_value);
#else
		Duint_type av = m_value;
		Duint_type bv = b.m_value;

		return (uint_type)((av*bv)%modulus.m_value);
#endif
	}

	/**
	 * Scalar modulus multiplication.
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @param &bInv NTL precomputation for b.
	 * @return is the result of the modulus multiplication operation.
	 */
	const NativeInteger& ModMulPreconOptimizedEq(const NativeInteger& b, const NativeInteger& modulus, const NativeInteger& bInv) {
#if NTL_BITS_PER_LONG==64
		this->m_value = (uint_type)NTL::MulModPrecon(this->m_value,b.m_value,modulus.m_value,bInv.m_value);
#else
		Duint_type av = m_value;
		Duint_type bv = b.m_value;

		this->m_value = (uint_type)((av*=bv)%=modulus.m_value);
		//this->m_value = (uint_type)((av*bv)%modulus.m_value);
#endif
		return *this;
	}

	/**
	 * NTL precomputations for a multiplicand
	 *
	 * @param modulus is the modulus to perform operations with.
	 * @return the precomputed factor
	 */
	const NativeInteger PrepModMulPreconOptimized(const NativeInteger& modulus) const {
#if NTL_BITS_PER_LONG==64
		return (uint_type)NTL::PrepMulModPrecon(this->m_value,modulus.m_value);
#else
		return 0;
#endif
	}


Gerard Ryan's avatar
Gerard Ryan committed
871 872
	/**
	 * Scalar modular multiplication where Barrett modular reduction is used.
Gerard Ryan's avatar
Gerard Ryan committed
873
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
874 875 876 877 878 879 880 881 882 883 884 885
	 *
	 * @param b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @param mu is the precomputed Barrett value.
	 * @return is the result of the modulus multiplication operation.
	 */
	NativeInteger ModBarrettMul(const NativeInteger& b, const NativeInteger& modulus,const NativeInteger& mu) const {
		return this->ModMul(b,modulus);
	}

	/**
	* Scalar modular multiplication where Barrett modular reduction is used - In-place version
Gerard Ryan's avatar
Gerard Ryan committed
886
	* Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
887 888 889 890 891 892 893
	*
	* @param b is the scalar to multiply.
	* @param modulus is the modulus to perform operations with.
	* @param mu is the precomputed Barrett value.
	* @return is the result of the modulus multiplication operation.
	*/
	void ModBarrettMulInPlace(const NativeInteger& b, const NativeInteger& modulus, const NativeInteger& mu) {
Gerard Ryan's avatar
Gerard Ryan committed
894
		*this = this->ModMulFast(b,modulus);
Gerard Ryan's avatar
Gerard Ryan committed
895 896 897 898 899
		return;
	}

	/**
	 * Scalar modular multiplication where Barrett modular reduction is used.
Gerard Ryan's avatar
Gerard Ryan committed
900
	 * Included here for compatibility with backend 2.
Gerard Ryan's avatar
Gerard Ryan committed
901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928
	 *
	 * @param &b is the scalar to multiply.
	 * @param modulus is the modulus to perform operations with.
	 * @param mu_arr is an array of the Barrett values of length BARRETT_LEVELS.
	 * @return is the result of the modulus multiplication operation.
	 */
	NativeInteger ModBarrettMul(const NativeInteger& b, const NativeInteger& modulus,const NativeInteger mu_arr[BARRETT_LEVELS]) const {
		return this->ModMul(b,modulus);
	}

	/**
	 * Scalar modular exponentiation. Square-and-multiply algorithm is used.
	 *
	 * @param &b is the scalar to exponentiate.
	 * @param modulus is the modulus to perform operations with.
	 * @return is the result of the modulus exponentiation operation.
	 */
	NativeInteger ModExp(const NativeInteger& b, const NativeInteger& mod) const {
		Duint_type exp = b.m_value;
		Duint_type product = 1;
		Duint_type modulus = mod.m_value;
		Duint_type mid = m_value % modulus;

		while( true ) {
			if( exp%2 == 1 )
				product = product * mid;

			//running product is calculated
Gerard Ryan's avatar
Gerard Ryan committed
929
			if(product >= modulus){
Gerard Ryan's avatar
Gerard Ryan committed
930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945
				product = product % modulus;
			}

			//divide by 2 and check even to odd to find bit value
			exp >>= 1;
			if(exp == 0)
				break;

			//mid calculates mid^2%q
			mid = mid*mid;

			mid = mid % modulus;
		}
		return (uint_type)product;
	}

Gerard Ryan's avatar
Gerard Ryan committed
946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987
	//Shift Operators

	/**
	 * Left shift operator
	 * @param shift is the amount to shift of type usshort.
	 * @return the object of type NativeInteger
	 */
	NativeInteger  LShift(usshort shift) const {
		return m_value << shift;
	}

	/**
	 * Left shift operator uses in-place algorithm and operates on the same variable.
	 *
	 * @param shift is the amount to shift of type usshort.
	 * @return the object of type NativeInteger
	 */
	const NativeInteger&  LShiftEq(usshort shift) {
		m_value <<= shift;
		return *this;
	}

	/**
	 * Right shift operator
	 * @param shift is the amount to shift of type usshort.
	 * @return the object of type NativeInteger
	 */
	NativeInteger  RShift(usshort shift) const {
		return m_value >> shift;
	}

	/**
	 * Right shift operator uses in-place algorithm and operates on the same variable.
	 *
	 * @param shift is the amount to shift of type usshort.
	 * @return the object of type NativeInteger
	 */
	const NativeInteger&  RShiftEq(usshort shift) {
		m_value >>= shift;
		return *this;
	}

Gerard Ryan's avatar
Gerard Ryan committed
988 989 990 991 992 993
	/**
	 * Stores the based 10 equivalent/Decimal value of the NativeInteger in a string object and returns it.
	 *
	 * @return value of this NativeInteger in base 10 represented as a string.
	 */
	const std::string ToString() const {
Gerard Ryan's avatar
Gerard Ryan committed
994
		return std::to_string(m_value);
Gerard Ryan's avatar
Gerard Ryan committed
995
	}
Gerard Ryan's avatar
Gerard Ryan committed
996 997 998 999 1000 1001 1002 1003 1004 1005 1006
#if 0
	template <typename I> std::string n2hexstr(const I w, size_t hex_len = sizeof(I)<<(8/4)) const{
	  //note the 8 above is the sizeof byte and the 4 is log2(16) as are the 4's below
	  //and the 0f below is the 4 bits. each of the following templates follow this pattern
	  static const char* digits = "0123456789ABCDEF";

	  std::string rc(hex_len,'0');
	  for (size_t i=0, j=(hex_len-1)*4 ; i<hex_len; ++i,j-=4)
	    rc[i] = digits[(w>>j) & 0x0f];
	  return rc;
	}
Gerard Ryan's avatar
Gerard Ryan committed
1007

Gerard Ryan's avatar
Gerard Ryan committed
1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
	template <typename I> std::string n2_32str(const I w, size_t hex_len = ceil(sizeof(I)*(8/5.0))) const{
	  static const char* digits = "0123456789ABCDEFGHIJKLMNOPQRSTUV";
	  //WXYZabcdefghijklmnopqrstuvwxyz@#
					 std::string rc(hex_len,'0');
	  for (size_t i=0, j=(hex_len-1)*5 ; i<hex_len; ++i,j-=5)
	    rc[i] = digits[(w>>j) & 0x1f];
	  return rc;
	}
	template <typename I> std::string n2_64str(const I w, size_t hex_len = ceil(sizeof(I)*(8/6.0))-1) const{
	  static const char* digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@#";
					 std::string rc(hex_len,'0');
	  for (size_t i=0, j=(hex_len-1)*6 ; i<hex_len; ++i,j-=6)
	    rc[i] = digits[(w>>j) & 0x3f];
	  return rc;
	}
#endif
	//this function coverts the type I into 128bit characters. Note they are nonprintable
	template <typename I> std::string n2_128str(const I w, size_t ohex_len = ceil(sizeof(I)*(8/7.0))) const{
	  bool dbg_flag = false;
	  static unsigned char digits[128] =" ";

	  if (digits[0]==' ') { //digits is uninitialized, initialize first time around
	    //std::cout << "INITIALIZING DIGITS"<<std::endl;
	    usint firstchar = 35;
	    for (unsigned int i=0; i < 128; i++){
	      digits[i] = (char)(i+firstchar);
	    }
	  }
	  std::string rc(ohex_len,' ');
	  for (size_t i=0, j=(ohex_len-1)*7 ; i<ohex_len; ++i,j-=7){
	    DEBUGEXP(std::hex<<w);
	    DEBUGEXP(std::dec<<j);
	    DEBUGEXP(std::hex<<(w>>j));
	    DEBUGEXP(std::hex<<((w>>j) & 0x7f));
	    rc[i] = digits[(w>>j) & 0x7f];
	    DEBUGEXP(std::hex<<rc[i]);
	  }
	  return rc;
	}
	    // note that for efficiency, we use [De]Serialize[To|From]String when serializing
Gerard Ryan's avatar
Gerard Ryan committed
1048 1049 1050 1051
	// BigVectors, and [De]Serialize otherwise (to work the same as all
	// other serialized objects.
	// Serialize using the modulus; convert value to signed, then serialize to string
	const std::string SerializeToString(const NativeInteger& modulus = 0) const {
Gerard Ryan's avatar
Gerard Ryan committed
1052 1053 1054 1055 1056
	  //numbers are straight unsigned int ==> base 128
	  bool dbg_flag = false;
        #if 0 //old slow way
	  // numbers go from high to low -1, -2, ... +modulus/2, modulus/2 - 1, ... ,1, 0
	    bool isneg = false;
Gerard Ryan's avatar
Gerard Ryan committed
1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
		NativeInteger signedVal;
		if( modulus.m_value == 0 || m_value < modulus.m_value/2 )
			signedVal = m_value;
		else {
			signedVal = modulus.m_value - m_value;
			isneg = true;
		}

		std::string ser = "";
		if( isneg ) ser += "-";
		unsigned char len = signedVal.GetMSB();
		ser += lbcrypto::value_to_base64(len);
		for( int i=len; i>0; i-=6 )
			ser += lbcrypto::value_to_base64(signedVal.Get6BitsAtIndex(i));
		return ser;
Gerard Ryan's avatar
Gerard Ryan committed
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114
        #else
		//std::string ser(n2hexstr<uint_type>(m_value)+"|");
		//std::string ser(n2_64str<uint_type>(m_value)+"|");
		DEBUG("---");
		std::string ser(n2_128str<uint_type>(m_value));
		DEBUGEXP(m_value);
		DEBUGEXP(ser);
		return ser;

        #endif
	}

	//this function coverts string of 128bit characters into the type I 
        template <typename I> const char* str128_2n( I* w, const char * &s, size_t ohex_len = ceil(sizeof(I)*(8/7.0))) {
	  static unsigned char digits[128] =" ";
	  bool dbg_flag = false;
	  usint firstchar = 35;
	    
	  if (digits[0]==' ') { //digits is uninitialized, initialize first time around
	    //std::cout << "INITIALIZING DIGITS"<<std::endl;
	    for (unsigned int i=0; i < 128; i++){
	       digits[i] = (char)(i+firstchar);
	    }
	  }

	  DEBUGEXP(*w);
	  *w=0;
	  DEBUGEXP(*w);	  
	  I d(0);
	  for (size_t i=0, j=(ohex_len-1)*7 ; i<ohex_len; ++i,j-=7) {
	    //d = (unsigned char)s[ohex_len-i-1] - firstchar;
	    d = (unsigned char)s[i] - firstchar;
	    DEBUGEXP(std::hex<<(unsigned int)d);
	    DEBUGEXP(std::dec<<j);
	    DEBUGEXP(std::hex<<(d<<j));
	    *w|= (d<<j);
	    
	    DEBUGEXP(std::hex<<w);	    
	  }
	  DEBUGEXP(s);
	  s+=ohex_len;
	  DEBUGEXP(s);
	  return s;
Gerard Ryan's avatar
Gerard Ryan committed
1115 1116
	}

Gerard Ryan's avatar
Gerard Ryan committed
1117 1118
	//deserialize from string
	const char * DeserializeFromString(const char * str, const NativeInteger& modulus = 0) {
Gerard Ryan's avatar
Gerard Ryan committed
1119
        #if 0 //old slow way
Gerard Ryan's avatar
Gerard Ryan committed
1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140
		bool isneg = false;
		if( *str == '-' ) {
			++str;
			isneg = true;
		}
		usint len = lbcrypto::base64_to_value(*str);
		uint64_t value = 0;

		for( ; len > 6 ; len -= 6 )
			value = (value<<6)|lbcrypto::base64_to_value(*++str);

		if( len )
			value = (value<<len) | (lbcrypto::base64_to_value(*++str));

		str++;

		if( isneg )
			value = (modulus.m_value - value);

		m_value = value;
		return str;
Gerard Ryan's avatar
Gerard Ryan committed
1141 1142 1143 1144 1145 1146 1147 1148 1149
           #else		

		bool dbg_flag = false;
		DEBUG("===");
		DEBUGEXP(m_value);
		DEBUGEXP(str);
		
		return str128_2n<uint_type>(&m_value, str);
           #endif
Gerard Ryan's avatar
Gerard Ryan committed
1150
	}
Gerard Ryan's avatar
Gerard Ryan committed
1151 1152 1153 1154 1155 1156 1157
	/**
	* Serialize the object into a Serialized
	* @param serObj is used to store the serialized result. It MUST be a rapidjson Object (SetObject());
	* @return true if successfully serialized
	*/
	bool Serialize(lbcrypto::Serialized* serObj) const{

Gerard Ryan's avatar
Gerard Ryan committed
1158 1159 1160 1161
	  if( !serObj->IsObject() ){
	    serObj->SetObject();
	  }

Gerard Ryan's avatar
Gerard Ryan committed
1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198
	  
	  lbcrypto::SerialItem bbiMap(rapidjson::kObjectType);
	  
	  bbiMap.AddMember("IntegerType", IntegerTypeName(), serObj->GetAllocator());
	  bbiMap.AddMember("Value", this->ToString(), serObj->GetAllocator());
	  serObj->AddMember("BigIntegerImpl", bbiMap, serObj->GetAllocator());
	  return true;
	  
	};
	
	/**
	* Populate the object from the deserialization of the Serialized
	* @param serObj contains the serialized object
	* @return true on success
	*/
	bool Deserialize(const lbcrypto::Serialized& serObj){
	  //find the outer name
	  lbcrypto::Serialized::ConstMemberIterator mIter = serObj.FindMember("BigIntegerImpl");
	  if( mIter == serObj.MemberEnd() )//not found, so fail
	    return false;
	  
	  lbcrypto::SerialItem::ConstMemberIterator vIt; //interator within name
	  
	  //is this the correct integer type?
	  if( (vIt = mIter->value.FindMember("IntegerType")) == mIter->value.MemberEnd() )
	    return false;
	  if( IntegerTypeName() != vIt->value.GetString() )
	    return false;
	  
	  //find the value
	  if( (vIt = mIter->value.FindMember("Value")) == mIter->value.MemberEnd() )
	    return false;
	  //assign the value found
	  AssignVal(vIt->value.GetString());
	  return true;
	};
	
Gerard Ryan's avatar
Gerard Ryan committed
1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209
    static const std::string IntegerTypeName() { return "NativeI"; }

	/**
	 * Get the number of digits using a specific base - support for arbitrary base may be needed.
	 *
	 * @param base is the base with which to determine length in.
	 * @return the length of the representation in a specific base.
	 */
	usint GetLengthForBase(usint base) const {return GetMSB();}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
1210 1211 1212 1213 1214 1215
	* Get a specific digit at "digit" index; big integer is seen as an array of digits, where a 0 <= digit < base
	*
	* @param index is the "digit" index of the requested digit
	* @param base is the base with which to determine length in.
	* @return is the requested digit
	*/
Gerard Ryan's avatar
Gerard Ryan committed
1216 1217
	usint GetDigitAtIndexForBase(usint index, usint base) const {

Gerard Ryan's avatar
Gerard Ryan committed
1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228
		usint DigitLen = ceil(log2(base));

		usint digit = 0;
		usint newIndex = 1 + (index - 1)*DigitLen;
		for (usint i = 1; i < base; i = i * 2)
		{
			digit += GetBitAtIndex(newIndex)*i;
			newIndex++;
		}
		return digit;

Gerard Ryan's avatar
Gerard Ryan committed
1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256
	}

	/**
	 * Convert a string representation of a binary number to a decimal BigInteger.
	 *
	 * @param bitString the binary num in string.
	 * @return the binary number represented as a big binary int.
	 */
	static NativeInteger BitStringToBigInteger(const std::string& bitString) {
		if( bitString.length() > m_uintBitLength ) {
			throw std::logic_error("Bit string is too long to fit in a native_int");
		}

		uint_type v = 0;
		for( size_t i=0 ; i < bitString.length() ; i++ ) {
			int n = bitString[i] - '0';
			if( n < 0 || n > 1 ) {
				throw std::logic_error("Bit string must contain only 0 or 1");
			}

			v <<= 1;
			v |= n;
		}

		return v;
	}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
1257
	 * Exponentiation. Returns x^p
Gerard Ryan's avatar
Gerard Ryan committed
1258 1259
	 *
	 * @param p the exponent.
Gerard Ryan's avatar
Gerard Ryan committed
1260
	 * @return the integer x^p.
Gerard Ryan's avatar
Gerard Ryan committed
1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
	 */
	NativeInteger Exp(usint p) const {
		if (p == 0) return 1;
		if (p == 1) return *this;

		NativeInteger tmp = (*this).Exp(p/2);
		if (p%2 == 0) return tmp * tmp;
		else return tmp * tmp * (*this);
	}

	/**
Gerard Ryan's avatar
Gerard Ryan committed
1272
	 * Multiply and Rounding operation. Returns [x*p/q] where [] is the rounding operation.
Gerard Ryan's avatar
Gerard Ryan committed
1273 1274 1275 1276 1277 1278 1279 1280 1281 1282
	 *
	 * @param p is the numerator to be multiplied.
	 * @param q is the denominator to be divided.
	 * @return the result of multiply and round.
	 */
	NativeInteger MultiplyAndRound(const NativeInteger &p, const NativeInteger &q) const {
		NativeInteger ans = m_value*p.m_value;
		return ans.DivideAndRound(q);
	}

Gerard Ryan's avatar
Gerard Ryan committed
1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310
	/**
	 * Computes the quotient of x*p/q, where x,p,q are all uint_type numbers, x is the current value; uses Duint_type arithmetic
	 *
	 * @param p is the multiplicand
	 * @param q is the divisor
	 * @return the quotient
	 */
	NativeInteger MultiplyAndDivideQuotient(const NativeInteger &p, const NativeInteger &q) const {
		Duint_type xD = m_value;
		Duint_type pD = p.m_value;
		Duint_type qD = q.m_value;
		return (uint_type)(xD*pD/qD);
	}

	/**
	 * Computes the remainder of x*p/q, where x,p,q are all uint_type numbers, x is the current value; uses Duint_type arithmetic
	 *
	 * @param p is the multiplicand
	 * @param q is the divisor
	 * @return the remainder
	 */
	NativeInteger MultiplyAndDivideRemainder(const NativeInteger &p, const NativeInteger &q) const {
		Duint_type xD = m_value;
		Duint_type pD = p.m_value;
		Duint_type qD = q.m_value;
		return (uint_type)((xD*pD)%qD);
	}

Gerard Ryan's avatar
Gerard Ryan committed
1311 1312 1313 1314 1315 1316 1317 1318 1319
	/**
	 * Divide and Rounding operation on a BigInteger x. Returns [x/q] where [] is the rounding operation.
	 *
	 * @param q is the denominator to be divided.
	 * @return the result of divide and round.
	 */
	NativeInteger DivideAndRound(const NativeInteger &q) const {

		if( q == 0 )
Gerard Ryan's avatar
Gerard Ryan committed
1320
			PALISADE_THROW( lbcrypto::math_error, "Divide by zero");
Gerard Ryan's avatar
Gerard Ryan committed
1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342

		uint_type ans = m_value/q.m_value;
		uint_type rem = m_value%q.m_value;
		uint_type halfQ = q.m_value >> 1;

		if (!(rem <= halfQ)) {
			ans += 1;
		}

		return ans;
	}

	//overloaded binary operators based on integer arithmetic and comparison functions
	NativeInteger operator-() const { return NativeInteger(0).Minus(*this); }

	/**
	 * Console output operation.
	 *
	 * @param os is the std ostream object.
	 * @param ptr_obj is NativeInteger to be printed.
	 * @return is the ostream object.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
1343
	friend std::ostream& operator<<(std::ostream& os, const NativeInteger &ptr_obj) {
Gerard Ryan's avatar
Gerard Ryan committed
1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377
		os << ptr_obj.m_value;
		return os;
	}

	/**
	 * Gets the bit at the specified index.
	 *
	 * @param index is the index of the bit to get.
	 * @return resulting bit.
	 */
	uschar GetBitAtIndex(usint index) const {
		if(index==0) {
			throw std::logic_error("Zero index in GetBitAtIndex");
		}

		return (m_value >> (index-1)) & 0x01;
	}

	/**
	 * Gets the 6 bits at the specified index.
	 *
	 * @param index is the index of the bit to get.
	 * @return 6 bit pattern
	 */
	uschar Get6BitsAtIndex(usint index) const {
		return lbcrypto::get_6bits_atoffset(m_value, index);
	}

	/**
	 * Compares the current NativeInteger to NativeInteger a.
	 *
	 * @param a is the NativeInteger to be compared with.
	 * @return  -1 for strictly less than, 0 for equal to and 1 for strictly greater than conditons.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
1378
	int Compare(const NativeInteger& a) const {
Gerard Ryan's avatar
Gerard Ryan committed
1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389
		if( this->m_value < a.m_value )
			return -1;
		else if( this->m_value > a.m_value )
			return 1;
		return 0;
	}

	/**
	 *  Set this int to 1.
	 *  Note some compilers don't like using the ONE constant, above :(
	 */
Gerard Ryan's avatar
Gerard Ryan committed
1390
	void SetIdentity() { this->m_value = 1; };
Gerard Ryan's avatar
Gerard Ryan committed
1391 1392 1393 1394 1395

	/**
	 * A zero allocator that is called by the Matrix class.
	 * It is used to initialize a Matrix of NativeInteger objects.
	 */
Gerard Ryan's avatar
Gerard Ryan committed
1396 1397 1398 1399 1400 1401 1402 1403 1404
	static NativeInteger<uint_type> Allocator() { return 0; }

	inline bool operator==(const NativeInteger& b) {return this->m_value==b.m_value; }
	inline bool operator!=(const NativeInteger& b) {return this->m_value!=b.m_value;}

	inline bool operator> (const NativeInteger& b) {return this->m_value > b.m_value;}
	inline bool operator>=(const NativeInteger& b) {return this->m_value >= b.m_value; }
	inline bool operator< (const NativeInteger& b) {return this->m_value < b.m_value;}
	inline bool operator<=(const NativeInteger& b) {return this->m_value <= b.m_value;}
Gerard Ryan's avatar
Gerard Ryan committed
1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448

protected:

	/**
	 * Converts the string v into base-r integer where r is equal to 2^bitwidth of integral data type.
	 *
	 * @param v The input string
	 */
	void AssignVal(const std::string& str) {
		uint_type test_value = 0;
		m_value = 0;
		for( size_t i=0; i<str.length(); i++ ) {
			int v = str[i] - '0';
			if( v < 0 || v > 9 ) {
				throw std::logic_error("String contains a non-digit");
			}
			m_value *= 10;
			m_value += v;

			if( m_value < test_value ) {
				throw std::logic_error(str + " is too large to fit in this native integer object");
			}
			test_value = m_value;
		}
	}

private:

	// representation as a
	uint_type m_value;

	//variable to store the bit width of the integral data type.
	static const uschar m_uintBitLength = sizeof(uint_type)*8;

	//variable to store the maximum value of the integral data type.
	static const uint_type m_uintMax = std::numeric_limits<uint_type>::max();

	// Duint_type has double the bits in the integral data type.
	typedef typename DoubleDataType<uint_type>::T Duint_type;
};

}//namespace ends

#endif