Inverzna funkcija

[ DarkMan @ 14.06.2004. 14:43 ] @

Znam da je matematika ali ima veze sa C-om:
Imam sledecu funkciju

Code:

DWORD func(DWORD a)
{
    DWORD b;
    b = a * 0x12345678 + 0x11111111;
    return b;
}

Da je u pitanju cista matematika inverzna funcija bi bila ovakva:

Code:

DWORD inverse(DWORD b)
{
    DWORD a;
    a = (b - 0x11111111) / 0x12345678;
    return a;
}

Medjutim ovo nije slucaj zato sto se pri proracunu odbacuju visi delovi rezultata (ne moze da stane u DWORD).
U sustini mislim da je i nemoguce napraviti inverznu funkciju u ovom slucaju ali ajde da pokusam, mozda ovde postoji neko ko provali ovo.

Jedino sto sam ja uspeo je ovaj banalan (brutalan) pristup:

Code:

DWORD inverse(DWORD b)
{
    DWORD a;
    for(a = 0; a < 0xFFFFFFFF; a++)
        if(func(a) == b) return a;
    return 0;
}

Napominjem da se nikakve izmene ne mogu raditi u prvobitnoj funkciji (odsecanja u racunu su neophodna). Meni treba resenje za inverznu funkciju.

[ milanche @ 14.06.2004. 16:10 ] @

Problem aritmetike velikih intidzera se cesto javlja u domenu enkripcije/dekripcije.
Ne moze bas lako resiti dosetkama, nego se radi mnogo promisljenijim principima.

Sabiranje i oduzimanje kako tako, ali mnozenje i delenje zahtevaju 64 bita, jer je
to velicina rezultata. Konverzija u float domen ne donosi resenje, jer float broj ima
samo 56 bita rezolucije (ako se izuzmu sign bit i mantisa).

Konverzija brojeva u double moze da ti resi problem, ali to resenje nije prenosivo
na sve platforme. Ako ti je ambicija da problem resis na tvom sistemu (predpostavljam
na Pentium/AMD masini), onda konvertuj brojeve u double, obavi aritmetiku, pa vrati
rezultat nazad u DWORD, i to bi bilo to).

Znam nekoliko biblioteka koje problem intidzerskog mnozenja velikih brojeva resavaju
u intidzerskom domenu. Uglavnom, predstavljaju broj kao string cifara, pa operisu
prakticno na stringovima, i samo na kraju konvertuju rezultat iz stringa cifara nazad
u DWORD broj. Ne koriste uopste float ili double instrukcije, i prenosive su na razne
platforme.

[ DarkMan @ 14.06.2004. 22:45 ] @

Pretpostavio sam da necu biti svhacen kako treba.
One funkcije navedene su samo primer slicnog problema.
Originalna funkcija se moze objasniti kao neka funkcija koja ce od ulaznog broja generisati neki drugi broj po poznatom sablonu. Svi brojevi sa kojima radi su 32-bit unsigned i imaju velike vrednosti tako da uvek dolazi do odsecanja visih bita.

Meni treba nacin da kreiram inverznu funkciju koja ce moci da rekonstruise ulazni parametar ako se zna rezultat. Problem nastaje bas zbog odsecanja pa direktan pristup nije moguc (bar ga ja ne znam).
Mozda je moguce naci resenje u odredjenom broju koraka ali da bude mnogo manje nego u mom resenju (sa 2^32 koraka).

[ -=Cheda=- @ 15.06.2004. 01:00 ] @

Mozda kad bi dao kod tog shablona neko uspe da ti pomogne. Daj da vidimo o cemu se radi pa da probamo... Ako ne onda 2^32 (u naj gorem slucaju) :(

[ blaza @ 15.06.2004. 05:14 ] @

Problem je u tome sto jednoznacno resenje ne postoji. U tvom primeru:

Code:

DWORD func(DWORD a)
{
DWORD b;
b = a * 0x12345678 + 0x11111111;
return b;
}

Npr. vazi:

Code:

func(1) == func(0x20000001) == func (0x40000001) == func(0x60000001) == func(0x80000001) == func (0xa0000001) == ... == 0x23456789

Koju od ovih vrednosti bi trebala da vrati inverzna funkcija inv_func(0x23456789)?

[ miličić.marko @ 15.06.2004. 15:23 ] @

>
>

[ DarkMan @ 15.06.2004. 21:44 ] @

Citat:

blaza:Problem je u tome sto jednoznacno resenje ne postoji. U tvom primeru:

Code:

DWORD func(DWORD a)
{
DWORD b;
b = a * 0x12345678 + 0x11111111;
return b;
}

Npr. vazi:

Code:

func(1) == func(0x20000001) == func (0x40000001) == func(0x60000001) == func(0x80000001) == func (0xa0000001) == ... == 0x23456789

Koju od ovih vrednosti bi trebala da vrati inverzna funkcija inv_func(0x23456789)?

Bilo bi mi dovoljno da vrati bilo koju vrednost (jedna je dovoljna), samo da bude sto brze.

[ blaza @ 15.06.2004. 22:47 ] @

Evo, smislio sam nesto na brzaka, pa ti razradi.
Zanemaricemo ono 0x11111111 - to uvek mozes oduzeti.
Imamo:

x=0x1234*0x10000+0x5678

a=c*0x10000+d
gde su c i d max 4-cifreni heksadekadni brojevi

y=x*a=(0x1234*0x10000+0x5678)*(c*0x10000+d)
y=0x123400000000*c+0x12340000*d+0x56780000*c+0x5678*d)
Y=y % 0x100000000
Y = (0x12345678*d+0x56780000*c)% 0x100000000
Sta nas interesuje: Da ako znamo Y nadjemo c i d

Zakljucak -> c ne utice na docnje 4 cifre Y
Zakljucak2 -> jedino D utice na docnje 4 cifre Y
Z=(0x1234*0x10000+0x5678)*d
Zakljucak3 -> donje 4 cifre Z zavise od 0x5678*d

Napravis petlju:

Code:

bool rezultat_d_postoji = false;
for(int d = 0; d <= 0xffff; d++)
    if(((0x5678 * d) & 0xffff) == (Y & 0xffff)){
        rezultat_d_postoji = true;
        break;
    }

Ako dobijes rezultat_d_postoji == true, tada si nasao d
Dalje racunas

Code:

DWORD YY = Y - 0x12345678*d;

Donje 4 cifre YY bice 0;
Sada vazi:
YY = 0x56780000*c
Pravis drugu petlju:

Code:

bool rezultat_c_postoji = false;
for(int c = 0; c <= 0xffff; c++)
    if((0x56780000 * c)  == YY ){
        rezultat_c_postoji = true;
        break;
    }

Ako dobijes rezultat_c_postoji, tada si resio problem, jer je a=c*0x10000 + d;
Ako ne dobijes rezultat_c_postoji, mozda bi bilo pametno vratiti se u petlju za nalazenje d i videti postoji li alternativno resenje za d, pa onda ponovo probati da li postoji resenje za c.
Mozda sam negde pogresio. Evo, ovoliko od mene, na brzaka.

[Ovu poruku je menjao blaza dana 16.06.2004. u 16:38 GMT]

[ blaza @ 15.06.2004. 22:59 ] @

Samo da primetim da problem mozes analogno dalje pojednostaviti:

d=e*0x100+f
e i f su max. dvocifreni heksadekadni brojevi
D = 0x5678*d = (0x56*0x100+0x78)*(e*0x100+f)
D =0x560000*e+0x5600*f+0x7800*e+0x78*f
DD =D & 0xffff = 0x5678*f+0x7800*e
Zakljucak (analogno primeru iz proslog posta): e ne utice na donje dve cifre DD -> samo f utice na ...
Dalje pravis petlje za trazenje e i f, kao sto je vec vidjeno.

[Ovu poruku je menjao blaza dana 16.06.2004. u 16:39 GMT]

[ -=Cheda=- @ 16.06.2004. 01:26 ] @

Cekaj a zar se vracanjem na alternativna reshenja to reshenje ne svodi samo na komplikovaniji zapis onog prvog reshenja. Ako ga nije nashao vraca se... Oper najgori slucaj 2^32. Mozda bi na ovo reshenje mogla da se doda neka heuristika.

[ blaza @ 16.06.2004. 02:13 ] @

Moze da odmah dobije sva moguca resenja za d (prva petlja se vrti od 0..0xffff) - naci ce x resenja, x << 0x10000. Tada za svako od tih resenja nek provrti drugu petlju, da bi nasao resenja za c.
Znaci prva petlja ce imati 0x10000 ciklusa, a druga najvise x*0x10000 ciklusa.
Posto je x << 0x10000, ukupan broj ciklusa je << 0x100000000.
Sad, moze ubrzati izracunavanje zamenom svake od petlji sa dve petlje nizeg nivoa.
Recimo, ako petlju za izracunavanje d zameni sa dve petlje od 0..0xff (na nacin opisan u mom prethodnom postu), resenje se dalje pojednostavljuje, tj. izracunavanje se ubrzava. Sa ovim trendom se moze nastaviti i dalje, sve dok petlja nizeg reda ima broj ciklusa > 1.

Nekako mi ovaj thread vise odgovara forumu Art of Programming.

[ blaza @ 16.06.2004. 18:30 ] @

Evo, ovaj kod vrlo brzo (za par ms) nalazi sva moguca resenja:

Code:
#include <iostream>
using namespace std;

const unsigned int A = 0x12345678;
const unsigned int B = 0x11111111;

unsigned int func(unsigned int a){
    return a * A + B;
}

void find_all_solutions(unsigned int b){
    b -= B;
    for(unsigned int c = 0; c <= 0xffff; c++)
        if(!(((c * A) ^ b) & 0xffff)){
            unsigned int d = b - c * A;
            for(unsigned int e = 0; e <= 0xffff; e++)
                if(((e * A) << 16) == d)
                    cout << (e * 0x10000 + c) << "\n";
        }
}

int main(int argc, char** argv){
    for( ; ; ){
    cout << "\nUnesi broj:";
        unsigned int a, b;
        cin >> a;
        b = func(a);
        cout << "\nfunc(" << a <<") = " << b << "\n";
        cout << "Sva resenja inv_func(" << b << ") su:\n";
        find_all_solutions(b);
    }
    return 0;
}

[ DarkMan @ 16.06.2004. 21:53 ] @

Svaka ti cast! Stvarno radi.
Videcu sta mogu da uradim sa tim.
Hvala!

[ -=Cheda=- @ 16.06.2004. 23:57 ] @

Svaka cast. To je to!!!

[ blaza @ 17.06.2004. 18:55 ] @

Resenje iz prethodnog posta baziralo se na zameni jedne petlje sa 2^32 ciklusa sa dve petlje sa po 2^16 ciklusa, pri cemu se druga petlja uslovno izvrsava.
Brzina izracunavanja se dalje moze povecati (sto je bitno ako je potrebno odraditi veliki broj proracuna za sto krace vreme) tako sto se svaka petlja sa 2^16 ciklusa, kao sto sam ranije napisao, zameni sa dve nove petlje sa po 2^8 ciklusa na nacin prikazan u primeru:

Code:
void find_all_solutions_2(unsigned int b){
    b -= B;
    for(unsigned int c1 = 0; c1 <= 0xff; c1++)
        if(!(((c1 * A) ^ b) & 0xff)){
            unsigned int d1 = (b - c1 * A);
            for(unsigned int e1 = 0; e1 <= 0xff; e1++)
                if (!((((e1 * A) << 8) ^ d1) & 0xffff)){
                    unsigned int c = e1 * 0x100 + c1;
                    unsigned int d = b - c * A;
                    const unsigned int A2 = A << 16;
                    for(unsigned int c2 = 0; c2 <= 0xff; c2++)
                        if(!(((c2 * A2) ^ d) & 0x00ff0000)){
                            unsigned int d2 = d - c2 * A2;
                            for(unsigned int e2 = 0; e2 <= 0xff; e2++)
                                if (!((((e2 * A2) << 8) ^ d2) & 0xffff0000)){
                                    unsigned int e = e2 * 0x100 + c2;
                                    cout << (e * 0x10000 + c) << "\n";
                                }
                        }
                }
        }
}

Samo ce prva petlja izvrteti svih 256 ciklusa, a ostale se uslovno izvrsavaju, tako da se vreme izracunavanja drasticno skracuje.

Evo rezultata brzinskog testa (naredbe za prikaz rezultata (cout << ... ) sam izbacio, da bi dobio realnije rezultate):
-Losije resenje se izvrti milion puta za 104 sek.
-Bolje resenje se izvrti milion puta za 9 sek.

Ako zelimo jos brze izracunavanje mozemo zameniti svaku petlju sa 2^8 ciklusa sa po dve petlje sa 2^4 ciklusa, itd...