Given a value $v$ which is in same group as the generator $g$ modulo prime $P$. The group size is a prime $s$.
$v = g^a \mod P$

Only known values are $v,g,P,s$. Some (possible) computation of other values independent of $v$ is also allowed. E.g. factorization of $P-1$.

Now I'm looking for any (not trivial) property of $v$ which happen again after using $n$ times generator $g$. Or has at least a high chance. Even better if $n$ is the smallest number until it happen again.

Usage example:
$g$ is used until $v$ has this property. After this $g^n$ is used to produce the next $v'$ with same property.

With numbers:
For $P$ is not a prime there are some ways, e.g.
$P=100, g=3, v=29$
chosen property is 'last digit is equal to $1$'.
$v=29 \not\equiv 1 \mod 10 \rightarrow 29 \cdot 3 \equiv 87 \mod 100$
$87 \equiv 7 \not\equiv 1 \mod 10 \rightarrow 87 \cdot 3 \equiv 61 \mod 100$
$61 \equiv 1 \mod 10 $ $\checkmark$
out of computation before we know
$g^4 = 81 \equiv 1 \mod 10 $
with this we can predict any further value $v''$ has the property 'last digit is equal to $1$' as well
$v''=61 \cdot g^4 = 61 \cdot 81 \equiv 41 \mod 100$, and $41\equiv 1\mod 10$ $\checkmark$
$41 \cdot g^4 = 41 \cdot 81 \equiv 21 \mod 100$, and $21\equiv 1\mod 10$ $\checkmark$

Now I'm looking for the case $P$ is a prime. Due to the fact group size $s$ is also a prime it's impossible for a fixed $n$ (except trivial $n=s$). So $n$ can depend at another (fast computable) property of $v$. Or only true in most cases. Another way is a min $n_{min}$ and a max $n_{max}$ to restrict the (next) appearance of that property in small region. Some (fast) calculation at $v$ also works.

The chosen property can be anything which can be evaluated faster than computing $n$ times the product with generator $g$ or determining the exponent of $g$ to produce $v$. The number of elements which have this property should increase with group size $s$ or be adaptable and $\ll s$.

In use case the generated group should be separated without knowing $a$ but same for all $v$ and without computing all elements.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.