niekbouman/ctbignum

Library for Multiprecision Compile-Time and Run-Time Arithmetic (including Modular Arithmetic)

ctbignum's Issues

Add text on how to refer / refer to publication

Handig om bovenaan de readme te zetten hoe mensen naar de lib kunnen refereren. Dat is dan meteen een ref naar het artikel.

Additional Benchmark comparison

The mp++ library is considered by many to be the state of the art for performant multiprecision integer arithmetic and underlies the symengine library behind the popular sympy python symbolic mathematics library.

A performance comparison to ctbugnum would be very interesting

add random element function

Add begin() and end() to big_int

Wrong value for mod_inv

I was playing with the library and I found an issue with mod_inv. You can check it with the following code:

auto p = cbn::to_big_int(115792089237316195423570985008687907853269984665640564039457584007908834671663_Z);
auto a = cbn::to_big_int(65341020041517633956166170261014086368942546761318486551877808671514674964848_Z);
std::cout << cbn::mod_inv(a, p) << std::endl;

It gives 83174505189910067536517124096019359197644205712500122884473429251816423926391 when it should be 83174505189910067536517124096019359197644205712500122884473429251812128958118

The problem seems to be the negative numbers after calling to subtract_ignore_carry. There is a check at the end of the function for t > modulus but it doesn't apply to this case.

Tracking the signs of t and newt, and applying add_ignore_carry based on them works, but it is an ugly workaround:

template <typename T, size_t N>
constexpr auto mod_inv2(big_int<N, T> a, big_int<N, T> modulus) {
  big_int<N, T> t{0};
  big_int<N, T> newt{1};
  auto r = modulus;
  auto newr = a;
  bool t_neg = false, newt_neg = false;


  while (newr != big_int<1, T>{0}) {
    auto qr = div(r, newr);
    auto tmp = t;
    auto tmp2 = partial_mul<N>(qr.quotient, newt);

    if (!t_neg && !newt_neg) {
      newt_neg = tmp2 > tmp;
    } else if (!t_neg && newt_neg) {
      newt_neg = false;
      t_neg = true;
    } else if (t_neg && !newt_neg) {
      newt_neg = true;
      t_neg = false;
    } else {
      newt_neg = tmp2 < tmp;
    }
    t = newt;
    newt = subtract_ignore_carry(tmp, tmp2);
    r = newr;
    newr = qr.remainder;
  }
  // if r > 1 then return "a is not invertible"
  if (t_neg)
    t = add_ignore_carry(t, modulus);
  return t;
}

Compiling on Fedora 36: <stdexcept> needed

Compilation fails on Fedora 36 because is needed for std::runtime_error. The following patch fixes this:

diff --git a/include/ctbignum/gcd.hpp b/include/ctbignum/gcd.hpp
index 406d6d8..bdf97cd 100644
--- a/include/ctbignum/gcd.hpp
+++ b/include/ctbignum/gcd.hpp
@@ -19,6 +19,8 @@
 #include <ctbignum/utility.hpp>
 
 #include <cstddef>
+#include <stdexcept>
+
 
 namespace cbn {
 namespace detail {

cmake should test availability of dependencies

Boost, NTL, ...

implement natural syntax for integer_sequences

Implement feature that allows us to write:
using GF25519 = decltype(Zq(2_Z ^ 255 - 19));

Untested branch in addition.hpp

Branch at this spot is not tested:
https://github.com/niekbouman/finitefield/blob/f0781afea43a5d05858fb1e22ea3c409a3f72e6b/include/ctbignum/addition.hpp#L72

I.e., replacing with if(true) passes all tests.

cmake "test" target does not build all required steps

ninja test fails when it's done on clean build dir

implement optimized reduction for mersenne / NIST-like primes

Provide non-intrusive overloads/specializations for the remainder function, for primes that come with fast reductions.

io.hpp should only include <ostream> instead of <iostream>

since it is output only and not referring to the globals (cin/cout) declared in I recommend to minimize dependency by including only.

add unit tests for relational operators

SIGSTKSZ changed to be a syscall

In file included from /usr/include/signal.h:328,
                 from /home/ilyas/projects/ctbignum/test/thirdparty/catch/catch.hpp:6456,
                 from /home/ilyas/projects/ctbignum/test/src/tests_main.cpp:13:
/home/ilyas/projects/ctbignum/test/thirdparty/catch/catch.hpp:6631:45: error: size of array ‘altStackMem’ is not an integral constant-expression
 6631 |     char FatalConditionHandler::altStackMem[SIGSTKSZ] = {};

Problem is similar to r-lib/testthat#1373.

gcc version 12.2.1

$ uname -a
Linux fedora 6.0.9-300.fc37.x86_64 #1 SMP PREEMPT_DYNAMIC Wed Nov 16 17:36:22 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

$ ldd --version
ldd (GNU libc) 2.36

Microsoft Visual C++ (latest version)

A couple of problems when compiling in MSVC (latest version)

Compiler errors:

Severity Code Description Project File Line Suppression State
Error C3177 you cannot have a conversion function to a type that contains 'auto' ctbignum\field.hpp 29

Severity Code Description Project File Line Suppression State
Error C3547 template parameter 'Is' cannot be used because it follows a template parameter pack and cannot be deduced from the function parameters of 'cbn::ext_gcd' dsapp ctbignum\gcd.hpp 69

Incompatible features

#define CBN_ALWAYS_INLINE [[gnu::always_inline]] in config.hpp

template <> struct dbl_bitlen<uint64_t> { using type = __uint128_t; };
template <> struct dbl_bitlen { using type = __uint128_t; };
in type_traits.hpp

Inline attribute should be configurable

The always inline attribute should be a macro such that it can be configured (if the compiler does not support the particular way of enforcing inlining). For example:

ctbignum/include/ctbignum/mult.hpp

Line 30 in d1b2659

[[gnu::always_inline]]

#define CBN_ALWAYS_INLINE [[gnu::always_inline] somewhere in a, e.g., ctbignum/config.hpp file.
Then later more fancy stuff can be added there for other compilers when needed.

Remove NTL dependency in unittest

Make unittests only depend on the bare minimum dependencies (i.e. Boost.Hana and sprout), should be able to build the tests without much effort / the extra cruft.

bigint?

Het is heel raar dat er niet een duidelijk "bigint" type is. Duurde even voordat ik doorhad dat je een sprout::array moet maken. Maak een bigint.h ofzo, een duidelijk startpunt voor nieuwe mensen ;)
template <size_t N> using big_int = sprout::array<uint64_t, N>; in bigint.h ?

clang-format style

add .clang-format bestandje

implement lazy reduction

rename all.hpp to ctbignum.hpp

implement separation between fixed-size and expanding integers

...and bookkeep an upper bound of the bitsize in the type

dedicated type for big_int

license kiezen

oppassen met code gekopieerd van anderen. "porten" = kopieren

add AUTHORS file

and refer to Authors in de standaard header in elk bestandje

implement multiplication

Add documentation

Use Doxygen? i.e. doxygen bestandje toevoegen. Doxygen kan LaTeX dus dat is wel zo handig om functies te beschrijven?

Montgomery arithmetic doesn't seem to be constant-time

Looking into montgomery.hpp there is a conditional substraction that depends on input secret data in all procedures:

ctbignum/include/ctbignum/montgomery.hpp

Lines 63 to 64 in a532f24

	if (result >= padded_mod)
	result = subtract_ignore_carry(result, padded_mod);

ctbignum/include/ctbignum/montgomery.hpp

Lines 115 to 116 in a532f24

	if (A >= padded_mod)
	A = subtract_ignore_carry(A, padded_mod);

ctbignum/include/ctbignum/montgomery.hpp

Lines 161 to 162 in a532f24

	if (result >= padded_mod)
	result = subtract_ignore_carry(result, padded_mod);

ctbignum/include/ctbignum/montgomery.hpp

Lines 209 to 210 in a532f24

	if (A >= padded_mod)
	A = subtract_ignore_carry(A, padded_mod);

Did I miss something?