Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
share|improve this question
    
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. –  André Nicolas Dec 11 '12 at 18:57
    
@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 sequence –  Mohsen Afshin Dec 11 '12 at 19:13
    
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. –  André Nicolas Dec 11 '12 at 19:17
    
I know that it becomes a PRP only, but it is the first step in any deterministic test. –  Mohsen Afshin Dec 11 '12 at 19:26
add comment

1 Answer 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$.

share|improve this answer
    
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$ –  Mohsen Afshin Dec 13 '12 at 12:41
    
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$. –  Gerry Myerson Dec 14 '12 at 0:35
    
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$. –  Mohsen Afshin Dec 14 '12 at 6:48
    
$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? –  Gerry Myerson Dec 14 '12 at 12:04
    
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. –  Mohsen Afshin Dec 14 '12 at 12:33
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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