Header for mmath.c. More...
Go to the source code of this file.
Macros | |
| #define | GOLDEN_RATIO 0.61803398875 |
Functions | |
| int64 | rand_int64 (int64 low, int64 up) |
| generates a random int64 inside [low, up] More... | |
| bool | is_prime_naive (int64 p) |
| checks if p is prime. complexity O(p), certainty 100% More... | |
| 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, the slower the calculation but higher certainty. complexity is O(k) More... | |
| 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 certainty of the result being prime. There is a (1/4)^k probability of a false positive. The greater the value of k, the slower the calculations. returns -1 if a prime wasn't found... More... | |
| 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 More... | |
| 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 implementation (a ^ m) % n = x More... | |
| 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) % n = x More... | |
| int64 | extended_gcd (int64 s, int64 t, int64 *u, int64 *v) |
| calculates the pgcd and the corresponding Bezout decomposition. pgcd = s*u + t*v More... | |
| 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. More... | |
Detailed Description
Header for mmath.c.
Function Documentation
◆ extended_gcd()
calculates the pgcd and the corresponding Bezout decomposition. pgcd = s*u + t*v
- Parameters
-
s pgcd(s, _) t pgcd(_, t) u return value v return value
- Returns
- int64 : the value of pgcd
◆ 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, the slower the calculation but higher certainty. complexity is O(k)
- Parameters
-
p potential prime k
- Returns
- true : p is prime with 1 - (1/4)^k certainty
- false : p isn't prime with 100% certainty
◆ is_prime_naive()
| bool is_prime_naive | ( | int64 | p | ) |
checks if p is prime. complexity O(p), certainty 100%
- Parameters
-
p
- Returns
- true : p is prime
- false : p is not prime
◆ jenkins_one_at_a_time_hash()
Jenkins one at a time hash function https://en.m.wikipedia.org/wiki/Jenkins_hash_function.
- Parameters
-
key len
- Returns
- uint32
◆ modpow()
calculates the exponent of a to the power of m modulo n in O(m log m). this is the main implementation (a ^ m) % n = x
- Parameters
-
a m n
- Returns
- int : the value of x
TODO: actually implement the iterative verstion...
◆ modpow_naive()
calculates the exponent of a to the power of m modulo n in O(m^2). (a ^ m) % n = x
- Parameters
-
a m n
- Returns
- int : the value of x
◆ modpow_r()
calculates the exponent of a to the power of m modulo n in O(m log m). _r stands for recursive (a ^ m) % n = x
- Parameters
-
a m n
- Returns
- int : the value of x
◆ rand_int64()
generates a random int64 inside [low, up]
- Parameters
-
low lower bound (included) up upper bound (included)
- Returns
- int64
◆ 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 certainty of the result being prime. There is a (1/4)^k probability of a false positive. The greater the value of k, the slower the calculations. returns -1 if a prime wasn't found...
- Parameters
-
low_size up_size k
- Returns
- int64
