-1
$\begingroup$

Suppose, $N=p\cdot q$ is the product of two safe primes $p=2p'+1$ and $q=2q'+1$ for some odd primes $p'$ and $q'$.

Let, $p_0,p_1,\ldots,p_m\ll p',q'$ be a few odd primes chosen uniformly at random where $m\ll N$. My question is that is it possible to have the following congruence at all,

$$p_0^{p_1 \times p_2 \times \cdots\times p_m}\equiv \pm 1 \pmod N?$$

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to MathOverflow. With the Multiplicative order, letting $m=\operatorname{ord}_{N}(p_0)=m$, then note $m\mid 2p_1\times p_2\times\cdots\times p_m$ and $m\mid \varphi(N)$ where $\varphi(N)=(2p')(2q')=4p'q'$. $\endgroup$
    – John Omielan
    Commented Apr 15 at 18:18
  • $\begingroup$ Note that, in the comment above, my $m$ should be something different (e.g., $m_1$) to avoid conflicting with your $m$. $\endgroup$
    – John Omielan
    Commented Apr 15 at 19:22
  • $\begingroup$ @JohnOmielan Thank you for your answer. So the only possible order is $m=2$. $\endgroup$
    – Somudro Gupto
    Commented Apr 16 at 5:32
  • $\begingroup$ You are welcome. Actually, $m_1=1$ is also a possible order, with $m_1=2$ only being the order in the $p_0^{p_1\times p_2\times\cdots\times p_m}\equiv -1\pmod{N}$ case. Regardless, with $m_1=1$ or $m_1=2$, based on the problem conditions, consider what that means about the possibility of such odd primes $p_i$ existing. $\endgroup$
    – John Omielan
    Commented Apr 16 at 15:02
  • $\begingroup$ @JohnOmielan Yes, you are right. Later, I noticed that both $\pm 1\pmod N$ are impossible as $p_i\ll p',q'$. The proof is here. First, for brevity, let's denote $w=p_0^{p_1\times p_2\times\cdots\times p_m}\pmod N$. Now, the only element that has order $1$ in $\mathbb{Z}^\times_N$ is the identity $1$ itself. Since, $p_0 \ne 1$, $w \neq 1$. For $w=-1$, we need either $p_0 \equiv -1 \pmod{p}$ or $p_0 \equiv -1 \pmod{q}$ or both. So, $p_0 \ge p-1=2p'$ or $p_0 \ge q-1=2q'$. It contradicts with $p_i\ll p',q'$. $\endgroup$
    – Somudro Gupto
    Commented Apr 17 at 6:20

1 Answer 1

Reset to default
0
$\begingroup$

It is impossible. The proof goes here.

Denote $d$ as the order of $p_0$, so $d$ divides the order of $\mathbb{Z}^\times_N$ that is $4p'q'$. Let, $e=p_1\times p_2\times\cdots\times p_m$ be the exponent. Since, $p_i$s are odd, $e$ is odd.

If $p_0^e=1$ then $d$ divides $e$. So, $d$ divides $\mathsf{gcd}(e,4p'q')=1$ which implies $d=1$. In $\mathbb{Z}^\times_N$, the only element with order $d=1$ is the identity $1$ itself. But, $p_0>1$, so, $p_0^e\ne 1$.
Similarly, if $p_0^e=-1$ then $p_0^{2e}=1$, so $d$ divides $2e$. So, $d$ divides $\mathsf{gcd}(2e,4p'q')=2$ which implies $d=2$. It means either $p_0=-1 \pmod{p}$ or $p_0=-1 \pmod{q}$ or both i.e., $p_0=-1 \pmod{N}$. Hence, $p_0\ge p-1=2p'$ or $p_0\ge q-1=2q'$. But, $p_0< p'$ and $p_0<q'$. Hence, $p_0^e\ne-1$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .