This is an archived, read-only copy of the United-TI 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 directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.
Open Topic & United-TI 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 Xk=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 :
xk=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 like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
