[stephanie904]

I am working with modular exponentiation and my code compiles, but I am not sure where my formula is wrong or is it maybe cause im doing int instead of long ? but im running 3.3.0 python so i should use int...if someone could help please...thank you

for example im trying to
find 7 644 mod 645 which answer should be 436
find 11 644 mod 645 which answer should be 1
find 3 2003 mod 99 which answer should be 27
find 123 1001 mod 101 which answer should be 22

the only one I have correct is the last one which is 22

here is what i have

def me(b, n, m):
    a = bin(n)[:1:-1]
    
    x = 1
    
    power = int(B)/> % int(m)
    
    for i in range(len(a)):
        if a[i] == '1':

            x = (x * power) % m
            power = (power * power) % m
            return str(x)

print (me(7, 644, 645))
print (me(11, 644, 645))
print (me(3, 2003, 99))
print (me(123, 1001, 101))

This post has been edited by stephanie904: 15 February 2013 - 04:52 PM

[Nekroze]

In python 3 an int is a long, however in python 2 there is both an int and a long.

Actually i believe that an int in python 3 may actually be a long long but don't quote me on that.

So I don't think that the int is your problem.

[Nekroze]

Sorry I am not at all versed on this topic but I will try to help.

A quick google for 'modular exponentiation python' found these two which may may be useful to you.

http://numericalreci...nentiation.html

http://www.wojtekrj....tiation-script/

One mentions something about the math.pow function in the python library that can do modular exponentiation thing but is much faster then any pure python implementation. So that may be worth checking out.

[darek9576]

What do you mean an int is a long? Python is dynamic.

[Nekroze]

Yes python is dynamic but it does still have types and in python 2 there is an int and a long, these can be created by calling int() or long() you can also put a capitol L after a number and it will be interpreted as a long.

However in python 3 there is only the int() function and the int type however python 3 stores the int in a long on the C side if that makes sense.

This change is documented here:
http://docs.python.o...0.html#integers

And the pep for this change is here:
http://www.python.or.../peps/pep-0237/

[macosxnerd101]

If you have a^b (mod m), this is equivalent to [a (mod m)]^{b (mod m)}. So reduce a and b by modular arithmetic, then calculate the result (a % m)^{(b % m)}, then take the result and apply (mod m) to that.

[sepp2k]

Nekroze, on 16 February 2013 - 01:11 AM, said:

In python 3 an int is a long, however in python 2 there is both an int and a long.

Actually i believe that an int in python 3 may actually be a long long but don't quote me on that.

Integers in Python can be arbitrarily large. So they're restricted neither to the range of C's long nor long long.

Python 2 does distinguish between ints that fit into native integers and longs that are arbitrarily large, but you still can't get overflows when doing arithmetic on ints. Any operation on ints that would otherwise overflow, simply produces a long automatically. Even calling int() on a long that does not fit into an int will simply return the long unchanged.

TL;DR: You will never run into overflow problems no matter how large your integers get and no matter which Python version you're using.

Nekroze, on 16 February 2013 - 01:57 AM, said:

python 3 stores the int in a long on the C side if that makes sense.

That is not true.

[Nekroze]

sepp2k, on 15 February 2013 - 07:05 PM, said:

Nekroze, on 16 February 2013 - 01:57 AM, said:

python 3 stores the int in a long on the C side if that makes sense.

That is not true.

My bad, just my flawed understanding. And yes python will automatically promote to a long in python 2 but my point was that when the op asked if he should be using int() or long() that it doesn't matter at all because they will end up the same and there is no long() in python 3.