Jump to content
begood

CRC32('rst') == CRC32(CRC32(...(CRC32('rst')...))) de n ori

Recommended Posts

Cum l-ati face cel mai rapid, pentru orice input a-z,A-Z,0-9 de lungime 1-16 ?

Pe scurt ma intereseaza : de cate ori trebuie sa se auto-apeleze functia hash CRC32 aplicata unui cuvant format din litere mici/mari/cifre pentru a rezulta primul CRC32 al cuvantului.

Exemplu :

--------------------

cuvant : 'a'

Primul CRC32 : CRC32('a') = '6b9b9319'

Al doilea CRC32 : CRC32('6b9b9319') = '9e6016f8'

....

Al n-lea CRC32 : '6b9b9319'

Cat e n?

--------------------

Puteti posta si sursa, daca doriti.

Mi-a venit aceasta idee nastrusnica ieri noapte, dar ma cam depaseste in acest moment : Daca acest rezultat poate fi folosit pentru a determina rapid "inversele" unui hash ? Sau poate niste coliziuni ?

Link to comment
Share on other sites

Verificarea mea cam asta ar fii..


<?php
$i=2; //Initializam i cu 2 deoarece prima verificare are loc dupa apelarea functiei de 2 ori
$check=hash('crc32','a'); //Retinem prima valoare (pentru if)
$crack=hash('crc32','a'); //Initializam prima valoare inafara while-ului
while (1)
{
$crack=hash('crc32',$crack); //Apelarea functiei
if ($crack==$check)
{echo $i;break;} //Afisam contor
$i++; //Contorul
}
?>

Am sa las un server sa calculeze, sa vad daca ajunge la un rezultat.. dar nu cred..

Link to comment
Share on other sites

Nu c?uta?i optimiz?ri degeaba. Arhitectura Intel care suporta SSE 4.2 (adic? procesoarele i3,i5,i7) are func?ia crc32. A?a c? ni?te inline asm in C ar rezolva cel mai repede/eficient problema. Din p?cate nu am un asemenea procesor la îndemân? s? testez cod.

Link to comment
Share on other sites

Un brut e cea mai proasta idee, de fapt se aplica pe caz particular. Trebuie analizata functia crc32 si poate se gaseste o oarecare simetrie in prelucrarea inputurilor ce provin din codomeniu si de abia apoi determinarea numarului de rotatii si modificarea acelei functii pentru a reduce numarul de rotatii la nivel de procedeu. Si in felul asta in loc sa se faca n se fac n-1 rotatii "optimizate" si voila coliziunea.

Link to comment
Share on other sites

Nu c?uta?i optimiz?ri degeaba. Arhitectura Intel care suporta SSE 4.2 (adic? procesoarele i3,i5,i7) are func?ia crc32. A?a c? ni?te inline asm in C ar rezolva cel mai repede/eficient problema. Din p?cate nu am un asemenea procesor la îndemân? s? testez cod.

Da codu ca testam noi

Link to comment
Share on other sites

Eu nu îi v?d totu?i utilitatea. O functie de tip crc32 imi returneaz? un întreg de 32 de bi?i. (Practic returneaz? un num?r, un int). Apoi eu trebuie s? o transform in char cu itoa. (Asta cred ca invalideaza si functia ta scrisa mai sus, pentru ca $check, $crack sunt returnate ca int, si probabil aplicate ca int).

Pe langa toate astea eu nu am garantii ca algoritmul se termina

Sa presupunem ca exista secventa

W->A->B->C->........->A

Si apoi sa presupunem ca exista Q astfel incat

Q->W si W nu apartine A->B->C->........->A

Deci practic daca incercam sa aplicam algoritmul lui Q ce vom obtine

Q->W->A->B->C->........->A -> B->C->........->A -> B->C->........->A (cicleaza).

Am notat ( A->B <=> crc32(A)=B ).

Link to comment
Share on other sites

Eu nu îi v?d totu?i utilitatea. O functie de tip crc32 imi returneaz? un întreg de 32 de bi?i. (Practic returneaz? un num?r, un int). Apoi eu trebuie s? o transform in char cu itoa. (Asta cred ca invalideaza si functia ta scrisa mai sus, pentru ca $check, $crack sunt returnate ca int, si probabil aplicate ca int).

Pe langa toate astea eu nu am garantii ca algoritmul se termina

Sa presupunem ca exista secventa

W->A->B->C->........->A

Si apoi sa presupunem ca exista Q astfel incat

Q->W si W nu apartine A->B->C->........->A

Deci practic daca incercam sa aplicam algoritmul lui Q ce vom obtine

Q->W->A->B->C->........->A -> B->C->........->A -> B->C->........->A (cicleaza).

Am notat ( A->B <=> crc32(A)=B ).

algoritmul se termina, deoarece exista un numar finit de numere de lungime x.

evident ca cicleaza, dupa un anumit numar N de ori.

ma intereseaza exact acel numar de cicli, pentru diferite caractere/siruri de caractere.

Link to comment
Share on other sites

@begood am facut un mini-program care sa calculeze ce ai zis tu dar nu cred ca se va gasi prea usor acel n. Uite un print:

crca.png

Aici e arhiva: main.exe e programul si celelalte sunt sursele cu functii si codul sursa principal.(sursele sunt luate dupa un forum de autoit)

le: in print se vede "path to file", e de la compilarea veche, in program se calculeaza pentru stringuri.

LE: dupa o noapte de calculat tot nu vrea:

sampleu.png

Edited by phantomas90
Link to comment
Share on other sites

use intel sse avx / nvidia tesla / fpga de la xilinx sau altera - pentru high performance.

em, din punct de vedere matematic nu poti obtine ciclul ala daca nu esti deja in el (cu o exceptie, vezi mai jos), fiindca acel element xk este obtinut dintr-un element p, dar la tine in ciclu xk e obtinut din x (k-1), deci ar insemna ca x (k-1) este p, deci p e si el in ciclu. Singura situatie in care ceea ce zici tu se poate intampla este atunci cand intampini coliziuni.

Edited by dranaxum
Link to comment
Share on other sites

De?i am demonstrat logic ?i ra?ional r?spunul (+ argumentat) tu vii s? înjuri.

SSE4 - Wikipedia, the free encyclopedia

Mai pe romane?te î?i spun a?a : Folose?te-mi tu instruc?iunea CRC32 in asm f?r? sse4.2, ca doar o rezolva "assmeblerul la nivel de l3" (level3?!) si eu imi sterg posturile de aici.

Extra:

1) Un polinom nu trebuie sa se termine in "=0". Un polinom e un polinom si atat.

2) C(8,32/(2/1/4) - pe undeva iti lipseste o paranteza

3) Dac? tu în continuare imi afirmi c? exist? un num?r maxim de pa?i în care g?se?ti r?spunsul e clar c? nu ai în?eles nimic din ce am zis.

Link to comment
Share on other sites

nu ai demonstrat nimic si nici un argument de al tau nu e valid daca tu crezi ca o instructiune de assembler face diferenta la un calcul pentru un crc32, si normal ca exista un numar maxim de pasi, sunt o infinitate de stringuri care returneaza acelasi CRC. drept urmare o sa fac un program ce iti demonstreaza chestia asta, si vii si arunci pastile aici:) pentru ca nu am inchis o paranteza si incerci sa imi demonstrezi ca un polinom nu trebuie sa se termine in =0 inseamna ca esti certat cu matematica, daca lumea gandea la tine iti scriam din pine.

Link to comment
Share on other sites

Este absolut evident c? exist? un num?r infinit de stringuri care au acela?i crc. Dar eu î?i pot g?si un num?r infinit de stringuri pentru care problema enun?at? de begood nu are solu?ie. Am ar?tat într-un post precedent.

A? fi curios de ce un polinom trebuie s? se termine în =0.

Dac? tu spui c? nu e niciun câ?tig de performan?? atunci cei de la Intel muncesc degeaba.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...