Skip to content

Issue-38: backend cleanup

Andrey requested to merge issue-38 into master

Closes #38 (closed)

A list of changes that were made:

STRUCTURE: In all backends now methods are in following order:
// CONSTRUCTORS
// ASSIGNMENT OPERATORS
// ACCESSORS
// ARITHMETIC OPERATIONS
// MODULAR ARITHMETIC OPERATIONS
// SHIFT OPERATIONS
// COMPARE
// CONVERTERS
// OTHER FUNCTIONS
// STRINGS & STREAMS
// SERIALIZATION

METHOD NAMES:

  • Methods for modulo operations are reconsidered:

    • methods with Fast suffix - components < modulus.
    • methods with additional mu parameter - we use Barrett reduction.
    • method for multiplication with Precon suffix and bInv parameter - we use Shoup method
  • Examples for multiplication:

    • ModMul(b, mod) naive modulo multiplication
    • ModMulFast(b, mod) naive modulo multiplication with components < modulus
    • ModMul(b, mod, mu) multiplication using Barrett reduction.
    • ModMulFast(b, mod, mu) multiplication using Barrett reduction with components < modulus
    • ModMulFastPrecon(b, mod, bInv) Shoup multiplication.

IMPLEMENTATION:

  • All methods that are implemented have a variant with Eq.
  • A few methods I'm not sure in have FIXME tasks.
  • In interface.h methods MultiplyAndRound/DivideAndRound added to BigIntegerInterface
  • ComputeMu() now in interface, not in nbtheory
  • Not all methods are implemented:
    • ModMulPrecon(b, mod, bInv) we always have components smaller than modulus, so no need for this method
    • ModAddFast(b, mod, mu) seems to be same as ModAdd(b, mod, mu), so there is only ModAdd(b, mod, mu) implemented.
  • Removed modulus.GetMSB() > MAX_MODULUS_SIZE support, as we use NativeVectors only to have fast arithmetics. SetModulus() throws an exception if modulus.GetMSB() > MAX_MODULUS_SIZE. Removed all checks in other places.
  • In ckkspackedencoding.cpp line 56 changed q from 2^63-1 to 2^60-1 not to throw exception (Not sure if it is ok, but all tests works)

CLEANUP:

  • Tried to unify the comments for arithmetic methods.
  • In exp_int removed commented code and DEBUG checks.
Edited by Yuriy Polyakov

Merge request reports