0
$\begingroup$

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

$\endgroup$

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.