With all our tools in math, isn't it really possible to find the prime number p of an RSA key without brute-forcing it with a computer? I'm not talking about doing it in 2 minutes but doing it in a clever way that is faster than our computers. Some algorithms work really well like MSIEVE and GGNFS, but it takes too much time to proceed. Can't we really find the prime p without the help of an algorithm?
$\begingroup$
$\endgroup$
7
2 Answers
$\begingroup$
$\endgroup$
If there was a general strategy to do this with pen and paper, we could do it with a computer just as well. Most pen and paper solutions to any math exercise rely on using lots of “shortcuts” or “tricks” that exploit special situations or specific properties of the numbers in the problem. However, since RSA keys tend to be very big, we'd need an impossible number of special situations to have an approach that works generally.
$\begingroup$
$\endgroup$
7
As a basic rule from computer science:
Computers are always better at calculations than humans.
There is no algorithm in the world, which a computer could not execute, if someone made the effort to write the program. Especially "math by hand" can only use the same tricks or clever ways, which can be used by a computer as well. And that's not only due to computation speed, a computer does not make mistakes (assuming the program is correct) or write down everything.
There are things, where humans are much better than computers, for example any kind of pattern recorgnition - both in sound and images. For images, computers have for example huge problems with difficult lighting scenarios. And for a computer to recognize words with a low error rate, you need a training phase and even then speak more clearly than usual.
Oh, and btw. RSA keys are chosen long enough that you cannot find $p$ with all the computation power in the universe. That's the entire point.
-
$\begingroup$ A Formalist would agree with you, but not a Platonist. $\endgroup$– user27950Commented Oct 30, 2016 at 15:20
-
$\begingroup$ I am not sure what platonism has to do with this. There is no statement or question about abstract objects or concepts which are neither physical nor mental. $\endgroup$– tyloCommented Nov 2, 2016 at 11:25
-
$\begingroup$ If you are referring to constructive mathematics only, then there is probably no difference between "math by hand" and "math by computers". But there is a difference, if you take also non constructive proofs into account, e.g. Proof by contradiction. $\endgroup$– user27950Commented Nov 2, 2016 at 11:53
-
$\begingroup$ The question was adressed towards calculations, and not proofs. More specifically, it was about factorization algorithms and being able to do any tricks that a computer can't do. $\endgroup$– tyloCommented Nov 2, 2016 at 11:59
-
$\begingroup$ You are completely right with respect to the stated question about factorization. I referred to the general statement you made with the sentence starting with "Especially, "math by hand" ...". $\endgroup$– user27950Commented Nov 2, 2016 at 12:07
- find someone who knows the primes (or the passkey for where the primes are stored) - beat them with the book until they tell you the answer.:) $\endgroup$