Let
G = ⟨g⟩ = { g⁰ , g¹ , … , g^{q-1} } ⊂ ℤ*ₚ , |G| = q

and let

I = { 1 , 2 , … , ⌊p/k⌋-1 } ⊂ ℤ*ₚ .

We are asked for an exponent

x ∈ {1,…,q-1} (1)

such that

g^x (mod p) ∈ I . (2)

Size of the solution set

|I| ≈ p/k, so the fraction of the residues in G that lie in I is

ρ = |G ∩ I| / |G| ≈ (p/k) / (p–1) ≈ 1/k. (3)

Hence there are about

q / k (4)

different exponents x that satisfy (2).
With the concrete numbers in the question (q ≈ 2¹⁶⁰, k ≈ 2⁶⁴) we expect about 2⁹⁶ solutions.

The obvious algorithm

Starting with y = 1 = g⁰ we repeatedly multiply by g

for x = 1,2,3,…
y ← y·g (mod p)
if y < p/k : output x and stop.

Every loop produces one new group element, requires one modular multiplication and one comparison, and succeeds after an expected k iterations, because each new element is (heuristically and, up to negligible bias, provably by equidistribution) uniformly distributed over G. Cost: Θ(k) modular multiplications.

Lower bound: a generic-group argument

Assume that an algorithm 𝔄 makes t < k/2 group-operations (multiplication or inversion) and outputs an exponent x satisfying (2).

In the generic-group model the elements of G are given to 𝔄 by random labels; the only thing 𝔄 can do with a label is ask for its product with another labelled value. After t operations 𝔄 has seen at most t+1 distinct random labels, hence at most t+1 independent, uniformly random members of G. The probability that none of them is in I is

Pr[failure] = (1 – ρ)^{t+1} ≥ (1 – 1/k)^{t+1} ≥ 1 – (t+1)/k. (5)

Therefore the success probability is at most (t+1)/k.
To obtain a constant (say ≥ 1/2) success probability we must have
t ≳ k/2. Consequently any generic algorithm needs Ω(k) group operations. The “incremental” algorithm described above is therefore essentially optimal in this model.

Can number–theoretic shortcuts help?

Because p is 1024 bits while q is only 160 bits, the subgroup G is tiny inside ℤ*ₚ and seems to behave like a random set with respect to the order relation «< p/k». No known number-theoretic property correlates g^x (mod p) with the size of the residue strongly enough to beat the generic bound. Known structured attacks (baby-step-giant-step, Pollard ρ/λ, index calculus, lattice methods, Coppersmith techniques, …) all boil down to solving one or several ordinary discrete logarithms and cost ≳ √q or worse, i.e. ≳ 2⁸⁰ operations for the parameters given—well above the Θ(k)=2⁶⁴ cost of the trivial search.

Conclusion

1. About q/k exponents x satisfy g^x < p/k, so the probability that a random x works is 1/k.

2. Inspecting k group elements is both sufficient and (up to a constant factor) necessary in the generic-group model. No algorithm that is substantially faster than the naive O(k) scan is known or expected.

3. With the concrete parameters p ≈ 2¹⁰²⁴, q ≈ 2¹⁶⁰, k ≈ 2⁶⁴, the naive method costs ~2⁶⁴ modular multiplications, already far cheaper than a discrete-log attack on the 160-bit subgroup.

So, apart from obvious engineering tricks (parallelising the scan, using vector instructions, batch Montgomery multiplication, …) there is no better algorithm known, and finding such an x is believed to be as hard as the generic lower bound suggests.