0

Recently studied some of the mathematics behind the RSA encryption scheme. From what I have seen, the proof that finding the prime factorization of a number is super-polynomial time is yet to be found. I'm trying to sharp my common sense about algorithms. How can the world of cryptography relay on this problem to be that "hard to calculate" so much and does not seek a solid method that has it's proof documented? I mean, it could be that it's not super polynomial time, and in one day everything will fall apart..

Yaron Scherf
  • 313
  • Yes, it could be. It could be that the NSA already has a polynomial time algorithm. (Since the RSA challenge suddenly disappeared, this seems likely to me.) Things won't fall apart, because the people who find the algorithm will sit tightly on it. – B. Goddard Feb 17 '18 at 15:18
  • @B.Goddard ...at least we won't see how it is (possibly silently and secretly) falling apart. Anyway, no risk no fun. – Thomas Feb 17 '18 at 15:21
  • but aren't there more reliable ways? – Yaron Scherf Feb 17 '18 at 15:22
  • As you might know RSA is a 'public' key cryptography where encryption keys are shared to everyone. There exist many other reliable ways. You just have to think of a function whose inverse you knew somehow but is extremely hard to solve for others – AgentS Feb 17 '18 at 15:28
  • Maybe it is a strategy to get somebody to solve the hard problem. That answer may be more valuable to some than anything that can be encrypted. – marshal craft Feb 17 '18 at 15:30
  • Also I personally believe that it is fundamental axiom of most "logical" systems that there is no quicker way. I think it is like asking to find a quicker way to count assuming you have to count. Note: finding a super quick computer isn't solving the problem but going around it. – marshal craft Feb 17 '18 at 15:32
  • @marshalcraft can you please describe why this question is like "asking to find a quicker way to count assuming you have to count"? – Yaron Scherf Feb 17 '18 at 15:35
  • Also I can think of a hypathetical machine which could do it quicker, if the number's $n$ primality is in question, hypathetically if you had $x \times y \times z$ $n$ cubes which lubricated just right, and a plane with variable dimensions $x,y$ but $z$ just slightly larger than the $z$ and you compressed both sides, either it would form some rectangle or it wouldn't because there would be 1 extra; in which case $n$ was prime. Here you would only have to count the cubes dumbed into the machine. – marshal craft Feb 17 '18 at 15:38
  • @Yaron Scherf, I can not. Perhaps you can think about it, and sorry if that makes me "stupid" because I can only try to formulate words based on a hunch. – marshal craft Feb 17 '18 at 15:40
  • Sorry it is hard to even think about. What is relation with rectangle to prime, has to do with the notion of product? Perhaps studied with some high level topology or differential geometry or something that probes into the very meaning of dimension or infinitesimal angles. – marshal craft Feb 17 '18 at 15:47

0 Answers0