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

[begood]

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 ?

[Zatarra]

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..

[Paul4games]

Cred ca o sa incerc sa scriu si eu o functie pentru asta, oricum citisem acum catva timp o metoda de a apela api-urile dupa hashul crc32 in delphi,deci cred ca o sa adaptez aceea functie la cerinta ta iar dupa aceea o sa vad daca o pot optimiza.

[em]

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.

[tromfil]

@Zatarra: De?i nu ajut? prea mult ai putea s? faci $crack=$check; în afara la while.

Ce zice @em pare foarte interesant. Sper s? revin cu un r?spuns mai lung.

[cmiN]

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.

[Zatarra]

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

[em]

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

[begood]

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.

[Petzy]

fuck me..miroase a brain aici.

Anyway, good luck in ce naiba vreti sa faceti ca eu nu inteleg nimic

scz de offtopic

[phantomas90]

@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:

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:

Edited July 9, 2011 by phantomas90

[dranaxum]

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 July 10, 2011 by dranaxum

[dragosmk]

crc32 nu se repeta o data la 2^32 iteratii?

edit

--

am citit mai bine acu, nu se aplica asta aici..

[em]

@dragosmk,

Daca s-ar repeta, atunci raspunsul lui begood ar fi fost simplu - 2^32

[cifratorul]

@xuquan: ce posturi pline de continut interesant. crezi ca ai gasit reteta succesului sa faci link-uri pentru siturile tale? sau ai citit vreun ebook care iti zice cum sa faci bani pe net

[em]

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.

[nightkhaos]

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.

[em]

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.