To efficiently find an ( x ) with ( 0 < x < q ) such that ( g^x \bmod p < p/k ) in a Schnorr group, we analyze the problem as follows:

Key Observations:

1. Schnorr Group Properties: The group is generated by ( g ) with prime order ( q ), meaning ( g^x \bmod p ) for ( x \in {1, 2, \ldots, q-1} ) produces exactly ( q ) distinct elements (the subgroup ( G )).
2. **Distrib...

Short answer No asymptotically better method than “scan powers until you hit” is known or expected in the generic setting. The expected cost to find an x with g^x mod p < p/k is Θ(k) group multiplications. For your concrete parameters (p ≈ 1024 bits, q ≈ 160 bits, k ≈ 2^64), this is utterly infeasible in practice.

Why Θ(k) is optimal

• Let I := {1, …, ⌊(p−1)/k⌋}. For a Schnorr/DSA subgroup of pri...

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)...

We can re‐state the problem very simply as follows:

• We have a cyclic subgroup of \Z_p^* of prime order q and generator g.
• We choose an exponent x uniformly at random in [0,q) and look at
y = g^x mod p.
• We declare “success” if y falls into the interval
I = { 1,2,…,⌊p/k⌋ }
(so |I|≈p/k, hence Pr[y∈I]=1/k).
• We want to exhibit some x...

This is an interesting problem about finding discrete logarithms with constrained output values. Let me analyze the approaches and complexity.

Analysis of the Problem

You're looking for such that in a Schnorr group setting.

Basic Approach Analysis

The naive approach you mentioned:

• Try until
• Expected number of ...

Excellent question. You've hit upon a problem that lies at the heart of why certain cryptographic assumptions are believed to be hard.

Let's break down the problem and the existing approaches.

Summary of the Answer

You are correct in your analysis. The simple "try-and-see" approach with an expected cost of **O(k) group operations is the best known general-purpose algorithm for this problem....

Let

 I(k) = { u ∈ ℤ : 0 < u < p/k },

and let

 S(k) = { x ∈ {1,… ,q–1} : g^x mod p ∈ I(k) }.

Because g generates the subgroup of order q, the map

 x ↦ g^x (mod p)

is a permutation of that subgroup, hence for a uniformly random exponent x the value g^x is uniformly distributed among the q non-zero subgroup elements.
Therefore

 |S(k)| = q · |I(k)|/p ≈ q/k . ...

<think> We are working in a Schnorr group, which is a subgroup of $\mathbb{Z}_p^*$ of prime order $q$. The generator is $g$, and we are given that $p/g$ is small (which implies that $g$ is close to $p$). We are to find an $x$ (with $0 < x < q$) such that $g^x \bmod p < p/k$ for a given $k$ that is sizable but much less than $\sqrt{q}$.

The problem is to exhibit such an efficiently. The trivia...

Finding Such That in a Schnorr Group

This problem asks for an efficient method to find an exponent (where ) such that in a Schnorr group, specifically as used in DSA with parameters:

• : a 1024-bit prime modulus
• : a 160-bit prime order (divides )
• : a generator of a subgroup of order , computed as
• : ...