ASIS CTF 2024

Bài này mình làm sau khi giải kết thúc.

Clement

Đề bài ở file source.py.

Ở bài này chúng ta cần nhập vào số \(n\). Chương trình sẽ tính \(k = n^2 + 4 n + 3\).

Hàm factoreal sẽ kiểm tra \(4 \cdot n! + n + 5 \equiv 0 \pmod k\) hay không.

Để giải bài này mình cần định lý Wilson:

Định lý Wilson

Nếu \(p\) là số nguyên tố thì

\[(p-1)! \equiv -1 \pmod p\]

Do \(k = n^2 + 4n + 3 = (n + 1) \cdot (n + 3)\), mình mong muốn tìm số \(n\) thỏa mãn hai phương trình

\[\begin{split}4 \cdot n! + n + 5 \equiv 0 \pmod{n+1} \\ 4 \cdot n! + n + 5 \equiv 0 \pmod{n+3}\end{split}\]

trong đó \(n+1\) và \(n+3\) là các số nguyên tố. Khi đó nghiệm trong modulo \(k\) theo CRT sẽ là \(0\).

Nếu \(n + 1\) là số nguyên tố, theo định lý Wilson thì \(n! \equiv -1 \pmod{n+1}\). Như vậy

\[4 \cdot n! + n + 5 \equiv 4 \cdot (-1) + (n + 1) + 4 \equiv -4 + 4 \equiv 0 \pmod{n+1}\]

Nếu \(n + 3\) là số nguyên tố thì \((n+2)! \equiv -1 \pmod{n+3}\). Khi đó

\[\begin{split}4 \cdot n! + n + 5 & \equiv 4 \cdot \dfrac{(n+3)!}{(n+2) \cdot (n+1)} + (n + 3) + 2 \pmod{n+3} \\ & \equiv 4 \cdot \dfrac{(-1)}{(n + 2) \cdot (n + 1)} + 2 \equiv 0 \pmod{n+3}.\end{split}\]

Như vậy nếu điều kiện cuối là \(4 \cdot \dfrac{-1}{(n+2) \cdot (n+1)} + 2 \equiv 0 \pmod{n+3}\) thỏa mãn thì mình đã tìm được số \(n\) cần thiết.

Đây là bài toán về coding với timeout nên chúng ta có thể lưu các số nguyên tố \(t\) bit vào file trước khi remote tới server (precompute).