Przekształcenie pseudolosowe

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
v11
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 21 gru 2010, o 09:07
Płeć: Mężczyzna
Lokalizacja: Internet

Przekształcenie pseudolosowe

Post autor: v11 »

Dane jest przekształcenie
R(s) = (s*13477pięć813 + 1) mod 4294967296
Początkowa wartość s = s0 jest nieznana. W toku 8 przekształceń (s staje się R(s)) uzyskujemy informację o tym, w której z 26 (możliwie) równych części, na jakie dzieli się skala (tj. 4294967296), znajduje się s po każdym przekształceniu.

(Ściślej rzecz biorąc każda informacja(liczba), którą mamy, jest wyznaczana na takiej zasadzie, że s mnożymy przez 26 i następnie dzielimy z odrzuceniem reszty przez N=4294967296.)

Na podstawie tej informacji należy określić, czy ciąg tych 8 liczb (0-25, lub jak kto woli A-Z) jest możliwy do uzyskania z jakiejś wartości początkowej s0 z zakresu 0 - N-1. Większość nie jest.

Na pewno zadanie da się rozwiązać na zasadzie, że zapisujemy gdzieś te (najwyżej) N możliwych ciągów i później porównujemy, czy się z nimi zgadza. Ale jest to bardzo nieefektywne. Rozwiązanie może być numeryczne i iteracyjne, poza tym może opierać się na jakichś zapamiętanych danych, ale nie aż tak. Czy jest w ogóle szansa uniknąć takiej ilości iteracji/pamiętanych danych?

Również rozwiązania częściowe, tzn. wykrywające wiele, ale nie wszystkie nieprawidłowe ciągi, są dla mnie wartościowe.



Obawiam się poważnie, że ze względu na chaotyczność nic tu się nie wymyśli, ale może chociaż jakieś optymalizacje algorytmu oceniającego... Już żeby to w milionach szło (pamiętane dane do pomocy), a nie w miliardach, to byłby sukces. Co do iteracji algorytmu to najwyżej setki tysięcy wchodzą w grę.
ODPOWIEDZ