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
    For composite $N$, most of the time it will not be among divisors of $N-1$. Example, $N=15$, $b=2$. Are you assuming, without saying so, that $N$ s prime? Your example is.2012-12-11
  • 0
    @AndréNicolas, your'true about composites.I'm looking to reduce the exponent for primility test. If I know $N$ is prime, then $N-1$ is an obvious member of the sequence2012-12-11
  • 0
    But as you know, even if $a^{N-1}\equiv 1 \pmod{N}$ for all $a$ relatively prime to $N$, it does not follow that $N$ is prime.2012-12-11
  • 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