I have a doubt in my research work, can anyone tell me;

  • What is the difference between $\bmod {p-1}$ and $\bmod p$
  • $\begingroup$ If $p$ is prime, then $p-1$ is the order of the field's multiplicative subgroup. $\endgroup$ – Ken Goss Jan 17 '19 at 17:29
  • 1
    $\begingroup$ @KenGoss Please refrain from answering questions in the comments. Comments should be use to make suggestions or ask for clarifications. $\endgroup$ – Ella Rose Jan 17 '19 at 19:05
  • If we assume that $p$ is prime then $\bmod p$ is forming the field $Z/pZ$ or denoted by, $Z_p$ or $\mathbb{F}_p$. Indeed $\mathbb{F}_p$ is a finite field.

  • If $p$ is not a prime then $\bmod p$ is not a field.

  • If $p$ is a prime then $\bmod p-1$ is prime only if $p=3$ then $p-1 = 2$ which is the only even prime number.

  • if $p$ is a prime then $p-1$ is the order of the multiplicative abelian group formed by the non-zero elements $\mathbb{F}_p^*$.

| improve this answer | |

Both $(p-1)$ and $p$ play a role in a decryption scheme. Let's say you want to find values $e$ and $d$ to the decryption equation:

$$ (x^e)^d = x\ (mod\ p)$$

Then, you should solve the equation: $$ed = 1 \pmod {p-1}$$

If you find such $e$ and $d$, then $ x^{ed} $ would equal to:

$$ x^{1 + k(p-1) } = x^{1} (x^{(p-1)})^k \pmod p $$

The second term on the right is equal to $1$ by Fermat's Little Theorem. In other words, the product of the exponents must be $1$ bigger than a multiple of $(p-1)$.

So, in summary, the decryption operation is in $\Bbb Z^*_p$, but the inverse calculation is in $\Bbb Z^*_{p-1}$.

Furthermore, note that there are p+1 integer numbers between 0 and p inclusive. If we consider all integers under the addition operations $\pmod p$, such group $\Bbb Z_p$ will have p elements: $0, 1,\ldots, p-1.$ An inverse of $x$ would be $-x$.

But, if we consider those numbers under multiplication, then to have a group we must get rid of $0$, because $0$ would not have an inverse. We are left with numbers $1,2,\ldots,p-1$. This list has $p-1$ numbers, and this is the order (size) of the multiplicative group $\Bbb Z^*_p$. The $*$ means that the zero was removed.

| improve this answer | |

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.