[Issue 5765] ^^ and << with BigInts

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=5765



--- Comment #4 from bearophile_hugs at eml.cc 2011-03-23 05:55:03 PDT ---
(In reply to comment #3)

> The thing I'm really worried about is this:
> BigInt a, b, c;
> 
> a = (a ^^ b) % c;
> This is an attempt to do modular exponentiation, which comes up frequently in
> cryptography. The code is mathematically correct, but completely wrong in
> practice.

In Python 2.6 the built-in pow function has a third optional argument, that's
the modulus, that uses a more efficient algorithm to perform the powermod (note
the second 6 that's not a multi-precision value):

>>> (20 ** 125) % 7
6L
>>> pow(20, 125, 7)
6

I suggest to add a similar function to std.math or std.bigint. Also the D
compiler may recognize the (x^^y)%z pattern and replace it with a power mod
function call.


> So I would rather give an informative static assert for the BigInt ^^ BigInt
> case.

Python allows you to use the power/shift with multi-precision numbers too, if
you want. The multi-precision numbers can be used transparently, syntax-wise. 
If you have D templated code that you want to use with both BigInt and int you
will have to use a static if to change the code from x^^y to
BigInt(x)^^y.toInt() (or call a little pow template function that does the
same, losing infix operator syntax again), this isn't good. BitInt are meant to
work as integers, mostly. I'd like a D program to work with as few changes as
possible if I replace int with BigInts or BigInts with ints (in some situations
I may write the code with BigInts, see the results and then try to write the
same with ints/longs, to spot the overflows).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------