This is an archived, readonly copy of the UnitedTI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's
General Open Topic subforum. Some of these topics may also be directlylinked to active Cemetech topics. If you are a Cemetech member with a linked UnitedTI account, you can link UnitedTI topics here with your current Cemetech topics.
Open Topic & UnitedTI Talk =>
General Open Topic
Author 
Message 

fullmetalcoder
Member
Joined: 01 Aug 2009 Posts: 139

Posted: 15 Dec 2009 02:17:49 pm Post subject: 


I stumbled upon that recent submission to arxiv.org : http://arxiv.org/abs/0912.2269
It claims to offer an efficient (i.e polynomial and more precisely O(n^3) ) algorithm to compute discrete logarithms over the cyclic groups of integers modulo p which is closely related to the problem of integer factorization. I've not checked it thoroughly but it might be quite a breakthrough.
edit : after a quick read I'm unsure whether the claim is for a O(p^3) complexity where p is the order of the group (which wouldn't be particularly impressive given that existing algorithms achieve O(sqrt(p)) ) or O(n^3) complexity where n is a number of bits of the input (which of the three inputs btw?). The provided code seems to back the first hypothesis whereas the text suggest that it might be the second...
Last edited by Guest on 15 Dec 2009 02:37:52 pm; edited 1 time in total 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 15 Dec 2009 03:29:47 pm Post subject: 


If it works, then that is amazing. But what does it have to do with Integer factorization. Can you explain?
If it works well, I can write up a quick java program for it.
All I understood was that X^{k}=y and that, I think, this finds k. Is that right? 

Back to top 


fullmetalcoder
Member
Joined: 01 Aug 2009 Posts: 139

Posted: 15 Dec 2009 06:30:32 pm Post subject: 


Graphmastur wrote: But what does it have to do with Integer factorization. Can you explain?
Basically, given (x, y, p) it solves the equation :
x^{k}=y (mod p)
The relation to integer factorization is not obvious because factorization is a somewhat more general problem. However these two problems are closely related in that most algorithms solving one can relatively easily be adapted to solve the other. Which means that even if the paper was a breakthrough some work would still be required to come up with a new algorithm for integer factorization.
A couple of links in case you want to dive into the topic :
http://en.wikipedia.org/wiki/Discrete_logarithm
http://www.cs.toronto.edu/~cvs/dlog/research_paper.pdf
As for the paper itself, here's the catchphrase (emphasis mine), provided G refers to the order of the considered cyclic group :
Quote: The algorithm obtains a computational complexity that is polynomial in the G and polynomial in the number of digits (bits) in G . Because all known algorithms had exponential complexity re the number of bits of G.
The only problem is that the proof is not all that convincing on first look due to its rigour, or lack thereof... Testing the behavior of an implementation would tell us a little more about the likeliness of that paper to be meaningful. 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 15 Dec 2009 07:29:17 pm Post subject: 


Ummm.... 0_o
I can write a java program, given that the code is already there. Would that help? 

Back to top 


bwang
Member
Joined: 15 Mar 2009 Posts: 128

Posted: 15 Dec 2009 08:08:06 pm Post subject: 


It seems like the complexity will be at least O(p):
Quote: The outer for‐loop of our algorithm iterates over the interval 0 < k < p.
Since nothing tricky happens in said loop (no breaking out of it) we need at least p operations. 

Back to top 


simplethinker snjwffl
Active Member
Joined: 25 Jul 2006 Posts: 700

Posted: 15 Dec 2009 10:31:38 pm Post subject: 


From my understanding of RSA, it involves exponentiating a certain number (let's say C) to a number coprime to n, but C itself isn't necessarily coprime to n. That means the discrete log (base C) can take on multiple residue classes of Z/nZ, so how does this help with factoring?
Last edited by Guest on 15 Dec 2009 10:32:28 pm; edited 1 time in total 

Back to top 


fullmetalcoder
Member
Joined: 01 Aug 2009 Posts: 139

Posted: 16 Dec 2009 04:45:20 am Post subject: 


bwang wrote: Since nothing tricky happens in said loop (no breaking out of it) we need at least p operations.
Actually the test code does break out of the loop. The closer I look at this article and the more inconsistencies I spot, the most striking being the differences between the pseudocode and the sample implementation of the algorithm... Another troubling thing is that the paper suggests in its conclusion that the exponential asymptotic behavior of other algorithms came from the use of exponentation while in fact it simply comes from the simple relation between a number and its digit count... That paper might very well be crap after all. 

Back to top 


Goplat
Advanced Newbie
Joined: 26 Jun 2007 Posts: 95

Posted: 16 Dec 2009 05:05:37 am Post subject: 


It is really just the naive algorithm (keep multiplying by the logarithm base until you get to the number) with the numbers scaled down from [0,p) to [0,360).
Not only is it still exponential time in the length of p, but the example implementation given will fail if p is bigger than 50 bits or so due to floating point imprecision. 

Back to top 



Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with likeminded coders and tech and calculator enthusiasts via the sitewide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page