flagrs 0.1.4

Rust Number Theory

flagrs

This is an experimental project parallel to my PyNTL project where I attempt to reimplement parts from my flagmining library as CPython extension code in Rust.

Is designed to be fast. Uses the rug library as a lightweight wrapper around GMP.

Due to some lacking functionality in rust-cpython==0.6.0 it depends on my own fork of said project, so you probably won't be able to compile it.

ZZ : ℤ

Normal Integer Operations

x+y -> n, x-y -> n, x*y -> n

Normal addition, subtraction, and multiplication.

x//y -> q, x%y -> r, divmod(x,y) -> (q,r)

Integers act Euclidean.

x**e, pow(x,e)

Normal exponentiation. e must be a natural number (i.e. non-negative integer).

bool(x), x.__bool__() -> bool

Numbers are true if they're non-zero.

n.sqrt() -> (w,r)

Floored integer square root with remainder. w*w + r == n.

n.root(d) -> (w,r)

Floored integer dth root with remainder. w**d + r == n.

-x

Negation.

abs(x)

Absolute value.

x.sign() -> s

The sign (also called signum) of x (-1, 0, or 1).

Bitwise Operations

x|y, x&y, x^y

Bitwise OR, AND, and XOR.

~x

Bitwise negation, acting as if the integer had infinite width. Equivalent to -x-1.

x<<i, x>>i

Bit shifts (can be negative).

n.nbits() -> c

Number of bits needed to represent the absolute value of n.

A synonym for n.bit_length() or len(n).

n.weight() -> c

Number of bits set in the absolute value of n.

n.truncate(bits, [signed=False])

Truncate n to the given number of bits. Negative numbers are treated as if they're in two's-complement form for the given bit width.

If signed is True the resulting bits will be re-interpreted as a signed value and so the result might be negative.

n.next_bit() -> b

Next power-of-two bigger than n.

list(n) -> [bool...].

Integers also function implicitly as a list of bits, from least significant to most significant.

>>> list(ZZ(256+16+1))
[True, False, False, False, True, False, False, False, True]

n[i] -> bool

Checks bit i (0-indexed).

n[i:j] -> v

Returns a number with the bits set in the slice.

Morally equivalent to (n>>i) % (1<<j-i) but supports full slice syntax, including negative numbers.

TODO: rust-cpython doesn't have PySlice objects!

Representation

str(x) -> str, x.__repr__()

Number in base-10 as a text string.

x.nbytes() -> l

Number of bytes needed to represent the number. For positive numbers this is equivalent to (x.nbits() + 7)//8. Negative numbers might require an extra bit (see x.bytes()).

x.bytes([order='big']) -> bytes

Interprets the number as base-256 and returns the digits as a bytestring.

Negative numbers are treated as if they're in two's complement representation of the minimum bit width that will successfully represent them, so -128 gives b'\x80' and -129 gives b'\xff\x7f'.

x.digits(base) -> [d...]

Yields a list of digits in base base. The base can be negative, but must have a magnitude of 2 or more.

Modular Arithmetic

n.inv_mod(m) -> r

Returns $1/n \pmod m$.

pow(x,e,m)

Exponentiation under a modulus. e can be negative if gcd(x,m) == 1.

a.kronecker(n) -> k

Kronecker symbol $$(\frac{a}{n})$$. For primes it corresponds to the Legendre symbol.

m.M -> <ZMod type>

Access to the modular numbers using the given number as modulus. See below for ZMod.

>>> F = ZZ(13).M
>>> F(3) * 5
(2)

Factors

n.gcd(m...) -> g

Returns the GCD of n with all arguments.

n.egcd(m) -> (g,x,y)

Extended GCD yielding Bézout coefficients. x*n + m*y == g.

n.lcm(m...) -> m

Returns the LCM of n with all arguments.

n.is_prime([reps=25]) -> bool

Trivial divisors, then Baille-PSW, then $(reps-24)$ rounds of Miller-Rabin.

n.next_prime() -> p

Returns the next prime larger than n.

n.make_odd() -> (q,e)

Returns the odd part and exponent of 2 in n. 2**e * q == n

n.small_factors([upto=0x100000]) -> (q,[(p,e)...])

Factors out all primes smaller than upto.

Returns the remaining factor q and a list of primes and their multiplicity.

x.factor_pollard(upto)

...

x.factor_fermat(s, e)

...

ZMod : ℤ_n

Represents the residue ring (or field) of integers under a given modulus. The normal arithmetic works as expected. In cases where a field is required for the operation to be well-defined, the code will simply assume the user knows what they're doing and operate under the assumption that it is (i.e. that the modulus is prime).

x/y -> z

Normal division works as expected:

>>> F = ZMod(17)
>>> F(5)/2
(11)
>>> F(11)*2
(5)

x**e -> y

Exponentiation also works as expected:

>>> ZMod(17179)(2)**0xdeadcafe
(14537)

p.EC(a,b) -> <EC type>

Access to the additive group of an Elliptic Curve using this modulus.

EC : Ellipic Curves