Hi guys,(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Shor's algorithm, definition of modulo

Loading...

Similar Threads for Shor's algorithm definition |
---|

I Definition of surjection |

A Pairing algorithm |

B Is there a definition of randomness? |

B Bellman's and Bellman-Ford algorithm |

I Dijkstra's algorithm spp |

**Physics Forums | Science Articles, Homework Help, Discussion**