Basic arithmetic with C integers

class sage.rings.fast_arith.arith_int

Bases: object

gcd_int(a, b)

inverse_mod_int(a, m)

rational_recon_int(a, m)

Rational reconstruction of a modulo m.

xgcd_int(a, b)

class sage.rings.fast_arith.arith_llong

Bases: object

gcd_longlong(a, b)

inverse_mod_longlong(a, m)

rational_recon_longlong(a, m)

Rational reconstruction of a modulo m.

sage.rings.fast_arith.prime_range(start, stop=None, algorithm='pari_primes', py_ints=False)

List of all primes between start and stop-1, inclusive. If the second argument is omitted, returns the primes up to the first argument.

This function is closely related to (and can use) the primes iterator. Use algorithm “pari_primes” when both start and stop are not too large, since in all cases this function makes a table of primes up to stop. If both are large, use algorithm “pari_isprime” instead.

Algorithm “pari_primes” is faster for most input, but crashes for larger input. Algorithm “pari_isprime” is slower but will work for much larger input.

INPUT:

• start – lower bound

• stop – upper bound

• algorithm – string, one of:

  • “pari_primes”: Uses PARI’s primes function. Generates all primes up to stop.

    Depends on PARI’s primepi function.

  • “pari_isprime”: Uses a mod 2 wheel and PARI’s isprime function by calling

    the primes iterator.

• py_ints – boolean (default False), return Python ints rather than Sage Integers (faster)

EXAMPLES:

sage: prime_range(10)
[2, 3, 5, 7]
sage: prime_range(7)
[2, 3, 5]
sage: prime_range(2000,2020)
[2003, 2011, 2017]
sage: prime_range(2,2)
[]
sage: prime_range(2,3)
[2]
sage: prime_range(5,10)
[5, 7]
sage: prime_range(-100,10,"pari_isprime")
[2, 3, 5, 7]
sage: prime_range(2,2,algorithm="pari_isprime")
[]
sage: prime_range(10**16,10**16+100,"pari_isprime")
[10000000000000061, 10000000000000069, 10000000000000079, 10000000000000099]
sage: prime_range(10**30,10**30+100,"pari_isprime")
[1000000000000000000000000000057, 1000000000000000000000000000099]
sage: type(prime_range(8)[0])
<type 'sage.rings.integer.Integer'>
sage: type(prime_range(8,algorithm="pari_isprime")[0])
<type 'sage.rings.integer.Integer'>

AUTHORS:

• William Stein (original version)
• Craig Citro (rewrote for massive speedup)
• Kevin Stueve (added primes iterator option) 2010-10-16
• Robert Bradshaw (speedup using Pari prime table, py_ints option)