Constant-time division is super slow for sure but it's not needed for cryptography.
Modulo is also similarly slow but rarely needed as well. For example in elliptic curve cryptography it's only needed at the very beginning of a computation when hashing to the elliptic curve or when producing a secret key from a random input key material.
In terms of speed, LLVM iXYZ wide-integer code is usually faster for basic operations (modular addition, substraction, multiplication) the big slowness is for modular inversion where constant-time inversion is about 20x slower than GMP inversion.
Plain bigint in general, including GMP are bottlenecked by memory allocation and the iXXX from LLVM are purely stack-based.
Regarding constant-time, I know that there have been petition to provide a constant-time flag to LLVM but no guarantees so far. Unfortunately you have to take an after the fact verification approach today unless you dropdown to assembly (see https://github.com/mratsim/constantine/wiki/Constant-time-ar... on a couple of constant-time verifiers available)
> or it's own JIT compiler that uses the MULX, ADCX and ADOX instructions.
Does LLVM's bigint implementation use those instructions? Last I tried LLVM can not handle the required data-dependencies on individual carry bits, making it impossible to use ADCX/ADOX in LLVM without inline assembly.
LLVM properly generates ADC code when you use __addcarry_u64 contrary to GCC[1] which generates really dumb code with setc/mov in and out of carry.
However __addcarryx_u64 which is supposed to generate ADCX and ADOX is not properly handled and only generates ADC.
I think you are mixing with one comment on the GCC mailing list about GCC not having the adequate representation of carry and even less a representation that can separate a carry and overflow chains[2]
There's a nearly identical issue in LLVM [1]. So neither are currently able to handle ADCX/ADOX in their IR and can only support it through inline assembly.
I was hoping LLVM could maybe bypass this IR limitation for the iXYZ types and generate the optimal instruction sequence, but from your assembly it looks like that doesn't happen either.
Modulo is also similarly slow but rarely needed as well. For example in elliptic curve cryptography it's only needed at the very beginning of a computation when hashing to the elliptic curve or when producing a secret key from a random input key material.
In terms of speed, LLVM iXYZ wide-integer code is usually faster for basic operations (modular addition, substraction, multiplication) the big slowness is for modular inversion where constant-time inversion is about 20x slower than GMP inversion.
Source: https://github.com/herumi/mcl#how-to-build-without-gmp this code has GMP backend, LLVM i254 / LLVM i381 backend, or it's own JIT compiler that uses the MULX, ADCX and ADOX instructions.
Plain bigint in general, including GMP are bottlenecked by memory allocation and the iXXX from LLVM are purely stack-based.
Regarding constant-time, I know that there have been petition to provide a constant-time flag to LLVM but no guarantees so far. Unfortunately you have to take an after the fact verification approach today unless you dropdown to assembly (see https://github.com/mratsim/constantine/wiki/Constant-time-ar... on a couple of constant-time verifiers available)