Ask Your Question
0

Set a specific polynomial as a divisor of hyper elliptic curve

asked 2018-01-06 14:49:39 -0500

sherifasagewad gravatar image

If I have a hyperelliptic curve of genus 2 = y2+( x2+x)y = x5+ x3 +1

and reduced divisor for the curve in Mumford is (x2+18x, 17x+1).

the two was given, I can construct the curve: as k. = GF(next_prime(2^160)); R.<x> = k[]

C = HyperellipticCurve(x^5 + x^3 + 1, x^2+x)

How to set (x2+18x, 17x+1) as it's divisor

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-01-07 01:41:17 -0500

dan_fulea gravatar image

References:

http://doc.sagemath.org/html/en/reference/curves/sage/schemes/hyperelliptic_curves/jacobian_morphism.html

https://en.wikipedia.org/wiki/Imaginary_hyperelliptic_curve

The question implicitly assumes there is such a divisor. In order to have a "normal situation" (small(er) prime $p$, so that the prints are suited to the width of this page, that still captures the solution, its idea, and where the claimed divisor is really a divisor) let us make a small computation in $\mathbb{Z}[x]$:

R.<x> = ZZ[]
f, h = x^5 + x^3 + 1, x^2 + x
u, v = x^2 + 18*x, 17*x + 1
(f -h*v - v^2) % u

This gives:

sage: (f -h*v - v^2) % u
105283*x

Note that we have the factorization:

sage: factor(105283)
127 * 829

So let $p$ be one of the two factors, my choice is $127$. We will work with this prime a while. Finally there will be also the following bigger prime $p$ involved in a small note:

sage: p = next_prime(2^160)
sage: p
1461501637330902918203684832716283019655932542983

Then we can initialize the corresponding divisor in Mumford coordinates as follows:

p = 127
K = GF(p)
R.<x> = K[]

f, h = x^5 + x^3 + 1, x^2 + x
C = HyperellipticCurve( f, h )
J = C.jacobian()
X = J(K)

u, v = x^2 + 18*x, 17*x + 1
D = X( [u,v] )
print D

This gives:

(x^2 + 18*x, y + 110*x + 126)

Observation:

sage: K(110/126)
17

Note that modulo $p=127$ we have the fulfilled condition that u divides $v^2+vh-f$.

sage: factor( v^2 +v*h - f )
(126) * x * (x + 18) * (x^3 + 109*x^2 + 54*x + 118)

Note: A more sophisticated way to get the divisor $D$ among those with given $u$ is as follows. The roots of $u=x(x+18)$ are $0$ and $-18$. We associate the corresponding points / lifts $P, Q$ as follows:

CP, CQ = C.lift_x(0), C.lift_x(-18)
JP, JQ = J(CP), J(CQ)
print "JP     = %s" % JP
print "JQ     = %s" % JQ
print "+JP+JQ = %s" % (+JP+JQ)
print "+JP-JQ = %s" % (+JP-JQ)
print "-JP+JQ = %s" % (-JP+JQ)
print "-JP-JQ = %s" % (-JP-JQ)

This gives:

JP     = (x, y + 126)
JQ     = (x + 18, y + 1)
+JP+JQ = (x^2 + 18*x, y + 14*x + 126)
+JP-JQ = (x^2 + 18*x, y + 110*x + 126)
-JP+JQ = (x^2 + 18*x, y + 1)
-JP-JQ = (x^2 + 18*x, y + 96*x + 1)

One of the values is our $D$.

Note: As promised, let us also do some related computations for the bigger prime 1461501637330902918203684832716283019655932542983 . Same code, but this prime:

p = next_prime(2^160)
K = GF(p)
R.<x> = K[]

f, h = x^5 + x^3 + 1, x^2 + x
C = HyperellipticCurve( f, h )
J = C.jacobian()
X = J(K)

u, v = x^2 + 18*x, 17*x + 1
D = X( [u,v] )
print D

This runs immediately into the

ValueError: Argument polys (= (x^2 + 18*x, 17*x + 1)) must be divisor 
on curve Hyperelliptic Curve 
over Finite Field of size 1461501637330902918203684832716283019655932542983 
defined by y^2 + (x^2 + x)*y = x^5 + x^3 + 1.

The error was manually reshaped.

Note: We can construct now corresponding divisors with $u=x^2+18x$ in the same way:

CP, CQ = C.lift_x(0), C.lift_x(-18)
JP, JQ = J(CP), J(CQ)
print "JP     = %s" % JP
print "JQ     = %s" % JQ
print "+JP+JQ = %s" % (+JP+JQ)
print "+JP-JQ = %s" % (+JP-JQ)
print "-JP+JQ = %s" % (-JP+JQ)
print "-JP-JQ = %s" % (-JP-JQ)

To see why i preferred to use $127$ instead, here is the result:

JP     = (x, y + 1461501637330902918203684832716283019655932542982)
JQ     = (x + 18, y + 1256459954126949149574270634668696857738035268857)
+JP+JQ = (x^2 + 18*x, y + 742142023287893335136809871805229629934516120054*x + 1461501637330902918203684832716283019655932542982)
+JP-JQ = (x^2 + 18*x, y + 1044137755672099120445471590403560727422734765797*x + 1461501637330902918203684832716283019655932542982)
-JP+JQ = (x^2 + 18*x, y + 417363881658803797758213242312722292233197777169*x + 1)
-JP-JQ = (x^2 + 18*x, y + 719359614043009583066874960911053389721416422912*x + 1)
edit flag offensive delete link more

Comments

In +JP+JQ = (x^2 + 18x, y + 14x + 126) ->

can not use the same method u, v = x^2 + 18x, 14x + 126 but using

u, v = x^2 + 18x, K(14/126)x + 1

Why?

So this mean:

11 * (x^2 + 18x, 110x + 126) not equal 11 * (x2+18x, 17x+1)

so which is reduced divisor, which i use in calculations

sherifasagewad gravatar imagesherifasagewad ( 2018-01-07 17:07:00 -0500 )edit

Please give a clear comment. All you need is D = X( [u,v] ) if you have $u$ and $v$. Unfortunately, in your post there was an error, since in order to have a correct Mumford representation the polynomials $u,v$ have to satisfy an additional condition. If the condition is satisfied, use D = X( [u,v] ). If not, then in the process of searching the correct $v$ for a given $u$ may go through lifts as above. (If the corresponding lift exists on the hyperelliptic curve.) This was but not the subject of the post, but just a help to may clear why there was an error. Please start a new post with a clear message if threre are still issues.

Yes, the points on the curve given by $(0,-126)$ and $(0,+126)$ are different. You should know yourself which divisor to use for which purpose.

dan_fulea gravatar imagedan_fulea ( 2018-01-07 21:36:17 -0500 )edit

I get the values from a research paper to ensure (u, v) are correct

A Secured Cloud System using Hyper Elliptic Curve and in sage: p = 4112543547855339322343814790708185367671872426434747235319998473455582535888229747778325047393413053

K = GF(p) R.<x> = K[]

f = x^5 + 7943193x^4 + 6521255x^3 + 1065528x^2 + 3279922x + 3728927 C = HyperellipticCurve( f ) J = C.jacobian() X = J(K)

u, v = x^2 + 22457213658579645161x + 62960708771725664757, 65279057408798633572x + 32004384923913711271 D = X( [u,v] )

"error"

sherifasagewad gravatar imagesherifasagewad ( 2018-01-09 17:19:24 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-01-06 14:49:39 -0500

Seen: 52 times

Last updated: Jan 07