mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Tales From the Crypt(o)

Reply
 
Thread Tools
Old 2016-05-03, 20:46   #12
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by xilman View Post
I've heard persuasive rumours for a few years now that GCHQ / NSA have developed and implemented a L(1/4) algorithm. The implication is that those organizations could break any kilobit RSA key they want, but not every key they would like. A further rumour has it that the Utah facility not only has a copy of the internet, a la Google, but factors integers in its idle cycles. Treat this rumour-mongering and speculation with as much suspicion as you think appropriate.

If the rumour is correct, then perhaps we can deduce that the algorithm requires finding O(sqrt(N) smooth integers of size bounded by O(sqrt(N)) . I've been thinking about such things for a little while now --- unsucessfully it's needless to say.
Where are you hearing these rumors from? On what basis do you call them "persuasive"?
Dubslow is offline   Reply With Quote
Old 2016-05-06, 02:25   #13
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Quote:
Originally Posted by xilman View Post
I
If the rumour is correct, then perhaps we can deduce that the algorithm requires finding O(sqrt(N) smooth integers of size bounded by O(sqrt(N)) . I've been thinking about such things for a little while now --- unsucessfully it's needless to say.
What you describe sounds like a N^(1/4) complexity algorithm, which would be much slower than L(1/4) complexity.
jasonp is offline   Reply With Quote
Old 2016-05-06, 13:40   #14
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2B1916 Posts
Default

Quote:
Originally Posted by jasonp View Post
What you describe sounds like a N^(1/4) complexity algorithm, which would be much slower than L(1/4) complexity.
I suspect that you missed or didn't appreciate the word "smooth".
xilman is offline   Reply With Quote
Old 2016-05-06, 15:29   #15
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by xilman View Post
I suspect that you missed or didn't appreciate the word "smooth".
I also thought there was a mistake in your post. If N is the number to be factored, then surely finding sqrt(N) numbers of any sort is infeasible. If N is the number of bits, then finding sqrt(N)-smooth numbers should be easy using standard dynamic programming, since sqrt(N) should be around 32.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 10:02.


Tue Dec 7 10:02:06 UTC 2021 up 137 days, 4:31, 0 users, load averages: 1.46, 1.33, 1.37

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.