ECDSA: Square roots, cube roots, clock (12th root), and other roots

[stwenhao]

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

[1714982993]

1714982993

[1714982993]

1714982993

[1714982993]

1714982993

[NotATether]

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

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.

[garlonicon]

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

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

How to get them?

By using numbers, where (n-1) modulo your_number is zero.

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.

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

[j2002ba2]

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. 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 = prime^power)

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 2⁵-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, a³ would be square root of 1, and not 6th.

Modulo n we get the following factors (and roots): 2⁶, 3, 149, 631, 107361793816595537, 174723607534414371449, 341948486974166000522343609283189. 7 * 2⁶ - 1 = 447 possible roots. Your example is for 2²*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.