# DamaS

I failed this task, tho it looked the most interesting.

For reference the task was set up like so:

```
# unknown
p, q = <random n-bit primes>
A = random_matrix(Zmod(p*q), 11)
f = rand_poly(11, p*q)
# known
N = p*q
e = <random>
B = f(A)
Q = B**pow(e, -1, (p-1)*(q-1))
```

Then `pow(flag, e, N)`

is encoded in some weird way into a matrix `S`

and you
are given `S*Q^r`

and `B^r`

for some unknown `r`

. I figured the only way forward
was to find `d`

or a factoring (equivalent).

I worked up all sorts of delusions involving the characteristic polynomials of the given matrices, thinking that if I could just find the right values to feed into the right polynomials some kind of magical algebra would take place and the factoring could take place.

There’s one eigenvalue of $B$ in the base ring $Z_{m}$ (find it by doing $g(B,Q_{e})$), but I was lost for how I might use it. I wasn’t able to find the corresponding eigenvalue of $Q=B_{d}$. And the others are likely roots of irreducible polynomials that I couldn’t find either. So was also lost for how to approach something like Jordan normal.

So many delusions… I desperately hoped there was a way to compose (or
otherwise combine) the characteristic polynomials^{1} for some magical fairy
math where I could factor the polynomials in $Z$. Tried to play around
with the companion matrices (Hermite form) and base changes. Or what if I could
find a `e`

-th root of 1, if I just— But maybe— What if—

I gave up when `poiko`

finally told me I shouldn’t waste my time and that the
solution was stupid (he was spoiled by looking at others discussing it).
*Apparently* the `e`

wasn’t random as outlined in the script, but rather a low
`d`

was picked so you could Coppersmith it…? What’s the point…

Edit: I double checked the above and indeed,

```
d = 1839320038472006359578228121964872958248984913931534334417556559320978533688828921
```

… which would be $≈$impossible if the numbers were actually generated by
the given script. Thus I feel this is a repeat of last year’s `congurence`

task.

All kinds of stupid party-tricks like $x−ec_{B} (B)$ and similar, where you’ll suddenly stumble across some surprise that give a jolt of

*I’m on to something here*until the inevitable*never mind, I’m just stupid*.↩