Rounding up to the nearest integer that’s congruent to k mod N

asked 2021-04-22 15:15:32 +0100

Miroslaw
35 ●3 ●8 ●13

I'm trying to perform so kind of calculation. I think you can help me. Task :

Rounding up to the nearest integer that’s congruent to k mod N during halfing by 2

We have curve: The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

  p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
    = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

The curve E: y2 = x3+ax+b over Fp is defined by:

a = 0

b = 7

The base point G form is:

G = (Gx,Gy)
Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G :

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

and the cofactor is:

 h = 01

Explanation of task:

Example and code:

Code:

p_string = 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'
p = ZZ( '0x' + p_string.replace(' ', ''))
p
E = EllipticCurve( GF(p), [0, 7] )  
E
n_string = 'FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'
n = ZZ( '0x' + n_string.replace(' ', '') )
half_mod_n = 1 / GF(n)(2)     

half_mod_n = ZZ(half_mod_n) 

#first point on curve and Generator of curve
xP = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yP = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
P = E.point( (xP, yP) )

#Point no 10 of the curve is multiply Generator and 10
P_10 = P * 10

#Point no 9 of the curve is multiply Generator and 9
P_9 = P * 9

# test halfing Point by 2

P_10_half = P_10 * half_mod_n

print("is P_10 after halfed by 2 is equal P5 : ",(P*5)==P_10_half)


P_9_half = P_9 * half_mod_n
# it is P_9_half = P_4 + P_05
P_4 = P*4
P_05 = P * half_mod_n


print("is P_9 after halfed by 2 is equal P4 + P_05 : ",(P_4+P_05)==P_9_half)

print(" it is possibiliy mult generator with float point P *1.5 : ",P*1.5)

question: how to round Point after halfing to full integer ? example : P_9 / 2 = P*5 not P_4 + P_05?

edit retag flag offensive close merge delete

add a comment

Comments

Only if you know what kind Points it is. Is there any function which can round to the nearest integer during halfing by 2 ( i mean modulo)?

Miroslaw ( 2021-04-23 13:25:34 +0100 )edit

It's not possible unless you know what multiple of P a given point is, which in general amounts to computing the discrete logarithm base P.

Max Alekseyev ( 2021-04-23 15:58:23 +0100 )edit

what is doing and how (inside function):

half_mod_n = 1 / GF(n)(2)     

half_mod_n = ZZ(half_mod_n)
P_9 = P * 9 * half_mod_n

and then how P_9 *0,5 = P4_5? is calculated and what kind precision is doing sqrt inside function? where I can see the function? how it is written?

Miroslaw ( 2021-04-24 12:02:14 +0100 )edit

The multiples of P, that is $\{O,P,2P,\dots,(n-1)P\}$ forms a cyclic group. Since $n$ is odd, you can also define half_mod_n = (n+1)/2, and it is an integer. No precision or sqrt is involved as all calculations are exact.

Max Alekseyev ( 2021-04-24 16:33:36 +0100 )edit

add a comment

Your Answer

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

Rounding up to the nearest integer that’s congruent to k mod N

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Rounding up to the nearest integer that’s congruent to k mod N edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Rounding up to the nearest integer that’s congruent to k mod N