înregistrare Logare
Puncte:3
avatar Crypto

Sită cuadratică: Cernerea cu puteri primare

drapel et
user93353

Încerc să înțeleg algoritmul Quadratic Sieve.

Momentan sunt blocat la partea de cernere.

Să presupunem că numărul care trebuie factorizat este 9788111. Mă hotărăsc să caut factori 50-smooth. Baza mea inițială a factorilor (FB) = $p_i$ = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.

Trec prin fiecare număr din FB și puterile lor.

Pentru fiecare număr din FB, verific mai întâi dacă N este un reziduu patratic mod numărul (adică N este un QR $\pmod {p_i}$. Dacă este, atunci găsesc rădăcinile.

Pentru 2, este trivial să verifici dacă N este un QR $\pmod 2$. Puteți extinde acest lucru și pentru puteri de 2. Pentru alte numere prime, puteți utiliza criteriile lui Euler pentru reziduuri cuadratice pentru a verifica dacă N este un QR $\pmod {p_i}$. Dacă este un QR, atunci puteți folosi Tonelli-Shanks pentru a găsi rădăcinile și apoi sită cu acel prim.

Ce fac eu pentru puterile prime? Pentru e.q. $5^2$, cum verific dacă $t^2 \equiv N \pmod {5^2}$ are o solutie? Există vreun test sau o regulă pentru a verifica acest lucru înainte de a încerca să găsesc rădăcina?

Pentru puterile prime mici precum $5^2$, este posibil să găsiți manual verificarea dacă N este un QR $\pmod {{p_i}^n}$, dar cum o faci pentru puteri primare mai mari?

102
1 + 0
Puncte:3
fgrieu avatar Crypto
drapel ng
fgrieu

Amintiți-vă că sita cuadratică (de bază) necesită găsirea unora $x$ cu $x^2-N$ neted. La aceasta, adaugă logaritmul (scalat, aproximativ) al $p_i$ la mici divizori ${p_i}^m$ de $x^2-N$ în index $x>0$ a unui tablou. Acest lucru este relativ rapid, deoarece doar două din ${p_i}^m$ intrările din matrice trebuie să fie atinse pentru fiecare ${p_i}^m$.

Ce să faci pentru puterile prime (adică ${p_i}^m$ pentru $m>1$)?

Opțiunea leneșă și suboptimă este să le ignori în faza de cernere, compensând printr-un prag neted mai mic și/sau mai multe prime în bază.

O variantă mai bună este să rezolvi $x^2\equiv N\pmod{{p_i}^m}$, iar apoi sită pentru ${p_i}^m$ așa cum am făcut pentru $p_i$. Pentru prim impar $p_i$, am rezolvat deja $x\equiv N\pmod{p_i}$, să spunem că are (două) soluții $x_j\in[0,p_i)$. Cele (două) soluții ale $x^2\equiv N\pmod{{p_i}^m}$ în $[0,{p_i}^m)$ sunt $${x_j}^{({p_i}^{m-1})}\cdot N^{({p_i}^m - 2{p_i}^{m-1} + 1)/2}\bmod { p_i}^m$$

Dickson atribute asta lui Tonelli. obisnuiam acest raspuns ca reîmprospătare. Formula este de asemenea în Wikipedia, cu exemple.

0 + 4
drapel et
user93353
Mulțumesc. Pentru un prim impar $p$, dacă $x^2 \equiv N\pmod p$ are o soluție, atunci este garantat că $x^2 \equiv N\pmod {p^m}$ are și o soluție. Știu că acest lucru nu este adevărat pentru puterile lui 2. Dar este același lucru pentru numerele prime impare sau este garantat?
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
@user93353: Da, pentru un prim impar $p$, dacă $x^2\equiv N\pmod p$ are o soluție, atunci este garantat că și $x^2\equiv N\pmod {p^m}$ are o solutie. Sunt cel mult două, modulo $p^m$.
0
Răspunde
drapel et
user93353
Grozav! Cred că am presupus că nu este (la fel cum nu este pentru puterile lui 2).Întreaga mea întrebare devine lipsită de sens dacă este garantată. Există vreo dovadă sau teoremă care să arate acest lucru? O referință într-o carte?
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
@user93353: Sursa Dickson (ea însăși citându-l pe Tonelli) de la sfârșitul răspunsului meu este cea mai bună pe care am găsit-o până acum. [Nota HAC 3.41](https://cacr.uwaterloo.ca/hac/about/chap3.pdf#page=16) afirmă că este ușor să găsești rădăcini pătrate într-un câmp de ordinul unei puteri prime, incluzând astfel modulo un prim putere, dar, din păcate, justificarea folosind faptul 3.42 și metoda, pare să acopere doar primul 2. O dovadă directă a formulei lui Tonelli (în răspunsul meu) ar putea fi posibilă, prin pătrare și simplificare.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.