Timeline for More Knowledge Integer Factorization
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2016 at 6:38 | history | tweeted | twitter.com/StackCrypto/status/811098376154611712 | ||
| Dec 19, 2016 at 13:01 | vote | accept | ChaosCoder | ||
| Dec 19, 2016 at 12:37 | answer | added | fgrieu♦ | timeline score: 3 | |
| Dec 19, 2016 at 8:30 | comment | added | ChaosCoder | Ah okay, no I don't. That took longer than needed. Why not add an answer to this question? | |
| Dec 19, 2016 at 8:12 | comment | added | fgrieu♦ | @ChaosCoder, Hint: do you learn anything about a permutation when given the images $x_j$ of unknown random elements $b_j$ by this permutation? | |
| Dec 18, 2016 at 12:58 | comment | added | ChaosCoder | @fgrieu: Could you elaborate on your comment? What does it mean that every $b_j \rightarrow x_j$ is a permutation for my question? Does it help you find $a$? | |
| Dec 17, 2016 at 17:49 | comment | added | fgrieu♦ | Knowing $x_1$ really leaves you with $\varphi(p−1)$ possible pairs of numbers, where $\varphi$ is the Euler totient function. Hint: show that for any fixed $a\in\mathbb Z_{p-1}^*$ (the subset of $\mathbb Z_{p-1}$ wich elements are coprime with $p-1$), the function $b_j\to x_j$ is a permutation of $\mathbb Z_{p-1}^*$; conclude. | |
| Dec 17, 2016 at 17:39 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Add necessary parenthesis
|
| Dec 17, 2016 at 14:02 | comment | added | Geoffroy Couteau | With a single pair, you have many possible solution, but the set of valid solutions is easy to compute, it cannot be seen as a hard problem. With two equations, you get the common factor by computing a gcd, and recovering the remaining factors takes one inversion and two modular multiplications then. | |
| Dec 17, 2016 at 13:25 | comment | added | SEJPM | This is about the same problem as recovering the private key from DSA signatures: You always have at least one more unknown variable than equations. | |
| Dec 17, 2016 at 10:34 | history | asked | ChaosCoder | CC BY-SA 3.0 |