0
$\begingroup$

I have a number say N, I need to divide this number into p and q so that when I multiply p and q I would get original number back. Also, p and q should be two prime numbers.

Google search suggest to find the factor of the number.link. See the example and it's subsection, factor.

Now, I can understand if the number N itself is a prime number then I can find it's two factors as prime number. Like if N is 23, I can get two factor 1 and 23 and they are prime. Otherwise, if the number N is a squared number like 49 or 25 I can get there factors, and the factors are prime numbers.

Like if N is 49 and it's factors are 7 and 7 both are prime numbers.

Now, N not necessarily a prime number. It could be a non prime number like if the N = 2,542, Factors are = 2 x 31 x 41, where 31 and 41 are prime numbers but 31*41 = 1,271 which is not equal to 2542.

So, the question arise how could I divide a number into two prime numbers so that there multiplication should be the original number

$\endgroup$
11
  • 1
    $\begingroup$ This is - unsurprisingly - only possible if $N$ is the product of two prime numbers. $\endgroup$
    – Hagen von Eitzen
    May 6, 2022 at 15:28
  • 1
    $\begingroup$ This is hard to follow. $1$ is not a prime. Most numbers are not the product of two primes. For those that are...well, factoring large numbers is really hard. $\endgroup$
    – lulu
    May 6, 2022 at 15:29
  • 3
    $\begingroup$ Perhaps you would benefit from reading about the fundamental theorem of arithmetic $\endgroup$
    – Joe
    May 6, 2022 at 15:33
  • 1
    $\begingroup$ uniquely as the product of $m$ primes, where $m\ge 1$. So $1200=2*2*2*2*3*5*5$, which is the product of 7 primes (not distinct). So, as @HagenvonEitzen commented, you can only find two primes that multiply to give $n$ if $n$ is in fact the product of two primes, meaning that its prime factorization contains only two primes (not necessarily distinct). Otherwise, there is no way to find two primes that multiply to give $n$. $\endgroup$
    – Joe
    May 6, 2022 at 16:10
  • 1
    $\begingroup$ Maybe you should change your question to be about that problem, and use the "cryptography" tag. $\endgroup$
    – Joe
    May 6, 2022 at 18:08

1 Answer 1

Reset to default
1
$\begingroup$

In the RSA scheme, you use two prime numbers p, q and their product N = p*q. The RSA scheme depends heavily on the fact that given a large enough N, it is practically impossible to find p and q. So you don’t start with N and try to factor it - if you could, then I could crack your encryption.

Instead you start with two primes p and q and calculate N from them.

$\endgroup$

You must log in to answer this question.

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