How do I prove that if $\text{gcd}(m,n) \neq 1$, the result is $p$ or $q$ in RSA?

P00

10/31/23, 8:59 AM

I understand that $\text{gcd}(m,n)$ needs to be $1$ so we can apply the Euler's theorem, and if it's not $1$, the result is one of the prime factors of $n$. But Why the result it is always $p$ or $q$? Couldn't it be any other number?

2 + 1

factoring

DannyNiu

10/31/23, 12:47 PM

It's pretty much a no brainer, because $p$ and $q$ are by definition the factors of $n$.

Score:0

Crypto

kelalaka

10/31/23, 11:34 AM

A positive $d'$ with $d'\mid n$ and $d'\mid x$ is called a common divisor and the greatest of them is called the greatest common divisor $d = \gcd(x,n)$.

Since $n$ is the product of two distinct primes, then any common divisor must divide $n$. By the fundamental theorem of arithmetic, the prime factorization of $n$ is unique (up to order), namely $n=p\cdot q$

Therefore any common divisor of $x$ and $n$ must divide at least one of $1,p,q,pq=n$.

$1$ iff $p\not\mid x$ or $q\not\mid x$
$p$ if $p \mid x$ and $q \not\mid x$
$q$ if $q \mid x$ and $p \not\mid x$
$n$ if $x \equiv 0 \bmod n$

as a conclusion $\gcd(x,n) \in \{1,p,q,n\}$

+ 0

Score:0

Crypto

Don Freecs

10/31/23, 11:21 AM

Let $m$ and $n$ be products of two primes as in RSA: $n=pq$ and $ m = rs$.

if $m=n$ then we cannot learn about the primes,

if $m\not= n$ and $\gcd(m,n) >1$: since $m\not =n$ then $1<\gcd(m,n) < \min(m,n)$
gcd is the max of divisors sets intersection $D_n=\{1,p,q,n\}$ and $D_m = \{1,r,s,m\}$ hence we know now the $ \gcd(m,n) \in \{p,q\}\cap \{r,s\}\subset\{p,q,r,s\}$ hence the gcd returns a prime divisor of $n$ and $m$.

+ 0

Elon Musk

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

EN: How do I prove that if $\text{gcd}(m,n) \neq 1$, the result is $p$ or $q$ in 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.