|
2005-11-25, 02:17
|
#1 |
Jun 2003
158210 Posts |
Collision algorithm for Discrete log
Does any body know anything about this? Could someone explain it to me.
How is it better than the index calculus algorithm. Citrix |
|
|
|
2005-11-25, 08:48
|
#2 | |
|
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
22×5×72×11 Posts |
Quote:
If you want to find out more, these are good search terms: "rho", "lambda", "giant step baby step" and "kangaroos", all in conjuction with "discrete log" and/or "Pollard". These methods are better than the index calculus algorithm in that they find discrete logs in any group at all. Index calculus methods work only in groups for which there is a useful notion of smoothness. Paul |
|
|
|
|
|
2005-11-25, 12:29
|
#3 |
Jul 2005
2×193 Posts |
The only references to "collision algorithm" with respect to discrete logs refer to finding collisions in hash table used by the Baby-Steps Giant-Steps algorithm for solving DL.
Index Calculus (IC) is good if the range of exponents is not limited, however most distributed-computing projects that need to solve DL (Mersenne, SoB/Riesel) have limited ranges for exponents. This means that a programing combining BSGS and SPH (Silver-Pohlig-Hellman) is much faster than IC for these projects. |
|
|
|
|
2005-11-25, 15:26
|
#4 |
|
Jun 2003
2·7·113 Posts |
Paul,
I don't think it is Phi rho. I read about it in the RSA crypto FAQ. They mention it but do not explain it. Citrix |
|
|
|
|
2005-11-25, 16:15
|
#5 | |
|
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
22×5×72×11 Posts |
Quote:
There are sources other than the RSA crypto FAQ. That's why I gave you a bunch of search terms: --- so you can find those sources relatively easily. Paul |
|
|
|
|
|
2005-11-25, 16:21
|
#6 |
|
Jun 2003
2·7·113 Posts |
I understand what you are saying and I know how all the methods work, but based on what RSA people say, it seems that the collision algorithm is a new faster algorithm.
Maybe it is just the grammar! Citrix |
|
|
|
|
2005-11-25, 16:34
|
#7 |
|
Jul 2005
2×193 Posts |
After a bit of googling there are several algorithms for solving DL due to Pollard (rho and lambda) which both mention collisions.
The following Master's Thesis has a good description of them. http://home.planet.nl/~hcdlp/mt/hcdlpV2.pdf Again, for sieving, SPH/BSGS is king. The other algorithms are more efficient at solving Discrete Log where there is no upper bound on the exponent. Have you got the link to that FAQ? Last fiddled with by Greenbank on 2005-11-25 at 16:35 |
|
|
|
|
2005-11-25, 16:53
|
#8 |
|
Jun 2003
2×7×113 Posts |
Ok! collision is same as Phi-Rho, I found the error in my understanding.
Thanks alot, Citrix |
|
|
|
 |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Help with discrete logarithm | pinnn | Information & Answers | 43 | 2021-03-18 15:40 |
| Find out a collision: AES(y, x) β y under key x | Raman | Puzzles | 0 | 2016-09-05 20:09 |
| How hard is Discrete Logarithm, really? (Joux's Algorithm) | Ken_g6 | Computer Science & Computational Number Theory | 40 | 2014-05-27 02:37 |
| Pollard Rho Discrete Log | rogue | Math | 6 | 2012-09-26 11:20 |
| On discrete logs | kpatsak | Math | 1 | 2008-02-19 04:44 |
