Wyniki wyszukiwania - BazTech

1

Optimal Strategies for Computation of Degree degree ℓⁿ Isogenies for SIDH

Wroński Michał, Chojnacki Andrzej

International Journal of Electronics and Telecommunications

|

2020

|

Vol. 66, No. 3

465--472

EN

This article presents methods and algorithms for the computation of isogenies of degree ℓⁿ. Some of these methods are obtained using recurrence equations and generating functions. A standard multiplication based algorithm for computation of isogeny of degree ℓⁿ has time complexity equal to O(n²M (n log n)), where M (N) denotes the cost of integers of size N multiplication. The memory complexity of this algorithm is equal to O (n log (n log (n))). In this article are presented algorithms for: - determination of optimal strategy for computation of degree ℓⁿ isogeny, - determination of cost of optimal strategy of computation of ℓⁿ isogeny using solutions of recurrence equations, - determination of cost of optimal strategy of computation of ℓⁿ isogeny using recurrence equations, where optimality in this context means that, for the given parameters, no other strategy exists that requires fewer operations for computation of isogeny. Also this article presents a method using generating functions for obtaining the solutions of sequences (սₘ) and (cₘ) where cₘ denotes the cost of computations of isogeny of degree ℓᵘᵐum for given costs p, q of ℓ-isogeny computation and ℓ-isogeny evaluation. These solutions are also used in the construction of the algorithms presented in this article.

2

Recent studies on the Dice Race Problem and its connections

Louchard G.

Mathematica Applicanda

|

2016

|

Vol. 44, No. 1

63--86

PL

W pracy rozważana jest znana i badana w literaturze następująca wersja gry w kości. Gracze na zmianę rzucają kością do gry sumując uzyskane wyniki tak długo aż wypadnie 1. W chwili wyrzucenia jedynki gracz, który ją wyrzucił traci swoją kumulację i jedna tura rozgrywki kończy się, a kość jest przekazywana do drugiego gracza. Po każdym rzucie gracz może zakończyć swoją kolejkę i odebrać uzyskaną wygraną. Zwycięża ten z graczy, który jako pierwszy osiągnie pewną ustaloną wygraną n ϵ N. Przedstawiono nowe wyniki dotyczące optymalnych strategii i wyznaczono prawdopodobieństwa wygranej w grze jedno- lub dwuosobowej. W przypadku jednego gracza nie konkuruje on z nikim, a jedynie chce zminimalizować oczekiwaną liczbę rzutów wybierając strategię prowadzącą do celu z wykorzystaniem wszystkich strategii dopuszczalnych.

EN

The following type of dice games has been mentioned and/or studied in the literature. Players take turns in rolling a fair die successively, each player accumulating his or her scores as long as the outcome 1 does not occur. If the result 1 turns up, the accumulated score is wiped out, and the turn ends, that is the player gives the die to the next player. At any stage after a roll, the player (she, say) can choose to end her turn and bank her accumulated score. The winner is the first player to reach some fixed target n ϵ N. We present some new results on optimal strategies and winning probability in a one or two players game. For just one player there is no competition of course, and in this case we suppose that the player simply wants to minimize her total expected number of tosses over all possible banking strategies.

3

Inteligentne algorytmy przeszukiwania : przeszukiwanie dużych przestrzeni

Bolc L., Cytowski J.

Elektronika : konstrukcje, technologie, zastosowania

|

2004

|

Vol. 45, nr 5

25-27

PL

Odnotowuje się ostatnio duży postęp w wyjaśnianiu struktury problemów przeszukiwania i konstruowania algorytmów przeszukiwania. Nowe osiągnięcia sztucznej inteligencji (szczególnie w dziedzinie automatycznego wnioskowania i reprezentacji wiedzy ) są wykorzystywane przy budowaniu nowych strategii przeszukiwania oraz teoretycznej analizie problemów i metod przeszukiwania. Celem naszej pracy jest zaprezentowanie klasycznych i nowych metod przeszukiwania. W tej części pragniemy przestawić strategie deterministyczne dla dużych przestrzeni przeszukiwania.

EN

Recently there has been significant progress in our understanding of the nature of search problems and the performance of search algorithms. Advances in artificial intelligence, (especially in automated reasoning and knowledge representation) are directly applied in constructing new search strategies as well as in the theoretical analysis of search problem and methods. Key features of our paper are presentation of classical and modern search methods. In this part we present deterministic strategies for large search spaces.