$n=pq$ $p<q$ impares, números primos hay una manera rápida de determinar si $p-1|q-1$ sin saber $p$ $q$

Question

Deje $n=pq$ $p,q$ impares primos $p<q$

Si sólo sabemos $n$ pero no $p$$q$, hay una manera rápida de determinar si $p-1|q-1$ sin factorización $n$ ?

Answer 1

Deje $n = pq$

si $p-1 | q-1$

1: $p-1| n-1$

2: No $q-1 | n-1$ (si esta falsa, n es un número de Carmichael con 2 divisores)

3: $x^{n-1} = 1$ (mod p) para cualquier x, donde x es coprime con n => $x^n = x$ (mod p)

Así, podemos hacer los siguientes pasos:

Obtener aleatoria x. de $[0, n-1]$

Calcular el $t = x^n-x$ mod n. No es $0$ con la probabilidad acerca de la $\frac{\phi(q-1)}{q-1}$

$t=0$ mod p. Así, el máximo común divisor(n, t) = p si $p-1 | q-1$

Por lo tanto, si mcd(n,t) es$1$ -, podemos decir "no".

si $gcd(n,t) > 1$, obtenemos la factorización y cah compruebe $p-1 | q-1$ manualmente