maan's profile - activity

Thank you very much. Forgot to say I'm new to sage math. Fascinating it is. I didn't knew it can be converted to a polyn

Is there a way to check if a given Elliptic-curve in a finite field has an element with a certain $x$ value? Hi, I alrea

Hi, I already found out how to generate an elliptic curve in a finite field in sagemath. How to get its oder, an element and some more. E.g.

E = EllipticCurve(GF(43),[2,8]);
E.order();                      
E.gens();                       
E.random_element()

But is there a way to check if the EC contains a point with a given x-coordinate?

(which returns a point including the y-coordinate as well)

Or as alternative a function which searches for a point closest to a given x value.

(For small EC I could just search among all elements but target usage is an EC with very high order)

Is there a way to check if a given Elliptic-curve in a finite field has an element with a certain $x$ value? Hi, I alrea

@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

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

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)

That only works with equations which have only one variable, right? ($k$ in example)

I would like to solve an equation like

solve( ((k^2)%17)==8,k)

or

R = GF(17)
solve(R(k)^2==8,k)

or as math equation: $k^2 \equiv 8 \mod 17$
This would be true for e.g. $k=5$
If I use the solve function above in sagemath I get an empty result $[]$ for first and 'self must be a numeric expression' for second.

How can I solve such equation?

ty, very informative pdf

Hi, I'm new to sagemath.
Is there any way to so calculate/solve/find a short version of a recursive defined sequence?

E.g. I have a sequence like: (Fibonacci)

def f(n):                            
        if n == 0:  
                return 0  
        if n == 1:  
                return 1
        if n == 2:
                return 1
        else:
                return f(n-1)+f(n-2)

How can I compute a short form of $f_n$?

In this example case $f_n$ would be:
$f_n=\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$

Edit: Thanks to Emmanuel I found how to solve those equations in pdf:

from sympy import Function,rsolve  
from sympy.abc import n  
u = Function('u')  
f = u(n-1)+u(n-2)-u(n)  
rsolve(f, u(n), {u(0):0,u(1):1})  

-sqrt(5)*(1/2 - sqrt(5)/2)**n/5 + sqrt(5)*(1/2 + sqrt(5)/2)**n/5