> On 13 Jan 2026, at 15:33, David Brown <david.brown_at_[hidden]> wrote:
>
> On 13/01/2026 14:43, Hans Åberg wrote:
>>> On 13 Jan 2026, at 14:41, David Brown <david.brown_at_[hidden]> wrote:
>>>
>>> On 13/01/2026 14:34, Hans Åberg via Std-Proposals wrote:
>>>> There might be support for modular integers int_mod<m> ≔ ℤ/mℤ for a modulus m that fits into a fixed-sized word, say 4096 bits for use in cryptology, m ≤ 2⁴⁰⁹⁶. With recursive templates, like those I have written, for fixed-size unsigned integral types up to uint4096_t, it should not be difficult to implement.
>>>
>>> "unsigned _BitInt(4096)" will give you that. That is already part of C23, and I believe it is coming to C++, though I don't know the current status off-hand.
>> It is too slow.
>
> Speed is a quality of implementation issue. The standard specifies the way these integer types work and their basic arithmetic operations, but it does not specify how those operations are implemented. So an implementation can use a simple O(n^2) multiplication algorithm - it could also use something a lot more sophisticated.

Indeed, it does not seem possible to distinguish by means of time complexity alone between, say, a pure 64-bit and a 32-64-bit implementation, even though the former might be a couple of times faster. The latter is the traditional one, so that is likely what will end up in the compilers.

> If you want a C++ library for cryptography work, there's a great deal more involved than just a large modular integer type. You'll want specific algorithms for particular operations, support for integer power operations, support for guaranteed clearing of key storage, and all sorts of other things. And of course none of this will be much use to ordinary users - they will want high-level cryptographic functions, without caring about the implementation.

Indeed, the idea is not to cover such specialized uses, but to enable more general code to be written in a portable way.

For example, cryptology uses a lot of sequenced multiplications or squarings of modular numbers, and for that, one can use Montgomery multiplication, which avoids division. But a paper from 2004 reports that it is only 20% faster than multiplication with interleaved division.

Then hardware support for division is much better nowadays, so it may not be worth pursuing.

Then multiplication with interleaved division leads to the very complicated classical division algorithm, that I now have optimized, and allocation overshoot with one.

So I decided to opt for a variation that avoids those issues, and I think is considerably faster, as it avoids backwards jumps, encouraging pipelining.

> Have you had a look for existing standards proposals in this area? I have not looked at it myself, but it would surprise me if there weren't a fair number of related proposals. Check to see what there is, and what their status is, then you can see if it is worth making a more specific proposal. But if all you are asking for is a modular integer type with normal arithmetic operations, it exists already, and if your only problem is that an implementation you tried was too slow for your liking, then the way forward is a bug report to the compiler implementer.

I also did some new mathematics, and then I realized this might be a suitable way to go. But if you have some other proposals, report them here, and we might compare.