Timeline for What are the solutions for discrete integers b, d to $a^b \equiv c^d \pmod p$ where $p$ is a large prime number?
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2014 at 5:46 | vote | accept | riseup | ||
| Apr 22, 2014 at 8:21 | comment | added | Greg Martin | Don't worry - if I had to apologize every time I wrote something imperfect on this site, I'd never have time for anything else! | |
| Apr 22, 2014 at 6:19 | comment | added | user45639 | @GregMartin : yes, you're perfectly right, I apologize for stupidly writing without thinking twice. Thanks. | |
| Apr 21, 2014 at 6:52 | history | edited | Asaf Karagila♦ | CC BY-SA 3.0 |
deleted 11 characters in body; edited title
|
| S Apr 21, 2014 at 6:39 | history | suggested | Seirios | CC BY-SA 3.0 |
LaTeX corrections
|
| Apr 21, 2014 at 6:09 | review | Suggested edits | |||
| S Apr 21, 2014 at 6:39 | |||||
| Apr 20, 2014 at 18:25 | answer | added | Achim Krause | timeline score: 1 | |
| Apr 20, 2014 at 17:13 | comment | added | Greg Martin | @Smaug: it's not enough to find a primitive root - you'd then need to express both $a$ and $c$ as powers of the primitive root, which is a special case of the original problem. | |
| Apr 20, 2014 at 13:41 | comment | added | Gerry Myerson | Note the case $c=1$ is asking to find the order of $a$ modulo $p$ (if you aren't satisfied with the easy solutions), and if $p$ is a large prime it may be infeasible to factor $p-1$, so that approach is ruled out. | |
| Apr 20, 2014 at 11:41 | comment | added | joro | If $c=a^x$ you get something quite close to discrete logarithm. | |
| Apr 20, 2014 at 9:42 | comment | added | user45639 | I'sorry for the bad editing (see above)...I've got the feeling that it is equivalent to find efficiently the smallest primitive root mod p. If you name it g(p), it seems that Burgess (1962) proves that for every a>0, there exists a constant C(a) such that g(p)< C(a) p^(0.25+a) , which is not so bad an upper bound. | |
| Apr 20, 2014 at 9:31 | comment | added | user45639 | I've got the feeling that it is equivalent to ask for an efficien, | |
| Apr 20, 2014 at 9:12 | comment | added | riseup | so the easy solutions without doing much work are: b = d = 0 (b = d = (p-1) and (maybe? (p-1)/2)). I am interested in the other solutions though and what this problem might be called | |
| Apr 20, 2014 at 8:47 | comment | added | riseup | @AlexDegtyarev -- I am wondering this myself, is there a way to show that this is the case? I can think of one way it is not, and that is when the ratio of log(c) to log(a) is a rational number -- then this is trivial to solve. What about when log(c) to log(a) is irrational? | |
| Apr 20, 2014 at 8:45 | comment | added | riseup | One further restriction -- a^b (mod p) and c^d (mod p) should be between 2 and (p-1) | |
| Apr 20, 2014 at 8:40 | comment | added | The Masked Avenger | You could start with b and d both p-1, and try divisors of p-1 after that. | |
| Apr 20, 2014 at 8:38 | comment | added | joro | $b=d=p-1$ I suppose. Sometimes $(p-1)/2$. | |
| Apr 20, 2014 at 8:32 | comment | added | Alex Degtyarev | I think what you are asking is the discrete logarithm problem, which is one of the foundations of the modern cryptography. | |
| Apr 20, 2014 at 8:20 | review | First posts | |||
| Apr 20, 2014 at 8:32 | |||||
| Apr 20, 2014 at 8:00 | history | asked | riseup | CC BY-SA 3.0 |