7 Replies - 922 Views - Last Post: 15 February 2013 - 07:08 PM Rate Topic: -----

#1 stephanie904  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 33
  • Joined: 14-February 12

modular exponentiation

Posted 15 February 2013 - 04:51 PM

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


Is This A Good Question/Topic? 0
  • +

Replies To: modular exponentiation

#2 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: modular exponentiation

Posted 15 February 2013 - 05:11 PM

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.
Was This Post Helpful? 0
  • +
  • -

#3 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: modular exponentiation

Posted 15 February 2013 - 05:28 PM

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.
Was This Post Helpful? 1
  • +
  • -

#4 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • View blog
  • Posts: 1,693
  • Joined: 13-March 10

Re: modular exponentiation

Posted 15 February 2013 - 05:43 PM

What do you mean an int is a long? Python is dynamic.
Was This Post Helpful? 0
  • +
  • -

#5 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: modular exponentiation

Posted 15 February 2013 - 05:57 PM

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/
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10774
  • View blog
  • Posts: 40,122
  • Joined: 27-December 08

Re: modular exponentiation

Posted 15 February 2013 - 06:47 PM

If you have ab (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.
Was This Post Helpful? 0
  • +
  • -

#7 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2151
  • View blog
  • Posts: 3,306
  • Joined: 21-June 11

Re: modular exponentiation

Posted 15 February 2013 - 07:05 PM

View PostNekroze, 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.

View PostNekroze, 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.
Was This Post Helpful? 2
  • +
  • -

#8 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: modular exponentiation

Posted 15 February 2013 - 07:08 PM

View Postsepp2k, on 15 February 2013 - 07:05 PM, said:

View PostNekroze, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1