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

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
    thanks for answer. As I told in the question I want to obtain $T$, **without calculating the modular exponentiation for all $T$ up to $N$**. With calculation it is obvious that $2^{27} \equiv 2^1 \pmod{2731}$. So $T = 27-1 = 26$2012-12-13
  • 0
    The only question you asked about obtaining $T$ was "how can we find it among the divisors of $N-1$," and as you have been told twice we **can't** since it may not be among the divisors of $N-1$.2012-12-14
  • 0
    As I know, if there is any $T$ it should be among divisors of $N-1$. That is, in case of existence of such a $T$, it should be made from the prime factors of $N-1$ so $T$ is one of divisors of $N-1$.2012-12-14
  • 0
    $T$ must be a divisor of $N-1$ **if $N$ is prime**, a condition which is mentioned nowhere in the body of your question and nowhere in your comments on my answer. If you mean for $N$ to be a prime, you should say so (and consider using $p$ instead of $N$). So: if $N$ is prime, and if you know the factorization of $N-1$, then you also know all the divisors $d$ of $N-1$, and you only have to calculate $b^d$ for such $d$. And you can calculate $b^d$ without first calculating $b^2,b^3,b^4,\dots$. Do you know how to do that? or is that what you are asking about?2012-12-14
  • 0
    I assume that $N$ or $p$ is prime and I know full factorization of $N-1$. And I know all divisors of $N-1$. How do I know which divisor is $T$ (fundamental period)?. The real problem is this.2012-12-14
  • 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