GNRATR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practise

Contest

Author, Tester, Editorialist: Vaibhav Gupta

PROBLEM

Find the kth generator greater than a given number a of a multiplicative group Zp.

QUICK EXPLANATION

A set of generators (g1,…,gn) is a set of group elements such that possibly repeated application of the generators on themselves and each other is capable of producing all the elements in the group. Cyclic groups can be generated as powers of a single generator.

EXPLANATION

Algorithm for finding the generator of a cyclic group.

INPUT: a cyclic group G of order n, and the prime factorization n = p1e1p2e2 · · · pkek.

OUTPUT: a generator α of G.

  1. Choose a random element α in G.

  2. For i from 1 to k do the following:

2.1 Compute b ← αn/pi .

2.2 If b = 1 then go to step 1.

  1. Return(α).

ACCEPTED SOLUTION:

rpwt’s Solution