For positive integers x and N, such that x<N, with no common factors, the order of x modulo N is defined to be the least positive integer r such that:


The order-finding problem is determining the order r of a specified x and N. Link: https://www.youtube.com/watch?v=YNq7x6z8F1g

My questions:

  1. Is it not 1modN, always 0 (then we want an r such that $x^r$ is 0, this sounds weird)? Maybe I am misunderstanding the ≡ symbol.
  2. Is it this problem exactly the period finding problem with another name?


  • 2
    $\begingroup$ Would Mathematics be a better home for this question? $\endgroup$
    – jng224
    Commented Apr 2, 2021 at 10:57
  • 2
    $\begingroup$ @Jonas Well, it relates to quantum computing, so I'd consider it on-topic here, even though the "bare" question is of course purely mathematics. (Otherwise, we'd have to migrate lots of problems - basically any mathematical question which can be understood and answered without the physical motivation in mind, such as this one: physics.stackexchange.com/questions/626267/…) $\endgroup$ Commented Apr 2, 2021 at 11:08

1 Answer 1

  1. No, it is 1 mod N: $x^0=1$, and then you want to know the smallest $r>0$ where $x^r=1$ again (modulo $N$). Ten, of course, also $x^{2r}=1$, $x^{3r}=1$, etc. (all modulo $N$), so this has a period $r$.

  2. No. Period finding is more general. This is finding the period of a specific type of function, namely a function of the form $f_{x,N}(r)=x^r\mod N$.

  • $\begingroup$ Thanks a lot! 1) The key word there is "again": so we want to find the r such that will make the modulo be 1 again. 2) Which is the specific type of function for order-finding? $\endgroup$
    – Theo Deep
    Commented Apr 1, 2021 at 22:37
  • 1
    $\begingroup$ @TheoDeep Clarified. $\endgroup$ Commented Apr 2, 2021 at 10:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .