Allegro.cc Forums » Off-Topic Ordeals » Prime number, I should have known

 Prime number, I should have known
 superstar4410 Member #926 January 2001 So I was reading up on RSA public key encryption. Did you know, I didn't know there were an infinite number of prime numbers (kinda embarrassed to say it) but looking at the proof it seems pretty clearQuote: It is known that there are an infinity of primes, and this has been known since antiquity. In Euclid's Elements, Book IX, proposition 20, Euclid offers a proof similar to this one:Assume there is a largest prime number. Call this number p.Create new number q, equal to the product of all primes between 2 and p, plus 1.Our new number q has no factors in the original set of primes (between 2 and p), because dividing by any of them would produce a remainder of 1.From point (3) we conclude that q is either itself prime, or is composed of prime factors, all of which are larger than p.Point (4) falsifies point (1).Even though a proof like the above needs no specific numerical evidence, here is an example with real numbers:Assume the largest prime is 17: p = 17.Our new number q equals the product of all primes in the set {2 ... p} plus 1: q = 2 * 3 * 5 * 7 * 11 * 13 * 17 + 1 = 510511According to the factoring calculator at the top of this page, q has these prime factors: 19, 97, 277.All the prime factors of q are larger than p.Point (4) falsifies point (1).There are a large number of proofs of the infinity of primes, this one happens to be easy to understand.Coool huh? Don't take yourself too seriously, but do take your responsibilities very seriously.
 Dustin Dettmer Member #3,935 October 2003 Yeah, cool.Now how does encryption use primes as protection from cracking? That part loses me.
 Arthur Kalliokoski Second in Command February 2005 Chew on this awhile “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”― Robert A. Heinlein
 superstar4410 Member #926 January 2001 Yea the link Arthur posted explains it well. Yea its amazing how people think of these mathematical equations Don't take yourself too seriously, but do take your responsibilities very seriously.
 Dustin Dettmer Member #3,935 October 2003 What is the weird e symbol and mod?Also what's up with that three line equals?
 Neil Black Member #7,867 October 2006 I think the three line equals means something like "is exactly the same as"I know my professor uses it when two things have exactly the same truth tables.
 superstar4410 Member #926 January 2001 http://en.wikipedia.org/wiki/Modular_arithmeticThis might help a bit Don't take yourself too seriously, but do take your responsibilities very seriously.
 StevenVI Member #562 July 2000 The "three line equals" means "is congruent to". I don't see a weird e symbol, unless you mean the phi: . It's a Greek letter, brush up! (Edit: not displaying properly, but if you make a LaTeX document, type "\varphi" for the symbol. )As for modulus, you're familiar with the idea if you've ever used the % operator: http://en.wikipedia.org/wiki/Modular_arithmetic. __________________________________________________Skoobalon Software[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]
 superstar4410 Member #926 January 2001 For the e he speaks of look at the bold Quote: A worked exampleHere is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.Choose two prime numbersp = 61 and q = 53 Make sure that these prime numbers are distinct.Compute n = pqCompute the totients of product. For primes the totient is maximal and equals the prime minus one. Therefore Choose any number e > 1 that is coprime to 3120. Choosing a prime number for e leaves you with a single check: that e is not a divisor of 3120. e = 17 Compute d such that e.g., by computing the modular multiplicative inverse of e modulo : d = 2753 since 17 · 2753 = 46801 and 46801 mod 3120 = 1, this is the correct answer. (iterating finds (15 times 3120)+1 divided by 17 is 2753, an integer, whereas other values in place of 15 do not produce an integer. The extended euclidean algorithm finds the solution to Bézout's identity of 3120x2 + 17x-367=1, and -367 mod 3120 is 2753)The public key is (n = 3233, e = 17). For a padded message m the encryption function is or abstractly:The private key is (n = 3233, d = 2753). The decryption function is or in its general form:For instance, in order to encrypt m = 65, we calculateTo decrypt c = 2790, we tap.Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real life situations the primes selected would be much larger; in our example it would be relatively trivial to factor n, 3233, obtained from the freely available public key back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key. Don't take yourself too seriously, but do take your responsibilities very seriously.
 Billybob Member #3,136 January 2003 I see you're reading up on RSA. It's neat stuff, and actually not that difficult to implement once you've read it over a few times. Took me a little while to wrap my head around modular arithmetic (pun intended)
 superstar4410 Member #926 January 2001 Yes bob reading up on it a bit. I actually read up on it a while back when I was learning about encryption techniques (though I wasn't doing public key encryption), and I researched other cihper algortihms before I coded my own digital encryption software allowing me to with relative confidence keep my data safe from the average person/or even coder (I don't expect the NSA to be trying to crack my encryption using their supercomputers).Anyways I've been reading Crypto"How the code rebels beat the government saving privacy in the digital age"By Steven levyhttp://gadgetopia.com/post/15 Don't take yourself too seriously, but do take your responsibilities very seriously.
 Matthew Leverton Supreme Loser January 1999 My social security number is prime.
 Tobias Dammers Member #2,604 August 2002 Matthew Leverton said: My social security number is prime. Is it '2' by any chance? ---Me make music: Triofobie---"We need Tobias and his awesome trombone, too." - Johan Halmén
 Shravan Member #10,724 February 2009 SSN is a nine digit number
 Tobias Dammers Member #2,604 August 2002 000000002 ---Me make music: Triofobie---"We need Tobias and his awesome trombone, too." - Johan Halmén
 StevenVI Member #562 July 2000 Mine is 607-70-1699. Go and steal my identity now. __________________________________________________Skoobalon Software[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]
 BAF Member #2,981 December 2002 Your SSN shows up at ***-**-**** when you type it. That's what I see when you post 607-70-1699.
 le_y_mistar Member #8,251 January 2007 optimus prime -----------------I'm hell of an awesome guy :)
 Neil Black Member #7,867 October 2006 Seventeen posts before an Optimus Prime reference was made. I'm not sure if I should be proud or disappointed.