mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Science & Technology

Reply
 
Thread Tools
Old 2012-06-19, 09:05   #1
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

241110 Posts
Default Fujitsu cracks 278-digit crypto

http://www.theregister.co.uk/2012/06..._world_record/
Code:
We were able to overcome this problem by making good use of various new  technologies, that is, 
a technique optimising parameter setting that  uses computer algebra, a two dimensional search
 algorithm extended from  the linear search, and by using our efficient programing techniques to
 calculate a solution of an equation from a huge number of data, as well  as the parallel programming
 technology that maximises computer power.
and the original link
http://www.fujitsu.com/global/news/p...120618-01.html

Last fiddled with by firejuggler on 2012-06-19 at 09:06
firejuggler is offline   Reply With Quote
Old 2012-06-19, 09:45   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×33×132 Posts
Default

"21 personal computers (252 cores) in 148.2 days?" (The 0.2 days precision looks quite out of place.) Sheesh...
Attached Thumbnails
Click image for larger version

Name:	20120618-01a.gif
Views:	144
Size:	27.2 KB
ID:	8148  
Batalov is offline   Reply With Quote
Old 2012-06-19, 09:56   #3
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2,411 Posts
Default

Now it's time to generalise 2048-bit crypto...

even if a wrench might work far faster...
http://xkcd.com/538/

Last fiddled with by firejuggler on 2012-06-19 at 09:57
firejuggler is offline   Reply With Quote
Old 2012-06-19, 09:57   #4
poily
 
Nov 2010

3216 Posts
Default

It probably has nothing to do with factoring. More like with DL over some exotic group or EC.
poily is offline   Reply With Quote
Old 2012-06-19, 12:01   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×11×172 Posts
Default

http://www.nict.go.jp/en/press/2012/...20120618en.pdf is a PDF describing what they've done: there's an index-calculus-like attack which gets you from an EC problem over GF(3^97) to a discrete-log one over GF(3^582), and they've then done that one using the function field sieve.
fivemack is offline   Reply With Quote
Old 2012-06-19, 12:10   #6
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

1518 Posts
Default

Quote:
Originally Posted by fivemack View Post
http://www.nict.go.jp/en/press/2012/...20120618en.pdf is a PDF describing what they've done: there's an index-calculus-like attack which gets you from an EC problem over GF(3^97) to a discrete-log one over GF(3^582), and they've then done that one using the function field sieve.
What do you mean "index-calculus-like"? It's simple discrete log transfer by evaluating pairings.
Robert Holmes is offline   Reply With Quote
Old 2012-06-20, 06:31   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×33×132 Posts
Default

So it has asymptotically equivalent difficulty to SNFS? (Not to GNFS?)
Why did they compare it to the 676-bit GNFS factorization?

(I am only echoing Tom. I am not that smart. Also.)

Last fiddled with by Batalov on 2012-06-20 at 06:35
Batalov is offline   Reply With Quote
Old 2012-06-20, 10:31   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×11×172 Posts
Default

I think they're comparing it with the function-field-sieve in GF(3^426) (a 676-bit number) which an NICT group did and described in http://eprint.iacr.org/2010/090.pdf. The press release doesn't mention factorisation.

The uni-saarland link is for algorithms in large prime characteristic (though both general-prime and special-prime), which are rather different from the function field sieve that is used in small characteristic.

Last fiddled with by fivemack on 2012-06-20 at 10:36
fivemack is offline   Reply With Quote
Old 2012-06-20, 20:03   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Moved from Factoring to Science since it's not a factorization problem they solved.
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Crypto News Nick Tales From the Crypt(o) 51 2020-02-11 23:37
ElGamal crypto without prime ElChapo Math 9 2017-06-10 03:26
25-GPU cluster cracks every standard Windows password in <6 hours swl551 GPU Computing 4 2012-12-22 01:32
Crypto 2007 R.D. Silverman Lounge 2 2007-08-08 20:24
crypto game MrHappy Lounge 0 2005-01-19 16:27

All times are UTC. The time now is 09:14.

Sat Sep 26 09:14:32 UTC 2020 up 16 days, 6:25, 0 users, load averages: 1.40, 1.20, 1.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.