Thursday, September 13, 2012

[oswktlbt] 64-bit factorization

I think I would like a small integer factorization routine with domain limited to unsigned long long.

Tuned for speed, likely balancing Pollard's rho with trial division, with the balance different depending on the size of the input.  Perhaps tuned kernels FFTW-style.

unsigned long long get_factor(unsigned long long x);
/* Returns a prime factor of x.  Returns x if x is prime, 0, or 1.
  To get the entire factorization, divide by the result and iterate.
*/

Inspiration was wanting a permutation using a primitive root. Also need small modular exponentiation. These routines are useful for more than just cryptography.

No comments :