Allegro.cc - Online Community

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

This thread is locked; no one can reply to it. rss feed Print
Prime number, I should have known
superstar4410
Member #926
January 2001
avatar

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 clear

Quote:

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 = 510511
According 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.

http://www.arachnoid.com/prime_numbers/

Coool huh?

Don't take yourself too seriously, but do take your responsibilities very seriously.

Dustin Dettmer
Member #3,935
October 2003
avatar

Yeah, cool.

Now how does encryption use primes as protection from cracking? That part loses me.

Arthur Kalliokoski
Second in Command
February 2005
avatar

“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
avatar

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
avatar

What is the weird e symbol and mod?

3dcb6042d605b40b645a3c26c681f742.png

Also what's up with that three line equals?

Neil Black
Member #7,867
October 2006
avatar

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
avatar

Don't take yourself too seriously, but do take your responsibilities very seriously.

StevenVI
Member #562
July 2000
avatar

The "three line equals" means "is congruent to". I don't see a weird e symbol, unless you mean the phi: <math>\varphi</math>. It's a Greek letter, brush up! ;) (Edit: not displaying properly, but if you make a LaTeX document, type "\varphi" for the symbol. :P)

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
avatar

For the e he speaks of look at the bold

Quote:

A worked example
Here 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 numbers
p = 61 and q = 53 Make sure that these prime numbers are distinct.
Compute n = pq

Compute 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 calculate

To 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. 8-) 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
avatar

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 levy

http://gadgetopia.com/post/15

crypto.jpg

Don't take yourself too seriously, but do take your responsibilities very seriously.

Matthew Leverton
Supreme Loser
January 1999
avatar

My social security number is prime.

Tobias Dammers
Member #2,604
August 2002
avatar

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
avatar

SSN is a nine digit number :-/

Tobias Dammers
Member #2,604
August 2002
avatar

000000002

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

StevenVI
Member #562
July 2000
avatar

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
avatar

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
avatar

optimus prime

-----------------
I'm hell of an awesome guy :)

Neil Black
Member #7,867
October 2006
avatar

Seventeen posts before an Optimus Prime reference was made. I'm not sure if I should be proud or disappointed.

superstar4410
Member #926
January 2001
avatar

Thanks for the SSN

I stole your identity and am now wiring $20million US dollars from your account to mine.

I also had your vacation home in the South Pacific sold and I liquidated your
hard assets, such as your

images

and

images

and since I'm now you, I took your girl too. She is smart, at first she was like I wasn't you, but i told her I would prove to her that I was you because only you would know your ssn. So after I told her your ssn she believe me that I was you.

{"name":"amy-jackson-photos-01.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/d\/1dd6dec9bb3b33af4012b32d86659391.jpg","w":750,"h":1343,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/d\/1dd6dec9bb3b33af4012b32d86659391"}amy-jackson-photos-01.jpg

Oh by the way you are a father now, ooh thats right shes not your girl anymore, I mean I'm a father now.

Lastly I used your savings in your saving account to buy a new place for my new family. Thanks man you're the best

images

Don't take yourself too seriously, but do take your responsibilities very seriously.

StevenVI
Member #562
July 2000
avatar

Thanks man you're the best

I do what I can. 8-)

__________________________________________________
Skoobalon Software
[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]

superstar4410
Member #926
January 2001
avatar

and I do what I must ;)

Don't take yourself too seriously, but do take your responsibilities very seriously.

Go to: