Why if x ∉ Z*n then the gcd(x, n) != 1? RSA

P00

10/31/23, 10:40 AM

I understand that if the $\gcd(x, n)\neq=1$ then the $\gcd$ is one of the $n$ prime factors, $q$ or $q$. But how is the fact that $x \not\in Z^*_n$ related to $\gcd(x, n)\neq 1$?

1 + 5

factoring

kelalaka

10/31/23, 10:59 AM

What do you mean by $x\not\in Z_n^*$.

P00

10/31/23, 11:11 AM

I mean that the message(x) is not in the inverse set of n.

kelalaka

10/31/23, 11:16 AM

Then what are those elements? An element is invertible iff $\gcd(x,n) = 1$! Did you take a basic algebra course before diving cryptography?

P00

10/31/23, 11:19 AM

Meaby I didnt express correctly. I, as an attacker, know the message x and n. I also know that x ∈ Zn and x ∉ Z*n. The fact that x ∉ Z*n means that gcd(x, n)!=1, but I dont understand why.

kelalaka

10/31/23, 12:24 PM

Now, you can upvote, too. Note that you should/follow a basic course about algebra to move on

Score:2

Crypto

kelalaka

10/31/23, 11:55 AM

The fact that $x \not\in Z_n^*$ means that $\gcd(x, n)\neq 1$, but I dont understand why

Let $y$ be the inverse of $x \bmod n$, so that $xy \equiv 1 \bmod n$. That means that $xy=kn+1$ (Bezout identity), or $xy-kn=1$.

Now for any common divisor, $c$, of $x$ and $n$ we will have this; $c \mid (xy-kn)$ this also means that $c\mid 1$, which implies $c=1$.

Therefore, having an inverse requires the common divisor to be only $1$ for finding the inverse of an element $x$.

The converse is also true. i.e.; Let $\gcd(n,x) =1$, again use the Bezout identity, $xx'=kn+1$. Now take $\bmod n$ on both sides.

$$xx' = 1 \bmod n$$this means that $x'$ is the inverse of $x$

So, we have $$x \in Z_n^* \text{ iff }\gcd(x,n)=1$$

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why if x ∉ Z*n then the gcd(x, n) != 1? RSA

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.