modulo.cc File Reference

This is the implementation part of some number theoretic functions. More...

#include "modulo.H"
#include <iostream>
#include "sqrt_modulo.cc"

Include dependency graph for modulo.cc:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	numtheory
Defines
#define	nightshift(VV, RR, KK)
Functions
bool	numtheory::strong_probab_prime (const unsigned int p, const unsigned int base)
bool	numtheory::probab_prime (const unsigned int p)
bool	numtheory::is_prime (register const int p)
signed int	numtheory::jacobi (int a, unsigned int b)
signed int	numtheory::legendre (signed int a, const unsigned int p)
unsigned int	numtheory::invmod (const unsigned int x, const unsigned int m)
unsigned int	numtheory::bininvmod (register unsigned int x, register const unsigned int m)
static const char shifts[64]	numtheory::__attribute__ ((aligned(64)))
unsigned int	numtheory::montgominvmod (register unsigned int x, unsigned int m)

---

Detailed Description

This is the implementation part of some number theoretic functions.

The functions implemented in this file provide support for fast modulo operations (multiplication, exponentiation, computation of the modular inverse, quadratic residues) and some integer functions (greatest common divisor, prime numbers).

Most of these functions contain also optimized assembler code for Intel Pentium and AMD Athlon processors.

Definition in file modulo.cc.

---

Define Documentation

#define nightshift	(	VV,
		RR,
		KK		)

Value:

asm( \
   "mov %[v],%%ecx \n\t" \
   "and $0x3f,%%ecx \n\t" \
   "test $0x7f,%[v] \n\t" \
   "movzx %[shifts](%%ecx),%%ecx \n\t" \
   "jnz 1f \n\t" \
   "bsf %[v],%%ecx \n\t" \
   "1: add %%ecx,%[k] \n\t" \
   "shr %%cl,%[v] \n\t" \
   "shl %%cl,%[r] \n" \
   : [v] "+r" (VV), [r] "+r" (RR), [k] "+rm" (KK) : [shifts] "o" (shifts[0]) : "cc", "ecx");

Definition at line 484 of file modulo.cc.

---