On 13/01/2026 15:52, Hans Åberg wrote:
>
>> 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.
>

Are you thinking about more general modular arithmetic, rather than
specifically powers of 2? I don't see why you would need division at
all for powers of 2, but obviously it's a different matter for arbitrary
modulo numbers.

> 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.
>

That sounds fun.

I know a little of the theory in this area, but have very little
practical experience. (I did implement an RSA system a great many years
ago, but it was for understanding the mathematical principles, with no
effort spent on efficiency of the implementation.)

>> 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.
>

I don't know of any relevant proposals, sorry. Others here have a far
better overview of outstanding proposals than I ever could.