Results 1 to 4 of 4

Math Help - fast modulo

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    2

    fast modulo

    Let n be a binary number of 512 bytes. Given <a = n mod P> for some prime P. How can we calculate most efficiently < n' mod P> when n' is n without its MSB and added LSB (0 or 1) ?
    Is there any special trick?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elad2109 View Post
    Let n be a binary number of 512 bytes. Given <a = n mod P> for some prime P. How can we calculate most efficiently < n' mod P> when n' is n without its MSB and added LSB (0 or 1) ?
    Is there any special trick?
    512 bytes = 4096 bits

    So this number can be as large as 2^{4096}-1.

    I'm not sure what rules the question designer intended; is the MSB allowed to equal 0? Does "without its LSB" mean a bit shift, or does it mean set the LSB to 0?

    I think this thread (Post #7) as well as this Wikipedia article give some ideas but don't give a full answer to the problem. Would it be possible to find out more about the rules so that I don't spend time trying to answer the wrong problem?
    Last edited by mr fantastic; May 11th 2010 at 07:42 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    2

    example

    assume we know
    100001001 mod P = a

    how can we calculate efficiently:
    000010010 mod P = ?
    (MSB 1 was removed, LSB 0 was added)

    000010011 mod P = ?
    (MSB 1 was removed, LSB 1 was added)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by elad2109 View Post
    assume we know
    100001001 mod P = a

    how can we calculate efficiently:
    000010010 mod P = ?
    (MSB 1 was removed, LSB 0 was added)

    000010011 mod P = ?
    (MSB 1 was removed, LSB 1 was added)
    In what's below, when I use single quotes for 'mod,' I mean the operator that returns the common residue. Without single quotes, mod is used in the usual way for math textbooks.

    Well if we know 000010010 'mod' P, then 000010011 'mod' P is easy because it's just the first result plus 1. (Unless the first result is P-1, then the second value is 0.)

    Is it right to assume that n occupies all 4096 bits? If so, then the MSB being 1 signifies a summand of 2^{4095}. If not, it's not hard to adjust according to the location of the MSB.

    But assuming all 4096 bits are necessary to store n, then n' = 2\cdot(n-2^{4095}), if we let the new LSB = 0. So we want to find

    n' \text{ `mod' }p = \left(2n-2^{4096}\right) \text{ `mod' }p

    In other words,

    2n - 2^{4096} \equiv\ ?\ (\text{mod }p)

    Depending on the size of p, we can use Fermat's little theorem to reduce the size of the exponent 4096, and afterwards we can use fast exponentiation as described in my first post. If p > 4097, then I believe it will take 11 = log_2(4096)-1 steps to get 2^{4096}\ (\text{mod }p), just by successively squaring the current result. But if you're doing this operation a lot, you can store the value(s) in a table.

    Does all this seem reasonable to you?

    (Edit: Added the part in green for correctness, since we need common residue.)
    Last edited by undefined; May 11th 2010 at 09:35 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 10:04 AM
  2. need help fast
    Posted in the Calculus Forum
    Replies: 4
    Last Post: March 17th 2009, 05:57 PM
  3. I need fast HELP
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 6th 2006, 11:07 AM
  4. I need HELP FAST!!!
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 20th 2006, 09:49 AM
  5. Can someone help me fast?
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 27th 2005, 11:54 AM

Search Tags


/mathhelpforum @mathhelpforum