Mathematics desk
< October 22	<< Sep \| October \| Nov >>	October 24 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 23[edit]

Projecting a conic section[edit]

If the angle between the surface of a right circular cone and its axis is $\beta$ and the angle between a cutting plane and the cone’s axis is $\alpha ,$ the eccentricity of the resulting conic section C1 is ${\frac {\cos \alpha }{\cos \beta }}.$ Now suppose we project C1 onto the base of the cone (with the projection perpendicular to the base), giving a conic C2 on the base. What is the eccentricity of C2? Loraof (talk) 16:41, 23 October 2017 (UTC)[reply]

e=\tan \beta \cot \alpha

? Ruslik_Zero 20:51, 23 October 2017 (UTC)[reply]

Thanks. That makes sense—it means

e_{C2}={\frac {\sin \beta }{\sin \alpha }}e_{C1},

so a parabola remains a parabola, an ellipse lowers its eccentricity, and a hyperbola increases its eccentriciy. Loraof (talk) 22:15, 23 October 2017 (UTC)[reply]

Yep I get that too. You can get it from the formulae at Eccentricity (mathematics) using that a would change to a sin α. Dmcq (talk) 23:02, 23 October 2017 (UTC)[reply]

Product of 2 primes[edit]

See 11:40. It says that Cicada 3301 has a private key which is an extremely large number that is a product of two prime numbers. It then says that Google too has such a number -- very much larger than Cicada's -- and displays it. It says that cracking Google's number would take "trillions of trillions of trillions of years". So, a computer program would need that many years to figure out what two primes produce that number when multiplied. Is that right?

And if it's right, a follow-up question. So if Google's number is KNOWN -- I mean you can see it in the video and probably elsewhere -- doesn't that make it easier to crack? For example you can, judging from its last digit, narrow down the possible combinations for the two primes' last digits to just a couple. That's probably not too much but still is a starting point. And computers and technologies are ever advancing. Should Google be afraid that someone some day will figure out their two primes? --Qnowledge (talk) 23:19, 23 October 2017 (UTC)[reply]

Your interpretation is correct. See Integer factorization for details. Loraof (talk) 23:32, 23 October 2017 (UTC)[reply]

The 2017 video claims at 12:29 that you can get $200,000 for factoring RSA-2048 but the remaining RSA Factoring Challenge prizes were retracted in 2007. PrimeHunter (talk) 23:58, 23 October 2017 (UTC)[reply]

So it's harder than it seems. I see. But what's with these RSA numbers? How come we do know a number is the product of two primes but do not know the two primes it's the product of? --Qnowledge (talk) 00:19, 24 October 2017 (UTC)[reply]

A computer was programmed to compute two primes and store their product but not save the primes. RSA Factoring Challenge says: "The RSA numbers were generated on a computer with no network connection of any kind. The computer's hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge." There are many known primality tests which can say a number is composite without knowing a prime factor, but there is currently no known method to determine whether a large composite number has exactly two prime factors. You just have to trust the RSA employees and their computer. PrimeHunter (talk) 00:29, 24 October 2017 (UTC)[reply]

You seem to be using slightly the wrong terminology. In RSA, the public key is a single composite number which is the product of two primes, and the private key is the two primes themselves (i.e. the private key is actually 2 numbers - though of course if you only had one of the primes and the public key, finding out the other is simply a matter of division). The public key is easy to find if you have the private key, but the private key would take a huge amount of time to find from the public key. RSA encryption is based on a mathematical operation which uses the public key (i.e. the composite number), but can only be reversed by using the private key (i.e. the primes). This means that anyone can encrypt anything with the public key, but only the holder of the private key could decrypt it.

This also works in reverse - the private key holder can encrypt something with the private key in a way that anyone could decrypt with the public key. This may not seem useful, but it allows someone to confirm that a person is the holder of the private key (e.g. if I tell you to encrypt "hello", and I can then successfully decrypt the message you send with your public key, then I know you must hold the private key). This is the basis of digital signatures.

It is always going to be easier to compute larger primes with a classical computer than to factorise products of those primes with the same computer - so it will always be possible to make private keys which are effectively unbreakable (though sufficient advances in processing speed might allow the breaking of older public/private key pairs). Google's current key may be breakable in future, but they will be able to get a new one which is unbreakable by the standards of the time. Quantum computing shakes things up a bit, as Shor's algorithm provides a quicker way of factorizing large numbers - but a quantum computer which is stable enough for long enough to perform the algorithm on a large public key is a long way off, and by the time we have that we will probably also have quantum cryptography methods which are even more secure. MChesterMC (talk) 08:58, 24 October 2017 (UTC)[reply]

Thank you, very interesting. One more question. If the largest known prime number has 22M+ digits, are there any primes smaller than that but yet undiscovered? And if there are, what number is the highest threshold below which all primes are certainly known? And can I find a list of all those primes somewhere? --Qnowledge (talk) 14:51, 24 October 2017 (UTC)[reply]

Yes, there are probably a lot of undiscovered primes below that; I have to say probably, because if we knew that there were, we'd have discovered them. ^_^

It is difficult to say the real number. There are many lists online of primes up to a few billion, like here. But once you get to a few trillion, as this Maths Stack Exchange answer notes, you start to have more problems storing the primes than actually generating them. And it is not clear why you would want to store them, because it is easier to generate them again than to store them. Double sharp (talk) 15:02, 24 October 2017 (UTC)[reply]

It is not necessary to say probably: there are certainly gaps that are big enough that e.g. Bertrand's postulate kicks in. --JBL (talk) 15:37, 24 October 2017 (UTC)[reply]

Note that, as our article says, Bertrand's postulate has been proven. The proof is actually rather easy to understand. Tigraan^{Click here to contact me} 17:49, 24 October 2017 (UTC)[reply]

The crucial point is that testing whether a Mersenne number is prime is faster than for other candidates with a similar number of digits (see Lucas–Lehmer primality test). Hence, it makes sense to go after Mersenne numbers if you just want "the biggest prime number possible", rather than doing an exhaustive search. Tigraan^{Click here to contact me} 17:49, 24 October 2017 (UTC)[reply]

It's easy to compute more primes than anybody wants to store so the largest computations of sequential primes are only made to do something with the primes while they are briefly in computer memory. The Goldbach conjecture verification project had by 2012 computed all primes below 4×10¹⁸.[1] [2] says: "All prime gaps in 0 < x < 7e18 have now been analyzed". That means 165,220,513,980,969,424 primes (sequence A080127 in the OEIS) and may be the current limit. It would require tens of thousands of large hard disks to store them in a compressed format. If other projects have increased the limit then it's probably still below 10²⁰. The prime number theorem says there are approximately x/log(x) primes below x. x/(log(x)−1) is a better estimate. For the largest known prime x = 2^74,207,281 − 1 with 22,338,618 digits, it is approximately 5.8397447×10^22338609. The vast majority of these primes will never be computed. Dusart's result at Prime-counting function#Inequalities guarantees the approximation is accurate to the 8 significant digits I gave. I don't know the largest stored collection of primes. If somebody publishes a large claim then mathematicians will not be interested, and recomputing the primes will probably be easier than reading them, especially if it has to be done over the Internet. It would just be a waste of storage space. http://primes.utm.edu/lists/small/ has some small lists. PrimeHunter (talk) 01:15, 25 October 2017 (UTC)[reply]