flagrs 0.1.4
Rust Number Theory
License: BSD-3-Clause


# flagrs

This is an experimental project parallel to my
[PyNTL](https://gitlab.com/franksh/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 `d`th 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.

``` python-console
>>> 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`.

``` python-console
>>> 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 BeÌ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:

``` python-console
>>> F = ZMod(17)
>>> F(5)/2
(11)
>>> F(11)*2
(5)
```

### `x**e -> y`

Exponentiation also works as expected:

``` python-console
>>> 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