Módulo RSA y orden de los elementos multiplicativos

Question

Dado un $n=pq$ donde $p$ y $q$ son Impares, primos distintos. Sea $\alpha \in \mathbb Z_n^*$ y $\text{ord}_n(\alpha)$ sea el orden de $\alpha$ en $\mathbb Z_n^*$ . El texto afirma que:

$\text{ord}_n(\alpha) = \text{lcm}(\text{ord}_p(\alpha),\text{ord}_q(\alpha))$ .

¿Cómo debo interpretar esto? ¿Y si $\alpha \geq p$ ? ¿Simplemente calculo el valor modulo $p$ ? En ese caso el orden de $n$ en $\mathbb Z_n^*$ es siempre $\text{lcm}((p-1),(q-1))$ . Pero si $p=3$ y $q=5$ podemos encontrar fácilmente un elemento en $\mathbb Z_{15}^*$ de manera que el orden no sea 4. Tomemos por ejemplo el 4. ¿Alguien tiene algo de luz que arrojar sobre esto?

Answer 1

Es $\Bbb Z^*_n$ el grupo multiplicativo de enteros coprimo a $n$ ? Sí, si $\alpha \gt p$ (no puede ser igual, entonces no sería coprima de $n$ ) usted toma $\alpha \pmod p$ y buscar su orden multiplicativo. El orden multiplicativo es la solución más baja de $\alpha^k=1 \pmod p$ Así que si $p=13, \alpha=2, \operatorname {ord}_p(\alpha)=12$ pero si $p=13, \alpha=4, \operatorname {ord}_p(\alpha)=6$ Para su ejemplo, es correcto que $\operatorname {ord}_{15}(4)=2$ pero $ \operatorname {ord}_3(4)=1$ y $ \operatorname {ord}_5(4)=2$ con $\operatorname{lcm } 2$ Así que todo está bien.