How to solve an equation over finite field for exponent variable?
I want to resolve the following equation for exponent $n$ for given value $v$:
$$ v\equiv(r\cdot ((b+r)^n- (b-r)^n)) \cdot (2 \cdot r \cdot ((b+r)^{n-1}- (b-r)^{n-1}))^{-1} \mod P$$
with
$$r^2 = 4\cdot a+b^2 \mod P$$
and a prime $P$
Looking for a function $f(v) = n$.
The values $a,b$ are chosen in that way that for $n=[1,..,P]$ the results $v$ will be all values in ${{0,..,P-1 }\brace{ }}=\mathbb{F}_P $. That works iff there is no such root $r$ in $\mathbb{F}_P$ exists for $a, b$. If both parts in formula above are expanded only $r^2$ is left over.
Example:
$P=11; a=5; b=3 -> r^2=7$
R.<a,b,r,v,n>=PolynomialRing(GF(11))
[ r*((b+r)^n-(b-r)^n)/ (2* r*((b+r)^(n-1)-(b-r)^(n-1)) ) for n in R.base() if n>1]
[b,
(-5*b^2 + 2*r^2)/(-3*b),
(-3*b^3 - 3*b*r^2)/(b^2 + 4*r^2),
(-b^4 - 2*b^2*r^2 + 2*r^4)/(5*b^3 + 5*b*r^2),
(b^5 - 4*b^3*r^2 + b*r^4)/(-2*b^4 - 4*b^2*r^2 + 4*r^4),
(3*b^6 + 4*b^4*r^2 - 2*b^2*r^4 + 2*r^6)/(2*b^5 + 3*b^3*r^2 + 2*b*r^4),
(5*b^7 + 2*b^5*r^2 + 2*b^3*r^4 + 5*b*r^6)/(-5*b^6 - 3*b^4*r^2 - 4*b^2*r^4 + 4*r^6),
(-4*b^8 + 3*b^6*r^2 - b^4*r^4 - 5*b^2*r^6 + 2*r^8)/(-b^7 + 4*b^5*r^2 + 4*b^3*r^4 - b*r^6),
(-2*b^9 - 2*b^7*r^2 - 2*b^5*r^4 - 2*b^3*r^6 - 2*b*r^8)/(3*b^8 - 5*b^6*r^2 - 2*b^4*r^4 + b^2*r^6 + 4*r^8)]
in values: $0, 3 , 1 , 8 , 5 , 4 , 7 ,10 , 9 , 6 , 2 , 0 , 3 , 1 , ...$
There is some special case for $n=1$. With this the part which need to be inverted is $0$. In that case $v$ is assigned to 0.
As a alternative form without any root $r$ (for $n>2$): $$v\equiv \frac{2 \cdot \sum_{k=1}^{\lfloor n/2\rfloor} {n-1\choose 2k-1} b^{n-2k}(r^2)^{k} }{4\cdot \sum_{k=1}^{\lfloor (n-1)/2 \rfloor} {n-2 \choose 2k- 1} b^{n-2k-1} (r^2)^{k } } \mod P$$
in sagemath:
a,b,r,v,k,n=var('a b r v k n')
(sum( 2*binomial(n-1, 2*k-1) * b^(n-2*k)*(4*a+b^2)^(k) , k,1,floor( n/2) ))*(sum(4* binomial(n-2, 2*k-1) * b^(n-2*k-1)*(4*a+b^2)^(k) , k,1, floor( (n-1)/2) ))^(-1)-v
But only got it working with normal variables.
How can I solve such equation in sagemath?
R.<n>=PolynomialRing(GF(11))
(2*k-8).roots(); #multiplication works
(2^k-8).roots(); #power not working
($a,b,r^2$ can be exchanged with current values)
Warning: the exponentiation by a variable is not part of defined operations on polynomial rings
You are trying to break a hard nut. Googling for "discrete logarithm in finite fields" may ygive you some pointers.
The parts of Sage and Sage's modules dedicated to cryptography, of which I know nothing, may give you better pointers...
@Emmanuel Charpentier thanks for response again. I did some disc. log. computing before but only stuff like $v=g^n$. The problem is something like $v =a\cdot g^n+b\cdot h^n $ or worse. Will have some closer look but so far found nothing about such equations in linked pdf (or earlier with google). However my target prime is much smaller than those used in cryptography but still too big to compute all solutions. So if it can be reduced to a normal dis. log problem it would be easy to solve.
@mann:
In Sage, the expression
v==g^nhas a meaning for v and g indeterminates of polynomials on your base field (or ring, BTW), butnmust be an integer or rational; the expression has no meaning in Sage ifnis an indeterminate.Similarly,
v.log(g)has a meaning in Sage if bothvandgare numeric expressions (vbelonging to your finite field of interest) or SR expressions; in the latter case, you get the high school-defined log(v) in g basis, i.e. log(v)/log(g).In other words in Sage, exponentiation end logarithm are defined for finite fields and congruence rings, but not on polynomial rings thereof.
@Emmanuel Charpentier in target use case all variables except $n$ are know and can be replaced by their values. $v=g^n \mod P$ could be solved with
But as you wrote it would be polynomial ring