Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
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.

This forum is locked: you cannot post, reply to, or edit 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. Sad
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
Display posts from previous:   
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
    » Goto page Previous  1, 2, 3 ... 17, 18, 19
» View previous topic :: View next topic  
Page 19 of 19 » All times are GMT - 5 Hours

 

Advertisement