Why are primes important?

Why are primes important?
Why do researchers spend so much time looking for larger primes?
Why has so much effort gone into trying to find a way to predict prime numbers?
Why are primes more important or useful than composites?

Prime numbers are very often used in asymmetric encryption algorithms. RSA is a popular example of one of these. For it to be secure, large prime numbers are needed. It is very important that RSA remain secure for the foreseeable future because it is needed for client computers to securely exchange symmetric encryption (algorithms like AES) keys with websites. Therefore, without primes, SSL and TLS technologies would likely be crippled and we would have a very hard time maintaining secure connections to websites and preventing mass data collection.

That should answer your questions about why primes are important and why larger primes are needed (for greater security), but your question about finding a way to predict primes remains. Assuming one could "predict" the primes being used in a particular set of RSA keys, SSL and TLS could easily be broken and online encryption using these two technologies would not be secure. In such a situation, the only way to securely communicate over the internet would be with symmetric encryption in which the key is shared offline before the communication begins. The motivation behind trying to find a way to "predict" primes could therefore be one of many different things. It could be an oppressive government trying to make mass surveillance easier (with the absence of secure, standardized, easy-to-use encryption), or it could be a cryptographer testing the security of existing algorithms in order to formulate more secure methods of encryption in the future. It really depends on the entity and its point of view concerning encryption technologies.

Why does RSA depend on finding larger primes/how do larger primes beget more security?

Also, why are the large numbers needed for RSA/encryption required to be prime? Why can they not large composites?

There's a good khan academy series on it look it up

>Why are primes important?
They're very deeply connected to an insane amount of mathematics in all fields. It's why stuff like the riemann hypothesis is so important to prove, because a *lot* of other mathematics depends on it being true.

>Why do researchers spend so much time looking for larger primes?
For the fun and fame. There's no other use in knowing these absurdly huge primes, although the process of getting there helps push other fields as well (e.g. computing, algorithm design, prime generating formulas and so on)

>Why has so much effort gone into trying to find a way to predict prime numbers?
Mostly due to their relationship to other theorems and fields, as seen above

>Why are primes more important or useful than composites?
Primes being important is really a wrong way of phrasing it, it's more like “primarility is important”, i.e. the distinction between primes and non-primes. It's not like mathematics only consists of primes, the interesting thing is the relationship between primes and non-primes.

>Also, why are the large numbers needed for RSA/encryption required to be prime?
RSA's strength derives from the difficulty of factorizing a large product of primes. I.e. say you have two primes P and Q, it's very easy to calculate N = P*Q; but if you only have N it's very difficult to find P and Q. This difficulty depends on the size of ‘P’ and ‘Q’.

If you replace ‘Q’, for exmaple, by a similarly large composite number X = A*B*C, then you'd be trying to factorize N=P*A*B*C which is much easier than N=P*Q becuase ‘A’, ‘B’ and ‘C’ will be much smaller than ‘Q’ was and therefore found more quickly (making the rest of the problem easier)

By making sure both P and Q are primes, you avoid situations like these where you could end up with very weak RSA keys otherwise.

I'm by no means an expert on how RSA works, but it seems that primes are needed for RSA to works correctly (it's just how it's designed).

Wikipedia puts it as: "In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem"

RSA derives its strength from the difficulty of factoring the product of two very large primes. As those primes become larger, I assume that the difficulty involved in factoring their product increases very quickly. This difficulty is what I believe makes cracking RSA so hard, especially when very large key sizes are used. It is certainly possible to crack RSA, but the amount of time it would take for a computer to do it would make the process infeasible.

So, to answer your questions concisely:
The products of larger primes are more difficult to factor than the products of smaller ones, making RSA harder to crack when larger primes are used. As for why the numbers need to be primes and not composites, I believe it is because composites can be factored on their own, meaning that a product of two composites would be much easier to factor than a product of two primes. The need for primes may also be related to the way the algorithm itself works, not just the impracticality of the use of composites.

Ill just leave this right here.

Here's the brief summary of RSA, from a number theorist:

You know about modular arithmetic (since you use % to program). You can solve the equation 3*x = 4 mod 5 quite easily. One way is just try all 5 possibilities. A more systematic approach is to notice 3*3 + (-1)*5 = 4, so reducing mod 5 gives 3*3 = 4 mod 5. How to write expressions like ax+by = c given a,b,c is an early start to number theory.

Here's a similar question: solve 3^x = 4 mod 5. Well, based on what we saw above, we know 3^2 = 4 mod 5. But how would you solve it systematically? There's no analogy for a^x + by = c.

Solving this kind of equation is called the discrete log problem. In fact, when p is prime, it's not too hard to solve a^x = b mod p, but I won't go into it here. It involves simple ideas from an intro number theory course. The interesting stuff happens when you want to solve a^x = b mod pq.

A basic theorem in number theory says this is equivalent to solving a^x = b mod p AND a^x = b mod q, and gives you a recipe for gluing these solutions into one of the original problem. So what gives? Well, we have to split pq into well, p and q, i.e. we had to factor pq.

The basic principle is that when p and q are "too large" not even a supercomputer can do this in a reasonable amount of time (possibly hundreds if not hundreds of thousands of YEARS depending on size). This is what gives RSA its security - mathematicians believe factoring a number so large can't be done efficiently enough. But the primes have to be large, hence the interest in generating large primes.

I can go into more detail if you'd like but that's the basic idea.

It's also worth mentioning shor's algorithm, which can only be taken advantage of by quantum computers. Apparently, it could cut cracking time of RSA keys down significantly (especially when using the key sizes that are commonly used today).

This is mostly correct but I think you got an important detail wrong: In RSA, the exponent is known, and you have to find the base. This is not the discrete logarithm problem (in disclog, the base is known and you have to find the exponent)

i.e. you're trying to solve x^a = c mod pq for known ‘a’, ‘pq’ and ‘c’. In number theory, this would be expressed as finding the ‘a’th root (in a finite field).

Discrete logarithm is a separate problem, which is difficult even for prime fields. (And perhaps even only for prime fields, not sure)

Yes, you're right. In RSA the exponent + the modulus form the public key. So it should be x^a = b mod pq, and we can solve x^a = b mod p using FLT.

Yes, another good point. Shor's algorithm, which can only be implemented on a theoretical quantum computer would make it theoretically possible to break RSA in a "reasonable" amount of time. Hence the push for research into quantum computing by intelligence agencies.

But what does it all mean, Basel?

I dunno, but just thought it would fit in the discussion somewhere.

Pretty interesting if you use the Fibonacci sequence on the number 3 6 9 three numbers Tesla was keen on. They(at least as far as i have gotten) all point in four directions.

I wouldn't even say I'm a hobbyist mathematician even.

This is too complicated for me.

To understand a lot of this you will need to read up on the theory. Things like modulo arithmetic and groups will help you understand a lot of the notation and descriptions in textbooks/internet resources.

Too much work. Just wanted a simple explanation.

You wont really get an answer besides the bigger = harder to compute

See the revision here Try an example. Can you solve x^2 = 4 mod 5? Or written in programming language: x^2 % 5 = 4. How about x^2 = 4 mod 3, or x^2 % 3 = 4?

There's a general method for this when the number after % is prime, but if it's a product of two primes pq, then it's really hard if you don't know p and q individually. Recovering p and q individually knowing only pq is "essentially impossible."

So knowing p and q individually (if you're the guy who created the number pq in the first place) means you have a secret no one else can find out, even when it's out in the open.

I don't actually know what modulo is or how to use it so I make things much more difficult when I program.

remainder

hth

I don't know what those are either really. I only use floats and integers.

3^1 mod 7 = 3 mod 7 = 3
3^2 mod 7 = 9 mod 7 = 2 (7 goes into 9 once with a remainder of 2)*
3^3 mod 7 = 27 mod 7 = 6 (7 goes into 27 three times with a remainder of 6)**

* 9 - (7x1) = 2
** 27 - (7*3) = 6

Ah, I didn't know you skipped elementary school. Do you know what addition is? What about multiplication?

The easiest way to think about it is taking remainders upon dividing.

So 6 mod 5 = 1 (or 6 = 1 mod 5). This is because when dividing 6 by 5, we get remainder 1.

Another example: 17 = 3 mod 7, because 17 divided by 7 leaves remainder 3.

Try rereading my posts now and working out examples.

Sorry. Don't remember or use things from 4th grade very often.
>3^1 mod 7 = 3 mod 7 = 3
Don't know what this means.