ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 24 Apr 2021 16:33:36 +0200Rounding up to the nearest integer that’s congruent to k mod Nhttps://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-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
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?**
Thu, 22 Apr 2021 15:15:32 +0200https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/Answer by Max Alekseyev for <p>I'm trying to perform so kind of calculation. I think you can help me.
Task : </p>
<blockquote>
<p>Rounding up to the nearest integer
that’s congruent to k mod N during halfing by 2</p>
</blockquote>
<p>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>
<pre><code> p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1
</code></pre>
<p>The curve E: <code>y2 = x3+ax+b</code> over Fp is defined by:</p>
<p>a = 0 </p>
<p>b = 7</p>
<p>The base point G form is:</p>
<pre><code>G = (Gx,Gy)
Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
</code></pre>
<p>Finally the order n of G : </p>
<pre><code>n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
</code></pre>
<p>and the cofactor is:</p>
<pre><code> h = 01
</code></pre>
<p>Explanation of task:</p>
<p>Example and code:</p>
<p>Code:</p>
<pre><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)
</code></pre>
<p><strong>question: how to round Point after halfing to full integer ? example : P_9 / 2 = P*5 not P_4 + P_05?</strong></p>
https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?answer=56779#post-id-56779"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)
Fri, 23 Apr 2021 03:49:05 +0200https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?answer=56779#post-id-56779Comment by Max Alekseyev for <p>"Rounding" in this case means simply adding <code>P_05</code> like</p>
<pre><code>P_9_half_rounded = P_9_half + P_05
print(P_9_half_rounded == P * 5)
</code></pre>
https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56794#post-id-56794The 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.Sat, 24 Apr 2021 16:33:36 +0200https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56794#post-id-56794Comment by Miroslaw for <p>"Rounding" in this case means simply adding <code>P_05</code> like</p>
<pre><code>P_9_half_rounded = P_9_half + P_05
print(P_9_half_rounded == P * 5)
</code></pre>
https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56790#post-id-56790what 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?Sat, 24 Apr 2021 12:02:14 +0200https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56790#post-id-56790Comment by Max Alekseyev for <p>"Rounding" in this case means simply adding <code>P_05</code> like</p>
<pre><code>P_9_half_rounded = P_9_half + P_05
print(P_9_half_rounded == P * 5)
</code></pre>
https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56785#post-id-56785It'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`.Fri, 23 Apr 2021 15:58:23 +0200https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56785#post-id-56785Comment by Miroslaw for <p>"Rounding" in this case means simply adding <code>P_05</code> like</p>
<pre><code>P_9_half_rounded = P_9_half + P_05
print(P_9_half_rounded == P * 5)
</code></pre>
https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56783#post-id-56783Only 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)?Fri, 23 Apr 2021 13:25:34 +0200https://ask.sagemath.org/question/56766/rounding-up-to-the-nearest-integer-thats-congruent-to-k-mod-n/?comment=56783#post-id-56783