0
$\begingroup$

Let $T$ denote the smallest exponent such that $b^T \equiv 1 \pmod{N}$, then we call $T$ as fundamental period of the sequence satisfying the equation.

As an example for $b=2, N=2731$ we have $T=26$ since $T$ is the smallest number of the following sequence:

$ {26,52,78,104,...} $

It's obvious that $26$ is made of factors of $N-1$, here $\{2,13\}$. Assuming that we know all factors of $N-1$ even if $N$ is very large, without calculating the modular exponentiation for all $t$ up to $N$:

  1. How we can know the existence of any $T$ less than $N$?
  2. Is there any composite number having a $T$ less than N?
  3. If there exist one, then how we can find it among the divisors of $N-1$?
  • 0
    I know that it becomes$a$PRP only, but it is the first step in any deterministic test.2012-12-11

1 Answers 1

1

I think you are asking, how do we know there is a positive integer $T$ less than $N$ such that $b^T\equiv1\pmod N$. The answer is, we don't --- if $\gcd(b,N)\gt1$ then there is no such $T$. But if we know $\gcd(b,N)=1$, then consider the numbers $b,b^2,b^3,\dots,b^N$ all reduced modulo $N$. There are $N$ numbers in that list, and they are all between $1$ and $N-1$, inclusive, so by the pigeonhole principle, two of them must be equal. If $1\le r\lt s\le N$ and $b^s\equiv b^r\pmod N$ then $b^{s-r}\equiv1\pmod N$ and $1\le s-r\lt N$. So, you can take $T=s-r$.

In your question 2 it's not clear whether you want $b$ to be composite, or $N$, but, either way, we have just proved you can take $T\lt N$.

And as pointed out in the comments, if $N$ is composite, there is no reason to think $T$ will be a divisor of $N-1$.

  • 0
    And the answer is, check each divisor in turn to see whether it is $T$. To check a divisor $d$ takes only (on the order of) $\log d$ operations, and there are generally not all that many divisors to check.2012-12-14