September 15th, 2003, 11:58 AM
To elaborate a bit more.
The important thing here is that the values we have made public are E(17) & N(2773).
Crucially what we have not made public is J(N) i.e. 2668.
This is crucial as J(N) & D are used as seeds in Euclids algorithm to generate E.
In other words we provide it with D(157) & J(N) (2668), and most of the time it will find a satisfactory value for E - in this case 17 being a valid result (there may well be others as well!).
Incidentally, this branch of maths is called 'number theory', and some of the results you can get from it, like the PGP agorithm seem nonsensical unless you have gone through the maths yourself, and followed the proof. Showing my age here, but I first saw this published in a technical paper in 1975 when I was at university, folowed the proof with difficulty, and at the time thought 'that is really cool!'
The only mathematical link between E, N, & D is provided by J(N).
And obviously to calculate this we need to know what P & Q are in the first place!
This has stood the test of time, as in the last 30 years no one has found a mathematical way to reverse this process, and brute force doesn’t work either, as the number of primes (P) you have to guess is astronomical. Even on the fastest supercomputer on the planet you are typically looking at years of computing time for RSA 1024 bit - of course you might get lucky, but that is incredibly unlikely.