mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2013-10-26, 01:28   #1
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7×137 Posts
Default Laymans explanation of RSA encryption

http://arstechnica.com/security/2013...-cryptography/
Fusion_power is offline   Reply With Quote
Old 2013-10-26, 02:11   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Actually the post is more about elliptic curve crypto than RSA...
jasonp is offline   Reply With Quote
Old 2013-11-04, 17:25   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by jasonp View Post
Actually the post is more about elliptic curve crypto than RSA...
It also makes some grossly wrong assertions. e.g.

"These factoring algorithms get more efficient as the size of the numbers being factored gets larger. The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (i.e. the key's bit length) gets larger. As the resources available to decrypt numbers increase, the size of the keys needs to grow even faster. "


This is totally wrong. The gap between multiplying large numbers
and factoring large numbers is GROWING as the numbers get larger.
Multiplying N by N takes time M(N) := O(log N loglog N logloglog N) via
convolution methods. This is polynomial in log N. Factoring takes
(via GNFS) L(N, 1/3). This is sub-exponential.

lim N-->oo L(N,1/3)/M(N) --> oo.

The assertion is so grossly and trivially wrong that it makes me wonder if the
author knows what the f*ck he is doing.
R.D. Silverman is offline   Reply With Quote
Old 2013-11-04, 20:50   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

1167610 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It also makes some grossly wrong assertions. e.g.

"These factoring algorithms get more efficient as the size of the numbers being factored gets larger. The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (i.e. the key's bit length) gets larger. As the resources available to decrypt numbers increase, the size of the keys needs to grow even faster. "
Perhaps the author has access to a quantum computer? :)

I mention this because speaking of "gross inaccuracies", PBS Nova last week aired a segment on interesting science going on as one moves down the temperature scale - very close to 0Kthey discussed Bose-Einstein condensates and quantum computers, which will revolutionize tasks such as "factorization and ... weather prediction." I was rather taken aback to hear such abject nonsense coming from writers for that show.
ewmayer is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
not exactly in laymans terms, but interesting Riemann site Fusion_power Lounge 0 2013-09-27 17:52
Encryption and governments retina Soap Box 119 2012-02-28 05:00
Bounds explanation Uncwilly Lounge 4 2011-04-01 19:15
A good encryption ? science_man_88 Soap Box 14 2010-10-14 18:31
Interesting Encryption problem FDCmercs Math 0 2007-01-07 15:50

All times are UTC. The time now is 22:59.


Fri Dec 3 22:59:49 UTC 2021 up 133 days, 17:28, 0 users, load averages: 1.70, 1.53, 1.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.