Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shor's algorithm, definition of modulo

  1. Feb 7, 2016 #1
    Hi guys,
    My question shouldn't take too long to be answered but I simply can't find anything using a google search. It's more of a problem from number theory rather than a physical one. I am refering to the Wikipedia article to Shor's algorithm and I still can't get my head around how the modulo operation can yield a negative remainder ( 6) under "classical part"). Both a^(r/2) and N are positive numbers and I am using the definition:

    a mod N=r : Find numbers q and r such that: a=q*N+ r, with abs(r)<N
    (Am I correct that if a<N, r=N-a ?)

    There ist still a sign ambiguity but they choose r to be positive. So by definition the remainder can't be negative. My assumption: In Shor's algorithm they use a different definition.
    Using anove definition without the restriction abs(N) yields a positive number r1 and a negative number r2 and they choose r=+/-min(abs(r1),abs(r2)). Am I correct? If not how else can this operation yield -1?
     
  2. jcsd
  3. Feb 7, 2016 #2
    Hi mupsi:

    I am quite rusty WRT this kind of problem, and I have never seen a problem like this where r is negative. However, I believe that if a < N, then r = a as q=0.

    Hope this helps.

    Regards,
    Buzz
     
  4. Feb 7, 2016 #3

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You are correct that, strictly speaking, the result of a 'mod n' operation must be an integer between 0 and n-1. Writing '-1 mod n' is just a shorthand way of writing 'n-1'.
    You can think of it as a formula rather than a constant, ie '-1' denotes the additive inverse of 1 in the ring that is the integers mod n.
     
  5. Feb 7, 2016 #4
    yes you're right. I was half asleep,when I posted this. In the first case, a mod N = a, when a<N. So we agree
     
  6. Feb 7, 2016 #5
    I give you an example:
    (first definition)
    15 mod 9 : 15= 1*9+6, therefore r=6 > 0
    but we also have
    15= 2*9 - 3,
    according to the secound definition we have r=-3 since abs(-3)<abs(6)
    Am I right in assuming that they use the latter definition in Shor's algorithm?
     
  7. Feb 7, 2016 #6

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    @mupsi There is no role for the use of an absolute value in defining what x mod y means.
    The following definition quoted above is faulty:
    It should be

    a mod N=r iff ##a, N## and ##r## are integers, with ##0\leq r<N##, and there exists an integer q such that: a=q*N+ r

    Nor is there, as far as I can see from the wiki article, any role for absolute values in the Shor algorithm.

    15 mod 9 is 6, not 3.
     
  8. Feb 7, 2016 #7
    Ok and I understand that. But this still doesn't explain the case a^(r/2) mod N = -1. I didn't understand what you meant in your first post. Can you give a specific example (maybe with numbers). How is M mod N =r with r<0 to be interpreted?
     
  9. Feb 7, 2016 #8

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Interpret it as ##a \mod N=N+r##. Then you will have ##0\leq N+r<N##.
     
  10. Feb 7, 2016 #9
    so a^(r/2) mod N =-1 actually means a^(r/2) mod N = N-1 in other words: find integers k and r such that a^(r/2)=k*N +N-1 ? Which of course satisfies remainder=N-1<N. To avoid any confusions: we have used r to denote the remainder before but in this case it's the exponent.
     
  11. Feb 7, 2016 #10
    r is already defined from the subroutine in the step before.
     
  12. Feb 24, 2016 #11
    Strictly speaking, an integer K modulo a (positive) integer N should be an element of the group "the integers modulo N", which is sometimes denoted by ZN. (Technically, this is the quotient group of the integers Z by its subgroup NZ.)

    For the purposes of calculation, it suffices to represent ZN as a set of integers containing just one representative for each of its elements.

    The most obvious way to do this is to use {0, 1, 2, ..., N-1}. But this is not the only way to do this.

    For instance, if N is an odd number, it's frequently more convenient to use as representatives the nice and symmetrical set {-M, -M+1, ..., M} where M = (N-1)/2.

    So for example, Z7 could be represented by {-3, -2, -1, 0, 1, 2, 3}. Compared to the obvious method, -3 ≈ -3+7 = 4; -2 ≈ -2+7 = 5, etc., where ≅ means "represents the same element of Z7 as".

    You want to know the 4th power in Z7 of -2 ? Just take its 4th power as an integer, and then add or subtract enough 7's to put the result in the range -3, ..., 3 again. So you would get (-2)4 = 16, and 16 - 7 - 7 = 2, which is again in range. (If instead you had to take the 4th power of the equivalent representative, namely 5, this would be more work.)

    [[[NOTE: Originally I wrote that ZN is a group. In fact, a commutative group. This is true, with respect to the group operation of addition. But as in the example of

    (-2)4

    in Z7, it also makes perfect sense to multiply elements of ZN as well. And as you might hope, multiplication distributes over addition, just as with the integers, reals, and complexes. Also, 1 in ZN behaves as a multiplicative identity.

    All these things make ZN into what mathematicians call a ring. What you often don't have are multiplicative inverses. The only cases where all the nonzero elements do have multiplicative inverses are when N is a prime number. Otherwise, only some of the nonzero elements will have multiplicative inverses.]]]
     
    Last edited: Feb 24, 2016
  13. Feb 24, 2016 #12
    that makes perfect sense. Thank you. Basically, to get from the "new" representation (the ring) to the one that is commonly used, do:
    r->N+r, in case the remainder is negative and r->r when the remainder is positive. That way you have unique mapping between the two representations.
    Thanks mate
     
  14. Feb 24, 2016 #13
    Just to be ultra clear, if you were somewhat ornery (or had a special reason for doing so), you could even take the set of integers {11, 12, 13, 14, 31, 37, 50} as your representatives. Not that I can think of any reason to do that. So to get these to correspond to the usual set {0, ..., 6} you might have to subtract more than just one times 7 to get to the usual set. In fact, {11, 12, 13, 14, 31, 37, 50} would correspond — if listed in the same order — to {4, 5, 6, 0, 3, 2, 1} in the usual set.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Shor's algorithm, definition of modulo
  1. Euclidean algorithm (Replies: 2)

  2. EM algorithm (Replies: 0)

  3. Randomized Algorithms (Replies: 2)

Loading...