BitCell

(2^x) % p = n.
p - prim, dar nu prim de tip Mersenne
n ia valori intregi de la 1 la p-1 (evident)
x intreg.

Cum as putea gasi niste solutii pentru x ?
Program stiu sa fac ca sa determin solutiile, dar as vrea o ecuatie matematica.

Orice idee e bine venita !

Nu exista o solutie matematica care sa iti confere o ecuatie pentru x la 2^x = n (mod p) dat fiind n.
Exista o conjectura la care se lucreaza, formulata de Emil Artin, care implica printre altele faptul ca exista o infinitate de grupuri Zp* pentru care 2 este generator, DAR nu pentru toate, asa ca depinde de p daca 2 este generator (daca da, poti afla in functie de n, x-ul, dar nu prin formula).

Existenta scrisa a unei solutii matematice directe ar conduce la rezolvarea acestei mici parti a conjecturii, dar ea ar fi aparut daca se putea gasi/exprima cu functii elementare. Rezolvarea e alta si cred ca ar implica cunostinte avansate de teoria grupurilor.

Multumesc mult .
LE: p != 2^y +-1, y - integer.

---

L.E. (-- 10 May 2011, 10:34 --)

... acum am realizat ca rezolvarea acestei ecuatii practic ar duce la spargerea RSA, iar RSA sta la baza securitatii informatiei din intreaga lume.

encryption : c = m^e (mod n)
decryption : m = c^d (mod n)

Aplicand asta la mine, ar fi : n^z % p = 2, iar z este inversul multiplicativ modular (sau cum se traduce) a lui x, z=x^(-1) in grupul multiplicativ Zp*.

Dar tot nu ma ajuta cu nimic.

Inca o data, multumesc pentru informatii !

Funcția modulo o exprimi matematic din teorema împărțirii cu rest : adică , sau mai frumos : (folosind funcția parte întreagă). Problema o reprezintă acea funcție care nu este de tip continuu ceea ce înseamnă că nu se poate aproxima printr-o formulă matematică elegantă. S-ar putea recurge la serii (gen Fourier), dar funcția nu este periodică. Totuși, așa cum prezintă și wikipedia, pentru un împărțitor fix, există o descompunere în serie Fourier dată de relația :

Am impresia că suma respectivă nu te satisface.