[MaciejSkur]

W artykule „Practical solving of discrete logarithm problem over prime fields using quantum annealing” opublikowanym w materiałach pokonferencyjnych konferencji International Conference on Computational Science 2022 mjr dr inż. Michał Wroński z Wydziału Cybernetyki Wojskowej Akademii Technicznej przedstawił pierwsze praktyczne realizacje obliczania logarytmu dyskretnego w ciele skończonym z wykorzystaniem metod kwantowych.



Jak wyjaśnia mjr Wroński, problem logarytmu dyskretnego w ciele skończonym polega na znalezieniu takiego najmniejszego całkowitego dodatniego y, dla którego i dla elementów g oraz h z tego ciała zachodzi równość g do potęgi y jest równe h. Aby to lepiej wyjaśnić, naukowiec posługuje się przykładem.



„Załóżmy, że operujemy w ciele 11-elementowym. Ważne, aby liczba elementów była liczbą pierwszą, a 11 taką liczbą właśnie jest. Operowanie w ciele 11-elementowym oznacza, że działania wykonujemy na resztach z dzielenia przez 11. Teraz chcemy wyznaczyć najmniejsze całkowite dodatnie y, dla którego w naszym ciele 4 do potęgi y jest równe 9” – tłumaczy autor artykułu. Chodzi więc o znalezienie takiego y, dla którego liczba 4 podniesiona do potęgi y przy dzieleniu przez 11 da resztę 9. Rozwiązaniem jest w tym przypadku y równe 8. „Każdy może sprawdzić, że 4 do potęgi 8 równa się 65 536, a liczba ta przy dzieleniu przez 11 daje właśnie resztę równą 9” – dodaje mjr Wroński, ale zastrzega, że dla dostatecznie dużych ciał problem staje się bardzo trudny.



Komputery realizujące wyżarzanie kwantowe posiadają obecnie znacznie więcej zasobów aniżeli komputery kwantowe ogólnego przeznaczenia. Dlatego naturalnym pomysłem była próba wykorzystania wyżarzania kwantowego do rozwiązania problemu logarytmu dyskretnego w ciałach skończonych. „Najpierw trzeba było pokonać pewne trudności. Wiedzieliśmy, w jaki sposób, wykorzystując wyżarzanie kwantowe, rozwiązywać układy równań wielomianowych w ciałach skończonych. W przypadku logarytmu dyskretnego w ciele skończonym cała trudność polegała na przekształceniu funkcji wykładniczej do pewnej funkcji wielomianowej, a następnie do pewnego kwadratowego problemu optymalizacyjnego, który posiada stosunkowo mało zmiennych. Trzeba pamiętać, że poszukiwany y znajduje się właśnie w wykładniku. Wykorzystując wyżarzanie kwantowe, udało się w ten sposób rozwiązać problem logarytmu dyskretnego w 6-bitowym ciele skończonym” – tłumaczy naukowiec.



Jak podkreśla mjr Wroński, pomimo że rozmiar rozwiązanego problemu nie wydaje się zbyt duży, osiągnięty wynik jest istotny z teoretycznego punktu widzenia i może prowadzić do bardziej efektywnych metod kwantowego rozwiązywania problemu logarytmu dyskretnego, zanim to będzie możliwe z wykorzystaniem algorytmu Shora.

#matematyka
#nauka
#ciekawostki
#informatyka

[leoha]

Ważne, aby liczba elementów była liczbą pierwszą

@MaciejSkur: istnieja ciala skonczone, ktore maja liczbe elementow nie bedacych liczba pierwsza ale jej potega.

[MaciejSkur]

@leoha: no tak