toychain/mmath_8h_source.html

#ifndef __MMATH_H

#define __MMATH_H


#include <stdbool.h>

#include <stddef.h>

#include "lib/types.h"


#define GOLDEN_RATIO 0.61803398875


int64 rand_int64(int64 low, int64 up);


bool is_prime_naive(int64 p);

bool is_prime_miller(int64 p, int k);

int64 random_prime_number(int low_size, int up_size, int k);


int64 modpow_naive(int64 a, int64 m, int64 n);

int64 modpow(int64 a, int64 m, int64 n);

int64 modpow_r(int64 a, int64 m, int64 n);


int64 extended_gcd(int64 s, int64 t, int64* u, int64* v);


uint32 jenkins_one_at_a_time_hash(const uint8* key, size_t len);


#endif

is_prime_miller
bool is_prime_miller(int64 p, int k)
checks if p is prime with (1/4)^k probability of a false positive. the larger the k,...
Definition: mmath.c:77

modpow_r
int64 modpow_r(int64 a, int64 m, int64 n)
calculates the exponent of a to the power of m modulo n in O(m log m). _r stands for recursive (a ^ m...
Definition: mmath.c:200

modpow
int64 modpow(int64 a, int64 m, int64 n)
calculates the exponent of a to the power of m modulo n in O(m log m). this is the main implementatio...
Definition: mmath.c:169

modpow_naive
int64 modpow_naive(int64 a, int64 m, int64 n)
calculates the exponent of a to the power of m modulo n in O(m^2). (a ^ m) % n = x
Definition: mmath.c:147

jenkins_one_at_a_time_hash
uint32 jenkins_one_at_a_time_hash(const uint8 *key, size_t len)
Jenkins one at a time hash function https://en.m.wikipedia.org/wiki/Jenkins_hash_function.
Definition: mmath.c:255

random_prime_number
int64 random_prime_number(int low_size, int up_size, int k)
Generates a random prime number with number of bits between low_size and up_size. k specifies the cer...
Definition: mmath.c:117

extended_gcd
int64 extended_gcd(int64 s, int64 t, int64 *u, int64 *v)
calculates the pgcd and the corresponding Bezout decomposition. pgcd = s*u + t*v
Definition: mmath.c:234

is_prime_naive
bool is_prime_naive(int64 p)
checks if p is prime. complexity O(p), certainty 100%
Definition: mmath.c:22

rand_int64
int64 rand_int64(int64 low, int64 up)
generates a random int64 inside [low, up]
Definition: mmath.c:62

types.h
a file with comfy aliases for long type signatures

int64
#define int64
alias for long long int
Definition: types.h:17

uint8
#define uint8
alias for unsigned char
Definition: types.h:32

uint32
#define uint32
alias for unsigned long int
Definition: types.h:22