$p, q$ are prime, $(p - 1) \bmod q = 0$, $(q^7 - 1) \bmod p = 0$ and $q$ is known, how to get $p$

Question

$p, q$ are primes (which is very big and can't be brute-forced), $$(p - 1) \bmod q = 0$$ and $$(q^7 - 1) \bmod p = 0$$
$q$ is given, is there any way to calculate $p$ without brute-forcing?
Also, writing code to calculate $p$ is allowed.
Have completely no idea how to solve this problem, could anyone help me?

Answer 1

From $$p-1 \equiv 0 \pmod{q} \iff p-1=qk_1 \iff p=qk_1+1 \tag{1}$$ From $$q^7 -1 \equiv 0 \pmod{p} \iff q^7-1=pk_2=(qk_1+1)k_2 \tag{2}$$

and $q$ is given. So you need to find a prime

• of form $(1)$, which, according to DAP, can yield many.
• that satisfies $(2)$, not so many.

---

Further, $ord_p(q)=7$, because $7$ is a prime number. A property of $ord$ is that it divides any $t$ s.t. $q^t \equiv 1 \pmod{p}$. If we assume $ord_p(q)<7$ it will have to divide $7$ which is prime, but a $ord_p(q)=1$ would mean $q \equiv 1 \pmod{p}$ or, from $(1)$, $qk_1 +1 \mid q-1$ (for $k_1 \geq1$) which is wrong.

---

Considering LFT, $q^{p-1} \equiv 1 \pmod{p}$ and given $ord_p(q)=7$, we have $7 \mid p-1$. If $q \ne 7$ (and I assume it is, given it should be large), then $\gcd(7,q)=1$. Now we can improve $(1)$ and $(2)$ further.

$$p=7qk_1+1 \tag{1`}$$ $$q^7-1=(7qk_1+1)k_2 \tag{2`}$$

It's still a brute-force by $k_1$ and testing whether $7qk_1+1$ is prime (you can use "quick" probabilistic algorithms before applying precise ones, a bit of optimisation).