Explore chapters and articles related to this topic
Number-Theoretic Reference Problems
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
3.55 Note (solving the DLP in a cyclic group G of order n is in essence computing an isomorphism between G and ℤn) Even though any two cyclic groups of the same order are isomorphic (that is, they have the same structure although the elements may be written in different representations), an efficient algorithm for computing logarithms in one group does not necessarily imply an efficient algorithm for the other group. To see this, consider that every cyclic group of order n is isomorphic to the additive cyclic group ℤn, i.e., the set of integers {0, 1, 2, …, n − 1} where the group operation is addition modulo n. Moreover, the discrete logarithm problem in the latter group, namely, the problem of finding an integer x such that ax ≡ b (mod n) given a, b ∈ ℤn, is easy as shown in the following. First note that there does not exist a solution x if d = gcd(a, n) does not divide b (Fact 2.119). Otherwise, if d divides b, the extended Euclidean algorithm (Algorithm 2.107) can be used to find integers s and t such that as + nt = d. Multiplying both sides of this equation by the integer b/d gives a(sb/d) + n(tb/d) = b. Reducing this equation modulo n yields a(sb/d) ≡ b (mod n) and hence x = (sb/d) mod n is the desired (and easily obtainable) solution.
Mathematical Foundations
Published in Chintan Patel, Nishant Doshi, Internet of Things Security, 2018
Cyclic Group A group is cyclic if it contains a generator ξ. Generator is the element of group through which we can generate remaining elements of the group [Stallings (2010)]. Example: if a = ξ ∈ . Then for every element bi ∈ , we can represent it as a aj = bi. Example: Consider the group 11 = {1, 2, 3, 4, 5, 6, 7,, 8, 9, 10} defined over operation modulo 11. Then, for every i ≤ 10, operation 2imod 11 will return (2, 4, 8, 5, 10, 9, 7, 3, 6, 1), which is a set of all elements defined in group. So we can say 2 is the generator of group 11 defined over operation modulo 11. A group that contains only one generator is called a cyclic group. Every cyclic group is a commutative group, but it is not necessary that every commutative group is cyclic. Cyclic groups can be finite or infinite. Elements with the maximum orders are called a primitive element or generator.
Number Theory and Cryptographic Hardness Assumptions
Published in Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography, 2020
The identity element of any group G is the only element of order 1, and generates the group 〈1〉 = {1}. At the other extreme, if there is an element g∈G that has order m (where m is the order of G), then 〈g〉=G. In this case, we call G a cyclic group and say that g is a generator of G. (A cyclic group may have multiple generators, and so we cannot speak of the generator.) If g is a generator of G then, by definition, every element h∈G is equal to gx for some x ∈ {0,…, m − 1}, a point we will return to in the next section.
On the g-component connectivity of hypercube-like networks
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Shanshan Yin, Liqiong Xu, Zhecheng Yu
Throughout this paper, all groups are finite. If a subset H of a group G is itself a group under the operation of G, we say that H is a subgroup of G and denoted by . For a subset S of a group G, the intersection of all subgroups of G containing S is called the subgroup generated byS, denoted by . For an element g in a group G, the order of g is the smallest positive integer n satisfying . Let n be a positive integer. Throughout this paper, represents the cyclic group of order n.