Trait PrimitiveRootPrime

pub trait PrimitiveRootPrime {
    type Output;

    // Required method
    fn primitive_root_prime(&self) -> Self::Output;
}

A trait for finding a primitive root modulo a prime.

Required Associated Types

type Output

Required Methods

fn primitive_root_prime(&self) -> Self::Output

Implementations on Foreign Types

impl PrimitiveRootPrime for u8

fn primitive_root_prime(&self) -> u8

Given a prime number, computes a primitive root modulo that number. In other words, given a prime $p$, finds a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$.

If the input is not prime, this function’s behavior is unspecified. Since primality checking can be expensive, the input is not tested for primality.

Currently the smallest primitive root is returned, but there is no guarantee that this will be the case in the future.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0, and possibly panics if self is not prime.

Examples

use malachite_base::num::factorization::traits::PrimitiveRootPrime;

assert_eq!(5u32.primitive_root_prime(), 2);
assert_eq!(191u32.primitive_root_prime(), 19);
assert_eq!(4294967291u32.primitive_root_prime(), 2);

type Output = u8

impl PrimitiveRootPrime for u16

fn primitive_root_prime(&self) -> u16

Given a prime number, computes a primitive root modulo that number. In other words, given a prime $p$, finds a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$.

If the input is not prime, this function’s behavior is unspecified. Since primality checking can be expensive, the input is not tested for primality.

Currently the smallest primitive root is returned, but there is no guarantee that this will be the case in the future.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0, and possibly panics if self is not prime.

Examples

use malachite_base::num::factorization::traits::PrimitiveRootPrime;

assert_eq!(5u32.primitive_root_prime(), 2);
assert_eq!(191u32.primitive_root_prime(), 19);
assert_eq!(4294967291u32.primitive_root_prime(), 2);

type Output = u16

impl PrimitiveRootPrime for u32

fn primitive_root_prime(&self) -> u32

Given a prime number, computes a primitive root modulo that number. In other words, given a prime $p$, finds a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$.

If the input is not prime, this function’s behavior is unspecified. Since primality checking can be expensive, the input is not tested for primality.

Currently the smallest primitive root is returned, but there is no guarantee that this will be the case in the future.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0, and possibly panics if self is not prime.

Examples

use malachite_base::num::factorization::traits::PrimitiveRootPrime;

assert_eq!(5u32.primitive_root_prime(), 2);
assert_eq!(191u32.primitive_root_prime(), 19);
assert_eq!(4294967291u32.primitive_root_prime(), 2);

type Output = u32

impl PrimitiveRootPrime for u64

fn primitive_root_prime(&self) -> u64

Given a prime number, computes a primitive root modulo that number. In other words, given a prime $p$, finds a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$.

If the input is not prime, this function’s behavior is unspecified. Since primality checking can be expensive, the input is not tested for primality.

Currently the smallest primitive root is returned, but there is no guarantee that this will be the case in the future.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0, and possibly panics if self is not prime.

Examples

use malachite_base::num::factorization::traits::PrimitiveRootPrime;

assert_eq!(5u32.primitive_root_prime(), 2);
assert_eq!(191u32.primitive_root_prime(), 19);
assert_eq!(4294967291u32.primitive_root_prime(), 2);

type Output = u64

impl PrimitiveRootPrime for usize

fn primitive_root_prime(&self) -> usize

Given a prime number, computes a primitive root modulo that number. In other words, given a prime $p$, finds a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$.

If the input is not prime, this function’s behavior is unspecified. Since primality checking can be expensive, the input is not tested for primality.

Currently the smallest primitive root is returned, but there is no guarantee that this will be the case in the future.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0, and possibly panics if self is not prime.

Examples

use malachite_base::num::factorization::traits::PrimitiveRootPrime;

assert_eq!(5u32.primitive_root_prime(), 2);
assert_eq!(191u32.primitive_root_prime(), 19);
assert_eq!(4294967291u32.primitive_root_prime(), 2);

type Output = usize

Implementors