Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: stwenhao on July 23, 2022, 11:22:16 AM


Title: ECDSA: Square roots, cube roots, clock (12th root), and other roots
Post by: stwenhao on July 23, 2022, 11:22:16 AM
Why this value can be rotated like in a clock?
Code:
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^1=1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^2=ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283cf
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^3=70ad49ae7f8574ecab641a42b3a24f22d6374023944cc665a6bcaeb0f37bbf78
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^4=ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^5=52f304001743db1f87b8daf4cc4e75bfde925893336d9f80b9a2e8393ed84778
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^6=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^7=e245ba5197be6632dc54c0b218ac269bc309f5564e697956d2b898151b92c941
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^8=5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^9=8f52b651807a8b13549be5bd4c5db0dbe4779cc31afbd9d61915afdbdcba81c9
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^a=5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd73
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^b=ad0cfbffe8bc24e07847250b33b18a3edc1c84537bdb00bb062f7653915df9c9
1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800^c=0000000000000000000000000000000000000000000000000000000000000001
Are there other such values? How to get them? Is it possible to reach them for some other value like 2 or 3, for example to get it in five moves or in seven moves? Also, it is true for "n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", is it possible to get it based on "p=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"?

Title: Re: ECDSA: Square roots, cube roots, clock (12th root), and other roots
Post by: NotATether on July 23, 2022, 11:45:04 AM
Quote from: stwenhao on July 23, 2022, 11:22:16 AM
Why this value can be rotated like in a clock?

Apparently because N^2 = 1, and this value (let's call it E) gets to N in 6 multiplications.

And E^4 = E^2-1. I don't know what to make of this except E^2 would be sqrt(E^2-1), try checking that. (I am not sure how'd you compute a square root in a group!)

Quote
Are there other such values? How to get them? Is it possible to reach them for some other value like 2 or 3, for example to get it in five moves or in seven moves? Also, it is true for "n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", is it possible to get it based on "p=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"?

Without a specialized ECC calculator you'd have to experiment with different values manually.

If there was a way to find roots, then you could create arbitrary-sized roots of N (sqrt, cbrt, etc.) and generate a full circle that is about twice the size as the root being taken.

Title: Re: ECDSA: Square roots, cube roots, clock (12th root), and other roots
Post by: garlonicon on July 23, 2022, 01:34:11 PM
Quote
Why this value can be rotated like in a clock?
Because "n-1=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140" is divisible by 12.
Code:
(n-1)/12=155555555555555555555555555555553a393d1339460d5a4ffc328bbc048570
7^((n-1)/12)=1dba45ae684199cd23ab3f4de753d962f7a4e79060df26e4ed19c677b4a37800

Quote
Are there other such values?
Yes, as long as you can divide n-1 by some number and get zero as a remainder, you can do that:
Code:
(n-1)/0xc0=155555555555555555555555555555553a393d1339460d5a4ffc328bbc04857
5^((n-1)/0xc0)=4a460aa42654feb433f9d44c55cc8d996edcddbe656d171aa9560ea1dbde702f
4a460aa42654feb433f9d44c55cc8d996edcddbe656d171aa9560ea1dbde702f   1
5f37f2a42660253465eca8c8a7c7c52f7363dbcd9d1169f04c727eef8bb63a26   2
...
b61a6db116503f62906a783b0a3ac599b4e10a7cf1aa5322413f3dd67d564134   3f
0000000000000000000000000000000000000000000000000000000000000001   40

Quote
How to get them?
By using numbers, where (n-1) modulo your_number is zero.

Quote
Is it possible to reach them for some other value like 2 or 3, for example to get it in five moves or in seven moves?
No, because (n-1)%5 is equal to one, and (n-1)%7 is equal to two.

Quote
is it possible to get it based on "p=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"?
Of course, but not for 12. For example for 14:
Code:
p/14=1249249249249249249249249249249249249249249249249249249236db6d71
3^(p/14)=ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^1=ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^2=a2ab335e7a5b9784e9425431411a8f02a1e39029745c0d2567e7b217154fe2cb
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^3=63e09d3409537d4a2e723d236bf355f23c9721655c4a4de25898a240326d3f7d
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^4=828ae4be889531689c205b202218166ea14a2d24995eb1765297429aef1bd456
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^5=ff5daae1f719de20ab35810f88121fcbbf2eeee04bec58ceff13c6c490da1952
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^6=2ae8078df04e0b9fdd3ba4e7ce590f5c983cb2b771cbdf6e4f120ebe20910ef6
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^7=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^8=1320286b0d2e86dd770969f9c279c0f0205ba04028b008a74e1b65949e4a92b7
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^9=5d54cca185a4687b16bdabcebee570fd5e1c6fd68ba3f2da98184de7eab01964
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^a=9c1f62cbf6ac82b5d18dc2dc940caa0dc368de9aa3b5b21da7675dbecd92bcb2
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^b=7d751b41776ace9763dfa4dfdde7e9915eb5d2db66a14e89ad68bd6410e427d9
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^c=00a2551e08e621df54ca7ef077ede03440d1111fb413a73100ec393a6f25e2dd
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^d=d517f8720fb1f46022c45b1831a6f0a367c34d488e342091b0edf140df6eed39
ecdfd794f2d1792288f696063d863f0fdfa45fbfd74ff758b1e49a6a61b56978^e=0000000000000000000000000000000000000000000000000000000000000001

Title: Re: ECDSA: Square roots, cube roots, clock (12th root), and other roots
Post by: j2002ba2 on July 23, 2022, 02:20:38 PM
Quote from: stwenhao on July 23, 2022, 11:22:16 AM
Why this value can be rotated like in a clock?
...
Are there other such values? How to get them? Is it possible to reach them for some other value like 2 or 3, for example to get it in five moves or in seven moves? Also, it is true for "n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", is it possible to get it based on "p=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"?

There are many such values. Eventually what are you looking for is Primitive root modulo n (https://en.wikipedia.org/wiki/Primitive_root_modulo_n). From it you can get every possible root of 1.

Here is an algorithm for finding a primitive root modulo prime p (that is (p-1)-th root of 1):
Code:
r = 1
factors = factor(p-1)
for [prime, power] in factors:
    x = (p-1)/prime
    y = (p-1)/(prime ** power)
    for (a=2;;a++):
        b = pow(a, x, p)
        if (b != 1):
            r = (r * pow(a, y, p)) % p
            break
(prime ** power = primepower)

Modulo p we get the following roots: 2 (square), 3 (cube), 7-th, 13341, 205115282021455665897114700593932402728804164701536103180137503955397371, and any multiple of these numbers, for a total of 25-1 = 31 possible roots (2nd, 3rd, 6th, 7th, 14th, 21st, 42th,...). Each k-th prime root has k-1 possible values besides 1. However if k is composite, some of the k-1 values are the corresponding smaller root, i.e. if a is 6-th root of 1, a3 would be square root of 1, and not 6th.

Modulo n we get the following factors (and roots): 26, 3, 149, 631, 107361793816595537, 174723607534414371449, 341948486974166000522343609283189. 7 * 26 - 1 = 447 possible roots. Your example is for 22*3=12-th root.

Here are two primitive roots of 1 modulo the corresponding prime:
n: rn = 106331823171076060141872636901030920105366729272408102113527681246281393517969
p: rp = 77643668876891235360856744073230947502707792537156648322526682022085734511405


So, let's say you want a 631th root of 1 modulo n: x = pow(rn, (n-1)/631, n). Since 631 is prime number, you could get all 631 possible 631-th roots of 1 (modulo n) by rising x to the power from 1 to 631.




Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines