Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Inverzna funkcija

[es] :: C/C++ programiranje :: Inverzna funkcija

[ Pregleda: 4033 | Odgovora: 14 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

DarkMan
Darko Matesic

Član broj: 20445
Poruke: 572
217.26.66.*

Jabber: DarkMan


Profil

icon Inverzna funkcija14.06.2004. u 14:43 - pre 240 meseci
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.
 
Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.client.comcast.net



+1001 Profil

icon Re: Inverzna funkcija14.06.2004. u 16:10 - pre 240 meseci
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.
 
Odgovor na temu

DarkMan
Darko Matesic

Član broj: 20445
Poruke: 572
217.26.66.*

Jabber: DarkMan


Profil

icon Re: Inverzna funkcija14.06.2004. u 22:45 - pre 240 meseci
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).
 
Odgovor na temu

-=Cheda=-
Nenad Cetic
DSP Firmware Designer, RT-SP
Veternik

Član broj: 21827
Poruke: 26
*.ftn.ns.ac.yu

Jabber: -=Cheda=-
ICQ: 150608261


+1 Profil

icon Re: Inverzna funkcija15.06.2004. u 01:00 - pre 240 meseci
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) :(
Na prvi pogled izgleda kao obicna koza ali je u stvari shporet na ringishpilu.
Sluzi za zbunjivanje protivnika.
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Inverzna funkcija15.06.2004. u 05:14 - pre 240 meseci
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)?
O_o
 
Odgovor na temu

miličić.marko
Miličić Marko
Novi Sad

Član broj: 12598
Poruke: 346
*.yu
Via: [es] mailing liste

Sajt: milicicmarko.blogspot.com


+1 Profil

icon Re: Inverzna funkcija15.06.2004. u 15:23 - pre 240 meseci
>
>
Skripte iz oblasti računarstva na Srpskom jeziku
kontakt email milicic [tacka] marko [na] gmail [tacka] com

Numizmatička kolekcija:
http://numismaticscollection.blogspot.com/
 
Odgovor na temu

DarkMan
Darko Matesic

Član broj: 20445
Poruke: 572
*.verat.net

Jabber: DarkMan


Profil

icon Re: Inverzna funkcija15.06.2004. u 21:44 - pre 240 meseci
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.
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Inverzna funkcija15.06.2004. u 22:47 - pre 240 meseci
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]
O_o
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Inverzna funkcija15.06.2004. u 22:59 - pre 240 meseci
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]
O_o
 
Odgovor na temu

-=Cheda=-
Nenad Cetic
DSP Firmware Designer, RT-SP
Veternik

Član broj: 21827
Poruke: 26
*.ftn.ns.ac.yu

Jabber: -=Cheda=-
ICQ: 150608261


+1 Profil

icon Re: Inverzna funkcija16.06.2004. u 01:26 - pre 240 meseci
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.
Na prvi pogled izgleda kao obicna koza ali je u stvari shporet na ringishpilu.
Sluzi za zbunjivanje protivnika.
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Inverzna funkcija16.06.2004. u 02:13 - pre 240 meseci
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.
O_o
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Inverzna funkcija16.06.2004. u 18:30 - pre 240 meseci
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;
}

O_o
 
Odgovor na temu

DarkMan
Darko Matesic

Član broj: 20445
Poruke: 572
*.verat.net

Jabber: DarkMan


Profil

icon Re: Inverzna funkcija16.06.2004. u 21:53 - pre 240 meseci
Svaka ti cast! Stvarno radi.
Videcu sta mogu da uradim sa tim.
Hvala!
 
Odgovor na temu

-=Cheda=-
Nenad Cetic
DSP Firmware Designer, RT-SP
Veternik

Član broj: 21827
Poruke: 26
*.ftn.ns.ac.yu

Jabber: -=Cheda=-
ICQ: 150608261


+1 Profil

icon Re: Inverzna funkcija16.06.2004. u 23:57 - pre 240 meseci
Svaka cast. To je to!!!
Na prvi pogled izgleda kao obicna koza ali je u stvari shporet na ringishpilu.
Sluzi za zbunjivanje protivnika.
 
Odgovor na temu

blaza
n/a

Član broj: 961
Poruke: 743
*.vdial.verat.net



+3 Profil

icon Re: Inverzna funkcija17.06.2004. u 18:55 - pre 240 meseci
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...

O_o
 
Odgovor na temu

[es] :: C/C++ programiranje :: Inverzna funkcija

[ Pregleda: 4033 | Odgovora: 14 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.