Some Math

This is a discussion on Some Math within the C++ Programming forums, part of the General Programming Boards category; Hi ...can any one help me out with this (A^N)%M can be calculated in O(log(N)) time using fast power modulo ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    Some Math

    Hi ...can any one help me out with this

    (A^N)%M can be calculated in O(log(N)) time using fast power modulo

    but how do i calculate this ((A^N-1)/(A-1))%M ??
    Note that the above formula if from a geometric series

    Can any 1 help ?

    thank u

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If A-1 is invertible in Z mod M, then that's just one extra step since it can be written as a multiply. (I'm assuming here that A is an integer, otherwise the question makes no sense.)

    If A-1 and M are not relatively prime, then no shortcuts for you.

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    Re

    yes A is an integer , No it is no guarenteed that they are relatively prime
    How do i solve this ???

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Soooooooooooo, if you read, well, any of your book on discrete mathematics you would see something like

    ad = bd (mod pd) iff a = b (mod p)

    So since you need to divide by A-1, you need to do your initial congruence (i.e., in the calculation of A^n) not mod p, but mod p(A-1).

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    Re

    Didn't quite get u ... the problem is i am not CS/IS student

    Could u please explain a little more ?
    ex:

    ((19^1015-1)/(19-1))%103 ..

    how do i do this...

    PYTHON gives 55 ans the answer..

    Thank u

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    yay

    Got it dude..
    thank u so much !!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Math
    By knightjp in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 04-01-2009, 06:36 PM
  2. Help with C++ Math
    By aonic in forum C++ Programming
    Replies: 4
    Last Post: 01-29-2005, 04:40 AM
  3. Basic Math Problem. Undefined Math Functions
    By gsoft in forum C Programming
    Replies: 1
    Last Post: 12-28-2004, 03:14 AM
  4. Math Header?
    By Rune Hunter in forum C++ Programming
    Replies: 26
    Last Post: 09-17-2004, 07:39 AM
  5. toughest math course
    By axon in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-28-2003, 10:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21