sage.rings.bernoulli_mod

bernoulli_mod_p(...)

File: sage/rings/bernoulli_mod_p.pyx (starting at line 85)

Returns the bernoulli numbers $B_0, B_2, ... B_{p-3}$ modulo $p$.

INPUT:
    p -- integer, a prime

OUTPUT:
    list -- Bernoulli numbers modulo $p$ as a list
            of integers [B(0), B(2), ... B(p-3)].

ALGORITHM:
    Described in accompanying latex file.

PERFORMANCE:
    Should be complexity $O(p \log p)$.

EXAMPLES:
Check the results against PARI's C-library implemention (that
computes exact rationals) for $p = 37$:

    sage: bernoulli_mod_p(37)
     [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]
    sage: [bernoulli(n) % 37 for n in xrange(0, 36, 2)]
     [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]

Boundary case:
    sage: bernoulli_mod_p(3)
     [1]
    
AUTHOR:
    -- David Harvey (2006-08-06)

bernoulli_mod_p_single(...)

File: sage/rings/bernoulli_mod_p.pyx (starting at line 211)

Returns the bernoulli number $B_k$ mod $p$.

INPUT:
    p -- integer, a prime
    k -- even integer in the range $0 \leq k \leq p-3$

OUTPUT:
    The $k$-th bernoulli number mod $p$.

ALGORITHM:
    Uses the identity
      $$ (1-g^k) B_k/k = 2\sum_{r=1}^{(p-1)/2} g^{r(k-1)} ( [g^r/p] - g [g^(r-1)/p] + (g-1)/2 ), $$
    where $g$ is a primitive root mod $p$, and where square brackets
    denote the fractional part. This identity can be derived from
    Theorem 2.3, chapter 2 of Lang's book "Cyclotomic fields".

PERFORMANCE:
    Linear in $p$. In particular the running time doesn't depend on k.
    
    It's much faster than computing *all* bernoulli numbers by using
    bernoulli_mod_p(). For p = 1000003, the latter takes about 3s on my
    laptop, whereas this function takes only 0.06s.
    
    It may or may not be faster than computing literally bernoulli(k) % p,
    depending on how big k and p are relative to each other. For example on
    my laptop, computing bernoulli(2000) % p only takes 0.01s. But
    computing bernoulli(100000) % p takes 40s, whereas this function still
    takes only 0.06s.

EXAMPLES:
    sage: bernoulli_mod_p_single(1009, 48)
    628
    sage: bernoulli(48) % 1009
    628
    
    sage: bernoulli_mod_p_single(1, 5)
    Traceback (most recent call last):
    ...
    ValueError: p (=1) must be a prime >= 3
    
    sage: bernoulli_mod_p_single(100, 4)
    Traceback (most recent call last):
    ...
    ValueError: p (=100) must be a prime
    
    sage: bernoulli_mod_p_single(19, 5)
    Traceback (most recent call last):
    ...
    ValueError: k (=5) must be even
    
    sage: bernoulli_mod_p_single(19, 18)
    Traceback (most recent call last):
    ...
    ValueError: k (=18) must be non-negative, and at most p-3
    
    sage: bernoulli_mod_p_single(19, -4)
    Traceback (most recent call last):
    ...
    ValueError: k (=-4) must be non-negative, and at most p-3

Check results against bernoulli_mod_p:

    sage: bernoulli_mod_p(37)
     [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]
    sage: [bernoulli_mod_p_single(37, n) % 37 for n in xrange(0, 36, 2)]
     [1, 31, 16, 15, 16, 4, 17, 32, 22, 31, 15, 15, 17, 12, 29, 2, 0, 2]

    sage: bernoulli_mod_p(31)
     [1, 26, 1, 17, 1, 9, 11, 27, 14, 23, 13, 22, 14, 8, 14]
    sage: [bernoulli_mod_p_single(31, n) % 31 for n in xrange(0, 30, 2)]
     [1, 26, 1, 17, 1, 9, 11, 27, 14, 23, 13, 22, 14, 8, 14]

    sage: bernoulli_mod_p(3)
     [1]
    sage: [bernoulli_mod_p_single(3, n) % 3 for n in xrange(0, 2, 2)]
     [1]

    sage: bernoulli_mod_p(5)
     [1, 1]
    sage: [bernoulli_mod_p_single(5, n) % 5 for n in xrange(0, 4, 2)]
     [1, 1]

    sage: bernoulli_mod_p(7)
     [1, 6, 3]
    sage: [bernoulli_mod_p_single(7, n) % 7 for n in xrange(0, 6, 2)]
     [1, 6, 3]
     
AUTHOR:
    -- David Harvey (2007-08-31)

verify_bernoulli_mod_p(...)

File: sage/rings/bernoulli_mod_p.pyx (starting at line 35)

Computes checksum for bernoulli numbers.

It checks the identity
    $$ \sum_{n=0}^{(p-3)/2} 2^{2n} (2n+1) B_{2n}  \equiv  -2 \pmod p $$

(see "Irregular Primes to One Million", Buhler et al)
    
INPUT:
    data -- list, same format as output of bernoulli_mod_p function

OUTPUT:
    bool -- True if checksum passed
    
EXAMPLES:
    sage: from sage.rings.bernoulli_mod_p import verify_bernoulli_mod_p
    sage: verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(3)))
    True
    sage: verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(1000)))
    True
    sage: verify_bernoulli_mod_p([1, 2, 4, 5, 4])
    True
    sage: verify_bernoulli_mod_p([1, 2, 3, 4, 5])
    False

This one should test that long longs are working:
    sage: verify_bernoulli_mod_p(bernoulli_mod_p(next_prime(20000)))
    True

AUTHOR: David Harvey

Module bernoulli_mod_p

bernoulli_mod_p(...)

bernoulli_mod_p_single(...)

verify_bernoulli_mod_p(...)