prime Namespace Reference

The namespace for prime number related operations. More...

Functions
bool	is (const uint64_t &num)
	Checks if any given number is prime.
template<typename T = uint64_t>
void	next (T &num)
	Find the next prime greater than the provided number.
uint64_t	raise (uint64_t value, uint64_t exp, const uint64_t &mod)
	A O(logn) raise operation that works within modulus to prevent overflow.
std::pair< uint64_t, uint64_t >	generate ()
	Generates a prime number.

Detailed Description

The namespace for prime number related operations.

Remarks

Everything is inlined; this will increase binary size, but hopefully (If the compiler wants to cooperate) increase speed.

Warning

values are stored in regular C++ datatypes; best practice would be to use secure classes, such as a container that allocates on the heap, and then overwrites the values randomly upon its destruction.

Function Documentation

generate()

std::pair< uint64_t, uint64_t > prime::generate ( )

inline

Generates a prime number.

Returns

A prime number p, and the smaller prime q.

Remarks

This function will use std::rand() to find a starting value, and then find the nearest prime larger than it. There are some cavets to this approach for the sake of simplicity and readibility. Firstly, primes are confined from 3 - 2**64 Secondly, std::rand() is not considered a cryptographically secure PRNG. However, this implemention makes it easier to understand, and allows us to work within the confines of standard integer types.

See 2.2 of the Diffie-Hellman Reference.

is()

bool prime::is ( const uint64_t & num )

inline

Checks if any given number is prime.

Parameters

num	The number.

Returns

True if the number is prime, False if it isn't.

next()

template<typename T = uint64_t>

void prime::next ( T & num )

inline

Find the next prime greater than the provided number.

Template Parameters

T	The type of number. Generating a prime uses half-width.

Parameters

num	The number (Does not need to be prime itself)

Remarks

This function is intended to overflow, since the datatype is unsigned. Since we are always dealing with odd numbers, an overflow will bring us to 1.

Warning

This function is done in-place. It modifies the number you pass to it.

raise()

uint64_t prime::raise ( uint64_t value, uint64_t exp, const uint64_t & mod )

inline

A O(logn) raise operation that works within modulus to prevent overflow.

Parameters

value	The value to raise.
exp	The exponent to raise the value by.
mod	The mod space

Returns

the result.

Note

From https://www.geeksforgeeks.org/primitive-root-of-a-prime-number-n-modulo-n/

Remarks

Because raising values is almost assured to overflow when using such large numbers. We need to compute it piecemeal, applying the modulus on each self multiplication such that it remains bounded with our datatype.