Alternative to powmod in Nim

> Because it's so so slow, even naively converting multiplication in a series > of modular additions is much faster: dunno about this one - after fixing the insanely slow recursion, changing the implementation to a simple natural mul+divrem 100x:ed the performance - this is the textbook impleme

Alternative to powmod in Nim

Thanks :) On that front, Constantine as being integrated to Google continuous fuzzing framework OSS-fuzz in It's quite complete as it's fuzzed for both 32-bit and 64-bit.

Alternative to powmod in Nim

Amazing! As a normal Nim learner, I am grateful to you for your responsibly making highly completed libraries for Nim. (not those which provide naive solutions without covering edge cases or seeking high performance.)

Alternative to powmod in Nim

Following my last PR, I'm now **faster than GMP, even without assembly** on those small-medium-sized bigints. (with Clang, GCC codegen for bigints is meh)

Alternative to powmod in Nim

I have finished implementing a new arbitrary-precision backend in Constantine for powmod i.e. different from the fixed precision `BigInt[256]` or `BigInt[1024]`, it can deal with runtime sizes. PR: Benchmarks show that perf is within 85% to 140%

Alternative to powmod in Nim

> The fundamental problem with stint currently is a consequence of its > unfortunate recursive design which renders every single operation > exponentially slower than it has to be in the number of bytes used for the > size of the integer. Actually, the main slowness issue is currently the carry

Alternative to powmod in Nim

The fundamental problem with stint currently is a consequence of its unfortunate recursive design which renders every single operation exponentially slower than it has to be in the number of bytes used for the size of the integer. The first step to any stint work is to replace the implementatio

Alternative to powmod in Nim

I have read your post, but I have not much time to answer you. Barret and Montgomery techniques improve the reduction, which is crucial indeed. Unsigned integer arithmetic is slow, but 256 primes does not fit on floating point types, so it is basically our only solution. I am surprised that Ope

Alternative to powmod in Nim

Since implementing fast powmod comes back every few months, I've written an issue to explain the high to medium level details on how to implement high-performance powmod here:

Alternative to powmod in Nim

Here is an implementation of modular exponentiation in Constantine. 8ms on my machine # nim c -d:danger -r --outdir:build build/pow_bench.nim import ../constantine/[ arithmetic, io/io_bigints, config/precompute, arithmetic/limbs_modular,

Alternative to powmod in Nim

I'm currently also using stint for RSA, i initially used openssl but since it was adding pkcs1 padding (and mtproto doesn't want that) i opted for using this library. But the main issue is not related to that problem, what i am doing is explained here:

Alternative to powmod in Nim

You should use a cryptographic library for securing keys, not a general purpose library that does not optimize for security. In particular since you use powmod I assume you use it for RSA? In that case powmod is a critical function that can be easily attacked. Assuming you need cryptographic se

Alternative to powmod in Nim

>From a cursory look at implementation of [powmod in >stint](https://github.com/status-im/nim-stint/blob/master/stint/modular_arithmetic.nim#L68), > implementation of [pow in >python](https://github.com/python/cpython/blob/master/Objects/longobject.c#L4097), > keeping as reference the different m

Alternative to powmod in Nim

I am working on a mtproto client in Nim and the key exchange process requires handling big integers (also primes) with modular exponentation. Currently i am using the stint library using powmod, but i noticed that it is really slow (5 seconds in -d:release). The numbers are like this `powmod(3,