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

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


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
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 close merge delete

Sort by » oldest newest most voted

"Rounding" in this case means simply adding P_05 like

P_9_half_rounded = P_9_half + P_05
print(P_9_half_rounded == P * 5)

more

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)?

( 2021-04-23 13:25:34 +0200 )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.

( 2021-04-23 15:58:23 +0200 )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?

( 2021-04-24 12:02:14 +0200 )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.

( 2021-04-24 16:33:36 +0200 )edit