Problem for advanced mathematics?

I have a world where remnants of advanced ancient humans (tv tropes link) live among us, but we are not aware of them. Is there some problem that people with mathematics more advanced then ours would be able to solve easily but we could only check the correctness of the solution, either by hand or using computers?

• Welcome To Worldbuilding, muwesawa, I presume your ancient humans are the ones with the advanced mathematics. It is reasonable their advanced mathematics could solve problems easily that would be difficult for us. There are large classes of problems where the solutions can only be found by computer simulation. Perhaps the ancients have exact equations to solve them. There are many to choose from. You may need to specify what you want solved, in general terms, and edit your question appropriately. – a4android Jun 24 '17 at 13:13
• Glad to see you have got some good answers to your question. Congratulations. This is an interesting question. We don't see enough questions like this and especially about subtle subjects like mathematics. – a4android Jun 25 '17 at 4:56

Yes, they could break the RSA encryption algorithm.

RSA encryption consists of encoding a message using the product of two very large primes, a little easy (known to us) mathematical work with this number produces two keys; which we call the public key and the private key.

The public key can be published and known to everybody. It is not a secret; it is intended to be known. Transmit it over the Internet, put it on a billboard, whatever.

With a very straightforward algorithm the public key can be used to encrypt a message. However, the cool part of RSA is that this encrypted message, even with the public key known, can only be decrypted with the private key.

RSA encryption is used everywhere, on the Internet, in banking to move trillions of dollars around the world.

However, it relies on a mathematical difficulty that, so far, we do not know how to solve: Factoring a very large number into component primes. Current estimates are that it would take millions of desktop computers working together millions of years to factor numbers as large as those we use in RSA, using the best factoring algorithms known to man.

Even if we had quantum computers with enough q-bits to factor this number, those algorithms would still take thousands of years to discover the private key based on the public key. On top of that, we can just increase the size of the numbers. The 256-bit, 512-bit, 1024-bit encryptions you hear about are just how many bits are used to store an RSA key, in those flavors. There is no limit to this, and every time the number of bits is doubled the number of breaking calculations grows exponentially. So if some compute algorithm breaks 1024-bit encryption in a day, in 30 minutes I can have a 2048-bit encryption it cannot break in hundred years. (I am a mathematician familiar with this algorithm).

If you could break the factoring problem using some sort of mathematics or quantum computing algorithm currently unknown to us; to the point of knowing within a day both the public and private key no matter how long the encryption, then you could trick nearly every major bank in the world into transferring billions of dollars into your accounts, you could break security on nearly every supposedly secure website (including that of many government computers, most brokerages and stock market exchanges). You could utterly destroy commerce and the economy. You could hack elections, and law enforcement records, and the military command structure, anything that is recorded, transmitted or received online.

I am not privy to what organizations like the CIA and other secret agencies with billion dollar budgets may use for encryption; so it is possible they do not use RSA, or use it with some other layers of encryption we cannot break mathematically. That said, what common corporations, banks, websites, and government agencies use is always some flavor of RSA relying on the apparently intractable mathematical difficulty of factoring very large numbers.

P.S. Forgot the other requirement: We can check whether a factorization is correct by simple multiplication; done in a few milliseconds at most on a regular desktop computer, and even able to be done by hand within a day, given some large paper to work with 1000 digit numbers.

Correction due to commentary

My claim above about whether quantum computers could break RSA is mistaken; but it can be excised without changing my answer. First, no quantum computer in existence has thousands of q-bits in order to do that; they have not factored numbers of more than about sixteen bits. Second, the question is about ancient human advanced mathematics, not advanced technology, and for our foreseeable future breaking the RSA factorization problem would definitely be in the realm of an advanced mathematical technique, not a technological feat.

An aside: In the timeline of quantum computing there is no shortage of hype; the most plausible recent advancement is IBM's 2017 claim of a 17 qubit computer. D-Wave claims 2000 qubits, but Their own announcement says their system operates "1000 to 10,000 times faster" than classical computers. They cannot be all entangled with each other then, and 10,000 times faster is not enough to challenge RSA; we could just make the key longer to compensate, or change our keys every week, or for critical applications like banking or national security, every day. There is no shortage of big numbers!

I repeat, this is a side issue, and no known quantum hardware is anywhere near enough to challenge the security of RSA. But advanced mathematics plausibly could do so.

• Or take logaritms in finite fields (Diffie-Hellman)... – AlexP Jun 24 '17 at 13:40
• @AlexP True enough, but Diffie (and variants) are also dealing with large primes, exponentiation and the difficulty of factorizations so I think it likely if they can break RSA they have the mathematical tools to break Diffie, too. But that is a guess, I haven't looked into what it would take to break Diffie; I will note your link suggests computers could break it if the prime is small, and not if the prime is large (600 digits). I chose RSA because it is far more pervasive than any other encryption algorithm, and I know it is used in banking and Internet security and on Wall Street. – Amadeus Jun 24 '17 at 13:51
• This is great, exactly what I needed. – muwesawa Jun 24 '17 at 14:53
• I disagree with this answer. Quantum computing can factor arbitrary integers in polynomial time (Shor's algorithm), and this has already been demonstrated in practice for smallish integers. By contrast, many mathematicians would be very surprised if there turned out to be a polynomial algorithm for classical computers. A better example might be a proof of an open conjecture such as the Riemann Hypothesis or the Twin Prime conjecture, which are widely believed to be true. – Robin Saunders Jun 24 '17 at 15:20
• @RobinSaunders Fair enough, but it does not affect my answer, the note about quantum computation is incidental. The question is about more advanced mathematics, not more advanced technology; so if they have such more advanced mathematics the author can simply say they can break RSA with it, while our conventional mathematics cannot. – Amadeus Jun 24 '17 at 18:40

There are quite a few such problems. However, there's a nasty trap for an author in using something like this. If you aren't sufficiently comfortable with advanced mathematics to describe a mathematical problem clearly, you may well make mistakes in using it in your story. Such mistakes are vastly amusing to people who do understand the problem.

The kind of situation you're describing is reflected in the P vs. NP question. This considers the difficulty of verifying answers to questions, as opposed to finding answers to questions. There are problems whose answers can be verified easily and quickly, but which have no known algorithm for finding an answer quickly. Problems whose answers can be found quickly are in class P, and problems where an answer can be verified quickly are in class NP.

The question is if P = NP? Currently, we don't know either way. It seems likely that P and NP are not the same, but we can't prove it. A proof that they are different would be a convincing demonstration of highly advanced mathematics; a proof that they are the same would have vast implications for philosophy, mathematics, computing and many other fields.

However, it's a bit of a difficult problem to get over clearly. A better idea for story purposes would be a method of generating prime numbers, or an explanation of their distribution among the numbers (which amounts to much the same thing). Prime numbers are fairly easy to understand, as whole numbers that aren't divisible by any other whole number (except 1), and many people already understand them.

Mathematicians have sought to understand them for thousands of years, but we still have no simple formula or algorithm which will generate all the prime numbers. Your readers can understand the problem, and your characters can check the primality of large numbers easily enough with a computer.

• Technically, we do have simple algorithms which will generate all the prime numbers. The problem is efficiently finding, say, the Nth prime number without first finding the first N-1; and even there, we have some progress toward a solution on the assumption that the Riemann Hypothesis is true. Of course, this doesn't affect the substance of your answer, which I believe deserves to be accepted by the asker (this is a problem with ordering answers by current rating without taking recentness into account). – Robin Saunders Jun 26 '17 at 10:29

This used to be a comment, now it isn't anymore.

There are a number of things, but most of them are hard to do in a book (and such). Take for example generating new prime numbers - well, you do not have those prime numbers, so what do you write instead? You could make up something, but I personally think it is unsatisfactory. On top of that, prime numbers in particular are a bit cliche.

I would choose a different approach: Predicting the outcome of experiments way more accurate than we are able to. I will give you two examples later, but let us first discuss why I think it is a good idea:

1) We can very easily verify the prediction

2) Their advanced knowledge is not just reflected in one problem but several problems they would have to solve at once

3) Someone that is maybe even unknown to the community will not just go ahead and solve those problems way better than we currently can (see 2)). If they have a formula for prime numbers, well, anyone could've come up with that (not really, but kind of). It would be a very good indicator that we indeed have more advanced people.

4) You can make up everything yourself (my two examples) or take the numbers from existing experiments.

So, let's see my examples:

a) Predicting the weather accurately.

Very easy to verify. They tell you: It is gonna be raining X much over 10 minutes in Y at Z o'clock tomorrow.

In order to do this, they would need way more efficient algorithms than we do and a lot more knowledge to gather that kind of information from the data available to them. This is such a complex problem that demands so much knowledge that it could only be done by such people.

b) Predicting where exoplanets are going to be before they are "discovered" by telescopes.

I want to do this one because it shows how easily you can come up with something that might even be relevant to your story. I don't know your story, but let's assume it was about space colonization for some reason. This would demand very, very advanced people, but in principal it is the same as a) again. They would need very efficient algorithms + an extensive knowledge.

• Ancient humans (or aliens) knowing more math than we do does not invalidate the mathematical proofs we have in hand. Weather is a chaotic system and thus inherently not computable; the issue is not better mathematics, but the impossibility of making accurate enough measurements of the current state. Further, telling us about an exoplanet does not mean they have/had advanced mathematics, it could be they once had many observatories, and kept a list of 100,000 such planets, many of which modern humans have not discovered. The problems they solve have to be mathematical problems we can't solve. – Amadeus Jun 24 '17 at 14:04
• @Amadeus The last point is a story issue, they either have that list or they don't. I strongly disagree with you on the weather, I adressed those concerns already in my post and explained how exactly this shows that they are more advanced. You arguing in principal that we would need more parameters to fit data is exactly my point. I agree though that this does not incluce every field of math, but much more so than it is the case for your answer for example because of the complexity behind the issue. I do not know what your proof thing has to do with my post tbo. – Raditz_35 Jun 24 '17 at 15:08
• @Amadeus Weather might be calculable and predictable by a different mathematical process. Certainly the mathematics we use is chaotic. Nothing changes that, but in different systems(s) of equation(s) non-chaotic predictions might result. This is the point of having advanced mathematics. We can't solve the problem of weather prediction, they can. This will work in a story. In real life? Probably not. – a4android Jun 25 '17 at 4:53
• @a4android I disagree. The future state of a chaotic system is dependent on the exact initial conditions; down to every decimal point.This is how such systems were discovered in the first place, in a weather simulation by a weather researcher! As such accurate prediction demands perfect measurement without any extrapolation, which is effectively impossible in weather: We cannot sense the temp, speed, direction and humidity of every cubic meter of atmosphere. It is a sensing problem, not a mathematical shortcoming. – Amadeus Jun 25 '17 at 10:06
• This question is dead and answered. No need to get into details. If someone feels the need, please open a new question. I feel like if there was an argument to edit my post, it wouldn't be in this discussion. Please stop posting so I don't have to delete my answer to have some peace and quiet. – Raditz_35 Jun 25 '17 at 10:49

There are many problems in physics being actually mathematical problems. For example, string theory has shown roughly $10^{500}$ vacua ($\approx 10^{500}$ possible Universe), but there is no way to find, in which we are. It leads to the NP-complete Knapsack-Problem.

Solving them could lead to major advances in engineering (artifical gravity and so on).