1

Can someone kindly help me with the following question.

Please bare in mind I am not good at maths, but I do get concepts, so I am looking to see if my current conceptual understanding is correct (rather than the math behind it)

RSA Cryptography uses (amount other things) two large 'prime' numbers multiplied together.

Is it true that if you use two prime numbers when multiplied together they produce a non prime number but this number can 'only' be factored into integers by using the two original prime numbers

Lets say for a moment you did not use prime numbers, so you multiple twp large non-prime numbers. Therefore these two non-prime number would potentially have more than one set of smaller integer numbers that could be used to divide the large number?

If the above is correct then by definition there would be "more than one answer to the puzzle" e.g. what smaller numbers can I use to factor this very large number? and if there were multiple possibilities then from a computing perspective it would be easier (and thereby faster) to find a 'solution' to the factorization whose result could then use used to decrypt the information?

Are my assumptions above thus far correct (leaving aside the fact for a moment that the RSA protocol may not work with non-primes it is the principle of factorizing difficultly I am interested in)

So it is true to say as a 'prime' number can only be divided into an integer by using either 1 or itself then there is only 'one possible answer to the factorization of two primes that have been multiplied together' to arrive at the originator primes e.g. you have to know the original primes? therefore there is "only one answer to the puzzle" thereby making this one answer harder (and thereby slower) to find if you do not already know it

Thanks All

user2971567
  • 11

2 Answers2

0

From my understanding of the RSA cryptography, Your analysis is correct. Since you can factorize the large number obtained by two non-primes easily, you can supposedly solve the problem faster. However, read this -
https://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf
There may be special cases where the factorizing problem may be easier than the RSA problem. The question as to which is faster RSA or factorizing is still open for debate.
For general purposes, you can say RSA is slower to solve. I would also suggest you to read this-
https://crypto.stackexchange.com/questions/951/why-has-the-rsa-factoring-challenge-been-withdrawn

Community
  • 1
Win Vineeth
  • 3,504
0

I'm not sure to completely understand your question, however, in general, if you have a large number to factor then (unless it is prime), if the factors are more, then it may be easier to factor.

This simply depends on the fact that if a number $n$ is a product of two primes $n=p\cdot q$, with $p<q$, the only thing you can say is that $p < \sqrt{n}$.

On the other hand, if $n$ is the product of 4 primes $n=p\cdot q\cdot r\cdot s$, with $p<q<r<s$, then you know that $p<\sqrt[4]{n}$.

In other words, if you are looking for the smallest prime factor of $n$ (to begin factorization), on the average it will be much smaller if $n$ is the product of 3 or 4 primes than if it is the product of 2 primes.

In general, a number which is the product of 2 distinct primes $n=p\cdot q$, will have 4 divisors $\{1, p, q, p\cdot q\}$. A number which is the product of 3 distinct primes $n=p\cdot q\cdot r$ will have 8 divisors $\{1, p, q, r, pq, pr, qr, pqr\}$. And so on, i.e., a number which is the product of $k$ distinct primes has a total of $2^k$ divisors.

Giovanni Resta
  • 2,368