How to solve an equation over finite field for exponent variable?

asked 2019-11-24 21:25:03 -0600

maan gravatar image

updated 2019-11-24 23:54:27 -0600

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)

edit retag flag offensive close merge delete

Comments

1

Warning: the exponentiation by a variable is not part of defined operations on polynomial rings

sage: R.<t,u>=PolynomialRing(GF(13))
sage: t^u
---------------------------------------------------------------------------

[ Snip... ]

TypeError: u is neither an integer nor a rational

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 gravatar imageEmmanuel Charpentier ( 2019-11-25 01:31:52 -0600 )edit
1

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

maan gravatar imagemaan ( 2019-11-25 02:46:22 -0600 )edit
1

@mann:

  • In Sage, the expression v==g^n has a meaning for v and g indeterminates of polynomials on your base field (or ring, BTW), but nmust be an integer or rational; the expression has no meaning in Sage if n is an indeterminate.

  • Similarly, v.log(g) has a meaning in Sage if bothv and g are numeric expressions (v belonging 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 gravatar imageEmmanuel Charpentier ( 2019-11-25 06:37:49 -0600 )edit

@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

P = 11
g = Mod(2,P); 
v = 5
n=discrete_log(v, g)
4

But as you wrote it would be polynomial ring

maan gravatar imagemaan ( 2019-11-25 18:05:50 -0600 )edit