[R] Modula Generators

[Hans W Borchers]

Sam K <upperhalfplane <at> yahoo.co.uk> writes:
> 
> Hi all,
> 
> Is there function on R for calculating Modula generators? For example for 
> primes above 100, e.g 157, i want
> to know which number generates the group under multiplication mod 157. i.e  i 
> want to find an element whose
> order is 156. The problem I occur is that modular arithmetic becomes 
> inaccurate when dealing with large numbers.

In other words, you are looking for a 'primitive root' in the field F_p
of prime p. By the way, there are phi(p) of them, where phi is Euler's 
function.

There is no known efficient algorithm for this, except the prime 
factorization of p-1 is given. And this algorithm is probabilistic,
i.e., in some cases it may not terminate.

In case your primes do not get too big, say between 100 and 1000, an
exhaustive search may be possible, somewhat simplified by the Euler
criterion.

Or you locate and read in some tables listing primitive roots. You can
find more information in Wikipedia or MathWorld.

For exact modular arithmetic you may turn to the 'gmp' R package.

Regards
Hans Werner

> Thanks for any help given.
> 
> Sam
>