0
$\begingroup$

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:

$x^r≡1(modN)$

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?

Thanks!

$\endgroup$
2
  • 2
    $\begingroup$ Would Mathematics be a better home for this question? $\endgroup$ – Jonas Apr 2 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$ – Norbert Schuch Apr 2 at 11:08
3
$\begingroup$
  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$.

$\endgroup$
2
  • $\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 Apr 1 at 22:37
  • 1
    $\begingroup$ @TheoDeep Clarified. $\endgroup$ – Norbert Schuch Apr 2 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.