szybkie algorytmy łamania szyfrów
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

szybkie algorytmy łamania szyfrów

AutorWiadomość
Temat założony przez niniejszego użytkownika
szybkie algorytmy łamania szyfrów
» 2019-11-12 18:22:16
Witam, bardzo proszę administrację o przeczytanie przed usunięciem :)
Rozwiązuję zadania informatyczne w internecie i natknąłem się na zadanie, które sprowadza się do znalezienia ilości poprawnych kluczy do zamka szyfrowego.
Do programu mam podaną ilość "pokręteł", liczb na jednym pokrętle, oraz numery pokręteł, które muszą mieć inną wartość, aby zamek się otworzył np.:

3 - ile pokręteł
3 - ile liczb na jednym pokrętle

1 2
2 3 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył
1 3
oznacza to następujący zamek:
1   1   1
2   2   2
3   3   3
Poprawne szyfry to:
123, 132, 213, 231, 312, 321, a odpowiedź to 6
Rozwiązuje to na razie metodą brut force, sprawdzając czy każdy szyfr pasuje, jednak jest to zbyt wolne, ma ktoś pomysł na szybszy algorytm / algorytm szukający liczby pasujących kodów zamiast wszystkich rozwiązań?
P-175547
» 2019-11-13 08:28:51
szukana przez Ciebie liczb jest obliczalna
znajdziesz to w  dziale Matematyki zwanym Kombinatoryką
Twoje pytanie dotyczy "Wariacji z powtórzeniami"

przeczytaj https://pl.wikipedia.org/wiki​/Wariacja_z_powt%C3%B3rzeniami
lub podobną publikację na ten temat

i zastosuj odpowiednio ten wzór

P-175553
Temat założony przez niniejszego użytkownika
» 2019-11-13 15:17:36
Wzór na ilość wszystkich kombinacji jest dość prosty i nie potrzeba mi wikipedii, problem jest w tym, że muszę odjąć kody, które się powtarzają
Np przy wejściu
4
4
1 2 - 1 i 2 liczba muszą być inne
1 3 - 1 i 3 liczba muszą być inne
2 3 - 2 i 3 liczba muszą być inne
Będzie 256 wszystkich kombinacji odjąć:
1. 64 zaczynających się na 11/22/33/44
2. 16 postaci1x1/2x2/3x3/4x4
3. 16 postaci x11/x22/x33/x44
Kod 1111 jest odejmowany w każdym punkcie, a powinien być liczony tylko raz
P-175554
» 2019-11-14 07:43:07
mylnie używasz nazwy "kombinacja", gdyż w matematyce kombinacja to podzbiór liczb - czyli coś nieuporządkowanego
Ty chcesz mieć ciągi uporządkowane, a w tym wypadku mowa jest o "wariancjach"
i mamy dwa przypadki bez powtórzeń i z powtórzeniami

na oba są wzory i jestem przekonany, że uwzględniają opisywane przez Ciebie przypadki.

Twoim problemem jest chyba to, że musisz wykorzystać równocześnie oba.
ale to proste, gdyż w tym przypadku
dzielisz pokrętła na dwie grupy (z powtórzeniami, bez powtórzeń)
i dla każdej z tych grup korzystasz z odpowiedniego wzoru

wynikiem jest iloczyn wyników

Pozdrawiam







P-175567
Temat założony przez niniejszego użytkownika
» 2019-11-14 15:30:09
Przeanalizowałem obie wariacje i nie widzę ich zastosowania, ja losuje po jednej cyfrze z n podzbiorów, w kazdym jest m liczb.
Wzory obu wariacji dla losowania 1 z m liczb skracają się do m = m, co jest dobrym, ale bezużytecznym wynikiem.

Zauważcie, że gdy mamy przykładowy zamek, używając oznaczeń z początku wiadomości
n = 3; m = 3; 1 i 2 muszą mieć inne wartości
Wzór na wszystkie kombinacje to:
3 * 3 * 3,
drugie pokretlo musi miec inna wartosc niz 1 wiec wybieramy tam w zasadzie jedna z 2, a nie 3 liczb - wzor wyglada nastepujaco:
3 * (3 - 1) * 3
Niestety przy zamku:
n = 3; m = 3; 1 i 3, 2 i 3 maja inne wartosci
(3 - 1) * (3 - 1) * 3 jest poprawny
(1 pokretlo ma inna wartosc niz 3; 2 pokretlo ma inna wartosc niz 3)
3 * 3 * (3 - 1 - 1) jest zly
(3 pokretlo musi miec inna wartosc niz 1 i  2 wiec wybieramy z 1, a nie 3 liczb, niestety nie uwzglednia kombinacji 11x, 22x, 33x)
Moje pytanie jak to zaprogramować, aby komputer odejmował od poprawnych pokręteł?
P-175572
» 2019-11-15 08:58:42
Przeczytałem Twoje słowa i przykro mi,
bo podałem Ci prawidłową ścieżkę do znalezienia rozwiązania.

Badane ilości układów pokręteł podpada pod definicję "wariancji" (matematyka - kombinatoryka).

musisz to tylko zobaczyć i zastosować.

Pozdrawiam
P-175582
Temat założony przez niniejszego użytkownika
» 2019-11-16 17:12:45
Myślę nad tym od dwóch dni i nic...

Odchodząc już od tego zamka mam 3-cyfrową liczbę z cyfr 1, 2, 3, pierwsza cyfra musi być inna od pozostałych.
Wynik to 12
między 1 i 2, oraz 1 i 3 cyfrą są wariacje bez powtórzeń - 6 wariacji
między 2 i 3 cyfrą jest wariacja z powtórzeniami - 9 wariacji
wariacja bez powtórzeń całej liczby - 6 wariacji
wariacja z powtórzeniami całej liczby - 27 wariacji

Jedyne co mi przychodzi do głowy to 6 + 6, czyli zależności między 1 i 2, oraz 1 i 3 cyfrą, ale to jest przypadkowa zbieżność...
P-175588
» 2019-11-18 13:22:54
podchodzisz do tego w zły sposób gdyż aby to rozwiązać
musisz tylko zrozumieć czym jest
* "wariancja bez powtórzeń" - ciąg liczb bez możliwych powtórzeń (a1,...,aN)
* "wariancja z powtórzeniami" - ciąg liczb z możliwymi powtórzeniami (b1,...,bN)

z treści zadania wynika, że możemy mieć do czynienia z sytuacją mieszaną
tzn.  szukamy ciągu, w którym na pewnych miejscach nie mogą wystąpić powtórzenia
ale na pozostałych mogą  czyli np. ciągu (a1,b1,b2,a2,b3,a3,b4),  gdzie :
A = (a1,a2, a3) "wariancja bez powtórzeń"
B = (b1,b2,b3,b4) "wariancja z powtórzeniami"
o ilości możliwych ciągów decydują wzory na odpowiednią wariancję
ostatecznym wynikiem jest iloczyn ilość(A)*ilość(B) 

to które wyrazu ciągu należą do A, a które B musisz rozstrzygnąć
na podstawie warunków początkowych

np. z twojego przykładu "2 3 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył"
 

co można zaprezentować na przykładzie
mamy
5 - ile pokręteł
7 - ile liczb na jednym pokrętle

1 3
3 4 - na których pokrętłach muszą być inne liczby, aby zamek się otworzył
1 4

szukamy ciągu 5 cyfrowego (a1,b1,a2,a3,b2)
(a1,a2,a3)  = 7*6*5  "wariancja bez powtórzeń"
(b1,b2)     = 7*7    "wariancja z powtórzeniami"

może być jeszcze bardziej skomplikowany przypadek, gdzie nie ma wszystkich warunków poczatkowych na "wariancja bez powtórzeń"

np. mielibyśmy tylko 2 warunki
1 3  - na których pokrętłach muszą być inne liczby, aby zamek się otworzył
1 4

co powodowałoby że szukalibyśmy rozwiązania dla 5 cyfrowego (a1,b1,c1,c2,b2)
gdzie
(a1)  = 7  "wariancja bez powtórzeń"
(b1,b2)     = 7*7    "wariancja z powtórzeniami"
(c1,c2)     = 6*6    "wariancja z powtórzeniami" (ale warunki początkowe ograniczają ilość liczb do wyboru)

no i przykład można dalej komplikować gdzie mielibyśmy np. po kilka "wariancja bez powtórzeń" i kilka "wariancji z powtórzeniami"

ale jak zaprezentowałem Ci rozwiązanie opiera się o znaną z matematyki teorię o "wariancjach"

Powodzenia




P-175600
« 1 » 2
 Strona 1 z 2Następna strona