Mă uitam la elementele de bază ale ecc și am găsit exemplele de pe Internet fie folosesc curba de domeniu continuă, fie folosesc un număr prim foarte mic p ca 17 într-un domeniu discret pentru a arăta punctele.
Sunt chiar curios că dacă pot găsi un punct cu un foarte mare p in practica. De exemplu, secp256k1 folosește un foarte mare p=2^256â2^32â977 în domeniu (p,a,b,G,n,h).
Mai jos este codul python pe care îl folosesc pentru a deduce posibilul întreg al lui y din rezolvarea ecuației cu intervalul întregului X. Spre surprinderea mea că nu există nicio descoperire chiar și în intervalul de 1 milion!
Deci întrebarea mea este, este mai jos codul, nu? Și în al doilea rând, dacă este corect sau corectat de un expert real, ce interval de valori ar trebui să încerc?
P.S.
Ma intreb cum punct generatorul G este selectat, de asemenea. Dar asta ar putea avea nevoie de o înțelegere mai profundă a subiectului.
import matematică
# secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
A = 0
B = 7
#nist P256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
def in_curve(x):
curba = x**3 + A*x + B
y_float = math.sqrt(curbă)
dacă abs(math.modf(y_float)[0]) < 0,0001 sau \
(1 - abs(math.modf(y_float)[0]) < 0,0001):
# print(y_float)
# bug: y_int = int(math.modf(y_float)[1])
y_int = int(round(y_float))
dacă y_int * y_int == (curbă):
print(y_int)
returnează y_int
return Niciunul
pentru x în interval (1, 1000000):
y = curba_în(x)
dacă y nu este Niciunul:
print(x, y)
Actualizare 1
Codul anterior este greșit, deoarece virgulă mobilă sqrt() va cauza o eroare inacceptabilă la convertirea lui înapoi în număr întreg.
Dar, după înlocuire math.sqrt() la math.isqrt(), tot nu face lucrurile rezonabile.
Actualizare 2
Mulțumesc sfaturilor tuturor răspunsurilor în thread. Folosind punctul generator pentru a-mi verifica algoritmul, acum știu clar de ce nu reușeam.
Ideea este, pe lângă utilizarea % pentru toate înmulțirile și adunările, I ar trebui să utilizați și rădăcina pătrată modulară pentru a găsi soluția, în loc de rădăcină pătrată întreagă împreună cu %. Este o utilizare totală greșită a % desigur.
Codul modificat trece testul cu niște vectori de testare.
import modular_sqrt
# de exemplu. Folosisem codul de la https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# vă rugăm să cereți permisiunea dacă utilizarea depășește domeniul educațional pentru pasionați și enumerați întotdeauna creditul fiind un om decent ;-)
# nist P256, preluat de pe https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109
def get_y_in_curve(x):
y2 = x**3 + A*x + B
y_int = modular_sqrt(y2, P)
dacă y_int și ((y_int * y_int) % P) == (y2 % P):
returnează y_int
return Niciunul
afirmă get_y_in_curve(Gx) == Gy
