China 
Africa 
Explore chapters and articles related to this topic
Cryptography
Published in R. Balakrishnan, Sriraman Sridharan, Discrete Mathematics, 2019
R. Balakrishnan, Sriraman Sridharan
The Miller-Rabin Algorithm is a randomized algorithmRandomized algorithm for primality testing. A randomized algorithm is an algorithm which during the execution of the algorithm makes at least one random choice. It is in contrast with the deterministic algorithms in which every step has a unique subsequent step. A randomized polynomial time algorithm is a randomized algorithm which runs in polynomial time (RP for short). We now give the precise definition of a randomized algorithm. RP algorithmConsider a decision problem, that is, a problem whose answer is either “yes” or “no.” (For example, given an integer n ≥ 2, we would like to know if n is prime or composite). A randomized polynomial time algorithm is a randomized algorithm which runs in polynomial time in the worst case such that for any input I, the probability that the answer is “yes” for the input I is ≥ 1/2 and the probability that the answer is “no” is 0. That is, the algorithm errs in case of output “yes” and makes no error in case of ouput “no.”
Mathematical Background
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
The algorithms studied so far in this section have been deterministic; such algorithms follow the same execution path (sequence of operations) each time they execute with the same input. By contrast, a randomized algorithm makes random decisions at certain points in the execution; hence its execution paths may differ each time it is invoked with the same input. The random decisions are based upon the outcome of a random number generator. Remarkably, there are many problems for which randomized algorithms are known that are more efficient, both in terms of time and space, than the best known deterministic algorithms.
Event Log Privacy Based on Differential Petri Nets
Published in Applied Artificial Intelligence, 2023
Daoyu Kan, Xianwen Fang, Ziyou Gong
According to Definition 3, dataset (1) and dataset (2) and dataset (1) and dataset (3) in Figure 1 all constitute neighboring datasets, since they all differ from each other by only one piece of data. is a randomized algorithm. The datasets and are neighboring datasets. is an arbitrary subset of all possible outputs of the randomized algorithm . If there is . Then the algorithm is said to be -differential privacy.
Distributed maximal independent set computation driven by finite-state dynamics
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos-Wilson
The MIS has a trivial solution in the classical sequential setting, where a greedy algorithm sequentially picks an arbitrary vertex, includes it in the maximal independent set, and removes that vertex together with all its neighbors. In the 80's, Karp and Wigderson [1] mentioned that the MIS is an interesting problem in non-centralized computation. Soon after that, Luby [2] and Alon, Babai, and Itai [3] presented simple distributed randomized algorithms solving MIS in time. Since then, this problem has been studied extensively in the distributed setting. In the LOCAL model, the fastest deterministic MIS algorithms for general graphs run in [4], and time [5]. Ghaffari [6] also obtained a time randomized algorithm on general graphs, and a time randomized algorithm for graphs of arboricity a. With respect to lower bounds, Linial [7] proved that computing an MIS on an n-cycle requires time . Moreover, Kuhn et al. [8] showed a lower-bound on the round complexity on general graphs.
Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays
Published in Optimization Methods and Software, 2022
Puya Latafat, Panagiotis Patrinos
In the second numerical experiment, depicted in Figure 2 (right), we considered a larger problem with m = 50 and the maximum delay B = 10. We simulated the algorithms with nominal stepsizes. It is observed that Algorithm 2 and the dual decomposition approach struggle to reach a high precision. Interestingly, the randomized algorithm Algorithm 3 is able to overcome this. Moreover, even with larger delays the algorithms are convergent with nominal stepsizes while the theoretical stepsize may become too small resulting in slow convergence in practice. It would be interesting to study if the stepsize conditions presented in this paper can be relaxed for the special case when are indicator functions and are quadratic.